为了应对量子计算机对现有密码算法的威胁，研究人员和密码学家已经着手开发新一代的密码算法，这些算法基于各种数学难题，旨在抵御量子计算的攻击。根据底层数学问题分类，后量子密码算法研究目前主要有5种技术路线，分别是基于格的密码、基于编码的密码、基于多变量的密码、基于哈希函数的密码以及基于曲线同源的密码。
基于格的密码：格（Lattice)俗称为“数的几何”(Geometry ofnumbers)，是一种数与形相结合的代数结构，其本质是一个离散加法子群，定义为一组线性无关的非零向量(格基）的整系数线性组合。格密码基于格上问题的困难性，如最短向量问题（SVP）、最近向量问题(CVP)及其变种等。格最初多被用于某些密码问题的分析，直到Ajtai和Regev分别引入小整数解问题（SIS)和容错学习问题（LWE)，开启了实用的可证明安全格密码研究。SIS和LWE被广泛用于构造密码哈希函数、身份认证和数字签名等密码方案以及全同态加密、不可区分混淆等高等密码算法。目前主流的加解密格体制和数字签名个密码体制基本基于这两个问题，NIST目前选择标准化的算法也多数是基于格的。基于格的算法的公私钥尺寸更小，计算速度也更快，且能被用于构造多种密码学原语，因此更适用于实际应用环境。
基于编码的密码：信道编码的目标是设计高效的冗余编码，以便在传输过程中纠正由信道噪声引入的错误，从而实现正确的译码。然而研究人员们发现某些编码的译码计算是困难的，这种译码的困难性为构造安全的密码算法提供了思路。基于编码的密码通常具有较小的密文，但其缺点是公钥大、密钥生成慢，在实用化方面有待提升。1978年McEliece提出了Classical-McEliece,这是基于对称群隐藏子群问题的困难性，使用Goppa码设计的公钥加密方案。与现有公钥密码方案相比，加密速度更快，但由于公钥尺寸太大，实用性较低。随着后量子密码的提出，McEliece等编码密码方案因具备后量子的特性，被认为可能成为基于数论的公钥密码体制的替代品，并成功通过了NIST-PQC前三轮评估，并入选了第三轮胜出算法集Finalists。
基于多变量的密码：基于多变量的后量子密码算法是后量子密码算法最早的类别之一，这类密码算法基于求解高次多变量方程组这一NP难问题。通常，这些密码算法采用二次多项式，并将有限域上一组二次多项式作为公钥映射。代表性的基于多变量的密码算法包括HFEv-类型的GeMSS签名体制和UOV类型的Rainbow签名算法。这两个算法都顺利通过了NIST-PQC评估的前三轮，并于2022年7月被分别选入第三轮的胜出集合Alternates集和Finalists集。多变量密码算法相比于其他后量子密码算法具有签名验签速度快、消耗资源少的优势，虽然其具有公钥尺寸大的缺点，但适用于无需频繁进行公钥传输的应用场景。
基于哈希函数的密码：哈希函数是将任意长度的消息映射到固定长度输出的映射，其算法完全公开，没有密钥或任何秘密信息，设计的主要安全目标是使得找到各类碰撞最有效的方法是通用攻击。哈希函数的困难性可直接假设等同于理想的通用攻击的复杂度，其安全性并不会随着设计的优化而减弱。哈希函数多用于数字签名算法，其中最具代表性的由Merkle提出的数字签名方案MSS采用哈希树将多个一次性验证密钥的有效性降低到一个公钥的有效性。在后量子标准化过程中，取得重要进展的代表性算法包括XMSS和SPHINCS+。XMSS是一种有状态的签名，是在MSS基础上提出的一种具有更小签名的可证明安全的数字签名方案。SPHINCS+签名算法是一种无状态的签名，采用了一种在Merkle树和Goldreich 树之间相折中的SPHINCS超树的结构进行构造。基于哈希函数的签名方案的理论安全性高，但也存在签名体积过大，有状态的哈希签名所能支持的签名次数有限等缺点。尽管目前基于Hash函数的数字签名方案成果并不多，但是由于Hash函数独特的属性及其实用性，在后量子时代，基于Hash函数的签名算法具有巨大的潜力。
基于曲线同源的密码：同源是指两条椭圆曲线之间存在一个映射，这个映射能够保持它们的群结构同态。同源密码包括超奇异同源Diffie-Hellman（SIDH）和CSIDH等公钥密码算法，可用作传统的椭圆曲线密钥交换（ECDH）的后量子替代。2011年Jao等人首次提出了超奇异同源Diffie-Hellman 问题，并设计了基于超奇异同源的公钥密码系统SIKE。与其他几类算法相比，其公钥和密文尺寸都非常小，可以在通信量受限的环境下运行，但是其运行效率非常低，其密钥生成、加密和解密速度几乎比基于格的算法低两个数量级，这使其不易实现在一些计算性能不足的设备上。SIKE算法在2022年7月进入了NIST-PQC评估的第四轮，但仅1个月不到就遇到了致命性的攻击。但是，SIKE的失败并不意味着同源密码的崩塌，同源问题本身并未被破解，仍是后量子密码的重要研究方向之一。
获取文件
扫码回复
