一、简介

HQC（Hamming Quasi-Cyclic，汉明准循环码）是一种基于编码理论的后量子密钥封装机制（KEM），用于在公共网络中安全交换加密密钥。

HQC 用准循环综合解码问题隐藏低重量秘密，用私钥完成噪声抵消，用公开 RMRS 码恢复消息，再用带盐 FO 转换把基础公钥加密升级成抗选择密文攻击的密钥封装机制。

二、基本内容

1.流程

Key Encapsulation Mechanism，密钥封装机制

Bob：
(pk, sk) ← KeyGen()

Alice：
(K, ct) ← Encaps(pk)
把 ct 发给 Bob

Bob：
K' ← Decaps(sk, ct)

正常情况下：
K' = K

协议：

HQC 生成共享密钥 K
              ↓
HKDF / KDF 派生会话密钥
              ↓
AES-GCM 或 ChaCha20-Poly1305 加密数据

2.

Hamming：汉明度量

$HQC 中所有主要向量都位于二元域：\mathbb F^n_2,每个分量只有 0 或 1$

汉明重量就是其中1的数量：wt(x)

HQC的秘密向量、临时随机向量和错误向量都是低汉明重量向量

Quasi-Cyclic：准循环

$HQC 把长度为 n 的二进制向量a=(a_0,a_1,…,a_{m-1})$

$对应多项式：a(X)=a_0+a_1X+…+a_{n-1}X^{n-1}$

$所有乘法在环R=\mathbb F_2[X]/(X^n-1)中进$

$因为X^n=1，所以乘法具有循环卷积的效$

循环矩阵和多项式乘法是等价的。一个完整的 n×n 循环矩阵只需要保存第一行，也就是一个长度为 n 的向量，因此准循环结构能够显著压缩公钥。HQC 使用双循环码，其校验矩阵可以写成：H=(In∣rot(h))

其中 rot(h) 是由向量 h 生成的循环矩阵。

Code-based：码基密码

HQC：合法接收者可以把密文中的大部分干扰抵消掉，只留下一个纠错码能够处理的小错误；攻击者无法完成这个抵消。

3.两套编码

随机准循环码

其校验矩阵为：$H=(I_n|rot(h))$

公钥关系为：$s=x+h \cdot y=H \begin {pmatrix} x \ y \end {pmatrix}$

h为均匀随机的公开向量，x、y为度汉明重量秘密向量，s为公开向量

公开的RMRS纠错码

HQC 使用公开的拼接码：C=Reed-Solomon∘Reed-Muller

具体来说：

外层使用缩短 Reed-Solomon 码；
内层使用重复的 RM(1,7) Reed-Muller 码；
Reed-Muller 码处理比特级随机错误；
Reed-Solomon 码进一步处理错误符号。

这里的纠错码 C 并不是秘密陷门。

三、算法分析

HQC-PKE

记：

x,y：长期秘密向量，重量为 ω； 
h：公开随机向量； 
s=x+hy：公钥主体； 
r1,r2：每次加密使用的临时低重量向量； 
e：低重量错误向量； 
C(m)：消息 m 的纠错码编码。

所有加减法都在$\mathbb F_2$中，故a-b=a+b

1.密钥生成

随机选择两个固定重量的向量:$wt(x)=wt(y)=w$,再随机生成h

计算$s=x+hy$$，得到公钥$$pk=(h,s)$$私钥主要包含用于重新生成 y 的种子：$$sk=seed_{sk}$$

公钥不需要直接保存完整 h，而是保存生成 h 的 32 字节种子和向量 s。

2.加密

先从随机数确定性生成：$$r_1,r_2,e 满足wt(r_1)=wt(r_2)=w_r \quad wt(e)$$

计算密文第一部分：$u=r_1+hr_2$ 第二部分：$v=C(m)+sr_2+$

所以PKE密文为：$c_{PKE}=(u,v)$

当前规范中的精确形式还包含 Truncate，因为环长度 n 略大于纠错码长度 n1n2：$v=C(m)+Truncate(sr2+e,ℓ$$ 其中：$$ℓ=n−n1n2$

3.解密

接收方知道秘密向量 y，计算：v-uy，代入密文：

$v−uy=C(m)+sr_2+e−uy=C(m)+(x+hy)r_2+e−(r_1+hr_2)y=C(m)+xr_2+r_1y+e$

(环乘法可以交换$hyr_2=hr_2$）

定义剩余错误：$e^′=xr_2−r_1y+e$ 于是接收方得到：$C(m)+e^′$

只要：$wt(e^{‘}) \leq \Delta$$ 其中$$\Delta$是纠错码的纠错能力，就能运行:$m=C.Decode(v−uy)$恢复消息