知识点滴 | 后量子密码

什么是后量子密码

数后量子密码指的是可以抵御已知量子计算攻击的现代公钥密码，这类密码算法的安全性依赖于计算复杂度。后量子加密，是一种新的加密方法，其能够利用现有经典计算机实现足以抵御未来量子攻击的能力。

后量子密码算法的优点在于可覆盖非对称算法的所有场景，且升级改造成本较低；缺点是缺少长期安全性证明，仍存在被破解的可能性。

后量子密码的构造方式

1.基于格的后量子密码算法。格是一种数学结构，定义为一组线性无关的非零向量（称作格基）的整系数线性组合。具体来说，给定一组格基图片对任意的整数图片都是属于这个格的向量。对于同一个格，其可以拥有不同的格基，并且求解格中的最短向量问题和最近向量问题是目前格理论中主要的非确定性多项式难题。除此之外，格中还有一些其他的困难问题，如LWE问题、有界距离解码问题、小整数解问题等。基于格的算法与现代公钥加密算法的功能一样，均可实现加解密、数字签名、属性加密、同态加密、密钥交换等多种密码学构造。

在后量子加解密算法方面，通过总结目前主流的基于格的加解密算法，我们发现以LWE困难问题为基础的格密码方案不仅应用广泛，而且安全性更高。

在后量子签名算法方面，基于格的签名算法的构造与现有的公钥密码体制略有不同。对于RSA、ElGamal、椭圆曲线等现有公钥密码体制而言，通过调换加解密算法的公私钥顺序即可将其转换为签名算法，但是基于格的密码方案不具有此种对偶特性，在设计基于格的后量子签名算法时通常采用零知识证明协议进行构造，即证明者证明自己拥有与对应身份的公钥相匹配的私钥，但是不泄露任何关于私钥的信息。

2.基于编码的后量子密码算法。编码理论是数学与计算机科学的一个分支，用来处理在噪声信道中传送信息时进行错误处理。基于编码的密码体制也被认为是在量子计算机中相对安全的密码算法，其核心在于将一定数量的错误码字引入编码中，纠正错误码字或计算校验矩阵的伴随式是困难的。

针对基于编码的数字签名方案，1990年有学者提出了第一个基于编码的数字签名方案。1991年，又有学者构造了一类同时具有签名、加密和纠错能力的公钥体制。随后，学者们在此基础上进行了一系列改进，并指出基于编码的公钥密码体制或许可以成为基于数论的公钥密码体制的一个很好的替代。

3.基于哈希的后量子密码算法。基于Hash函数设计的后量子密码算法主要集中在数字签名算法中，Hash函数具有很好的抗碰撞性，当Hash函数能抗强碰撞时，设计的数字签名算法便可有效抵抗量子计算的攻击。考虑到Hash函数独特的属性及其实用性，在量子时代，基于Hash函数的签名算法有望成为最有前途的数字签名方案之一。

4.基于多变量的后量子密码算法。作为后量子密码算法的最早成员之一，基于多变量的后量子密码算法相比其他三种主流构造方式而言具有更多的研究成果。一个基于多变量的公钥密码系统将有限域上一组二次多项式作为它的公钥映射，其主要安全假设为求解有限域上非线性方程组这个NP难问题。

5.其他后量子密码算法。除上述四种主流算法外，基于量子密码和基于同源的密码体制也在密码学家的研究范围内。2006年，“困难的同质空间”概念被提出，为基于椭圆曲线同源的密码系统奠定了基础。同年，又有学者提出了一个新的适用于公钥密码系统的通用数学问题——对于有限域上的椭圆曲线，计算给定椭圆曲线之间的同源。同时，ElGamal公钥加密和Diffie-Hellman密钥协议被提出用于同源密码系统。2012年，有学者提出了量子单向函数的候选方案，还有学者研究了经典认证密钥交换框架下量子密钥的分配问题。2014年，学术界公布了一个在椭圆曲线同源基础上不可否认的数字签名方案。2017年，学者们对超奇异同源密码系统的循环终止故障攻击和第一类故障攻击分别进行了讨论。2022年，针对超奇异同源密钥交换协议，提出了不同的密钥恢复攻击方案。但是，这些后量子密码算法并未像主流算法一样形成体系。

后量子密码算法的发展现状

1.国际后量子密码算法发展情况。美国国家标准与技术研究院（NIST）作为国际密码算法事实上的标准制订方，从2012年开始启动后量子密码算法研究，2016年启动算法征集，并历经3轮筛选后终于公布第一批拟标准化的算法，历时长达10年。NIST公布，公钥加密场景的Kyber以及数字签名场景的Dilithium、Falcon、SPHINCS+将作为第一批标准化的后量子密码算法，预计2024年正式发布标准。Kyber、Dilithium、Falcon是基于格的数学问题设计，SPHINCS+算法基于哈希安全问题设计。由于基于格的算法在安全与性能方面具有一定优势，NIST推荐优先使用Kyber、Dilithium算法，推荐Falcon用于对数字签名长度有限制的场景，SPHINCS+只是作为备用。

2.国内后量子密码算法标准发布时间尚未公布。我国密码科学技术国家重点实验室、中国密码协会等有开展后量子密码算法的研讨，并以课题形式资助算法研究。中国密码学会2018年举办非对称算法设计竞赛，鼓励提交能抵御量子攻击的后量子密码算法。2020年公布的评选结果显示，大部分算法也是基于格设计。

名词解释

格基（RLWE）：给定均匀随机选取的a∈Rq，服从某分布{\chi}_{s}的s\in\mathcal{R}_q，以及服从某分布{\chi}_{e}的e∈Rq，记bi=ais+ei。

LWE：是指容错学习问题，可以理解为，需要找到一组系数，使得一组基向量的线性组合无限逼近目标向量，使用噪音误差的大小来定义我们距离目标向量有多近。

RSA：RSA公开密钥密码体制是一种使用不同的加密密钥与解密密钥，由已知加密密钥推导出解密密钥在计算上是不可行的密码体制。RSA是被研究得最广泛的公钥算法，从提出到现在已近30年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

零知识证明：是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

Hash函数：一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

NP：多项式复杂程度的非确定性问题。

公钥密码体制：即公共密钥密码体制，其原理是加密密钥和解密密钥分离。用户可以将自己设计的加密密钥和算法公诸于众，而只保密解密密钥。任何人利用这个加密密钥和算法向该用户发送的加密信息，该用户均可以将之还原。公共密钥密码的优点是不需要经安全渠道传递密钥，大大简化了密钥管理。

ElGamal公钥加密：ElGamal加密算法是基于离散对数问题的一种公钥加密算法。其基本思想是将信息用随机数生成的密钥进行加密，然后通过公钥来解密密文。

超奇异同源密码：是一种新兴的抵抗量子计算机的后量子密码。

Diffie-Hellman密钥协议：是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道创建起一个密钥。