后量子密码算法之HQC算法解读

上一篇我们为大家介绍了NIST PQC征集第四轮最新进展，2025年3月11日，美国国家标准与技术研究院(NIST)发布了《NIST后量子密码标准化过程的第四轮状态报告》（NIST IR 8545），宣布最终选择HQC算法为第二个密钥封装机制（KEM），作为Kyber算法的安全补充标准；并预计将在两年内发布相关标准草案。本期我们将为大家详细解读HQC算法。

HQC算法是一种基于编码理论的非对称的密钥封装机制(KEM)。早在2024年8月13日，NIST就已经发布了基于格理论的后量子KEM标准FIPS 203。与FIPS 203不同的是HQC算法基于的困难问题是非格理论的。作为KEM，HQC算法是FIPS 203的一种补充和替代方案，可以有效地避免FIPS 203中可能存在的漏洞。

基于编码理论的公钥密码

编码理论是一门研究如何有效地传输和存储数字信息的学科。其主要目标是通过设计高效、可靠且具有容错能力的编码方案，确保在数据经过传输或存储过程后能够准确恢复原始信息。基于编码理论的公钥方案最早可以追溯到上个世纪70年代由Robert McEliece提出的McEliece密码。人们对McEliece密码的信心来源于一个简单而有力的事实：在过去50多年中，没有有效的攻击算法可以破解它。这一历史记录进一步巩固了编码密码在后量子时代的重要性。

HQC算法的原理

HQC是Hamming Quasi-Cyclic的缩写，从中可以看出，HQC使用的码是基于汉明距离的拟循环码，具体地说，这种拟循环码是截断Reed-Solomon码和重复Reed-Muller码的组合。虽然HQC算法与FIPS 203使用的底层困难问题完全不同，但在算法思路上确有几分相似。

1. 噪声引入：在算法的加密阶段，随机产生一些噪声，使用公钥把噪声混入到消息编码中产生密文；在解密阶段，使用私钥和解码算法对消息进行还原。

2. FO变换：二者均采用FO变换，把IND-CPA的公钥加密（PKE）机制转换成IND-CCA2的密钥封装机制（KEM）。

HQC算法的优势和劣势

根据《NIST后量子密码标准化过程的第四轮状态报告》所述，HQC算法具有以下优势：

1. 更可靠的安全性：HQC算法能够战胜BIKE算法的决定性因素是，它在解密失败率(DFR)分析上更可靠。有证据表明HQC具有足够低的DFR。虽然BIKE算法通过小的修改也能达到同样低的DFR，但NIST认为BIKE在DFR分析上不如HQC成熟。另外，HQC不需要通过修改就能达到所需的安全属性。基于这些，NIST对HQC的安全性更有信心。

2. 性能优秀：通过表1可以看出，在密钥生成上，BIKE比HQC慢6-10倍；解封装上，BIKE比HQC慢5-7倍；密钥生成上，McEliece比HQC慢3个数量级。

3. 更短的解封密钥：这对于IoT等资源受限环境尤为重要。通过表2可看出，BIKE的解封密钥长度是HQC的7-17倍，McEliece的解封密钥长度更是比HQC大2-3个数量级。

表1 x86_64平台上BIKE/HQC/McEliece性能(单位:1000 cycles)（数据来自NIST IR 8545及openquantumsafe.org网站）

表2 BIKE/HQC/McEliece密钥和密文尺寸(单位:bytes)

根据《NIST后量子密码标准化过程的第四轮状态报告》所述，HQC算法存在下列不足之处:

1. 密钥和密文长度较长：具体来说，HQC的封装密钥长度大约比BIKE长41-47%；HQC的密文长度大约是BIKE的3倍。

2. 对网络环境敏感：在TLS1.3和QUIC协议中对后量子KEM算法进行实验得到的结果表明，在理想网络环境下，HQC的握手速度更快；而当网络环境差到一定程度时，BIKE算法表现得比HQC优秀。

HQC算法的应用场景

HQC是一种密钥封装机制，可以用于在不安全信道上建立通信双方的共享密钥，应用场景包括邮件加密、网络协议、IoT设备、在线支付系统等。

握奇公司，作为数据安全领域的资深专家，凭借30年深厚行业积累，专注密码算法、数字安全防护及安全芯片操作系统等核心技术。在持续洞察NIST标准更新动态的基础上，我们更加关注后量子算法的前沿进展，积极布局技术演进，致力于为客户提供数字安全防护解决方案，以科技赋能行业稳健发展。