后量子密码学

提示：此条目的主题不是量子密码学。

后量子密码学（英語：Post-quantum cryptography，缩写：PQC），又称抗量子计算密码学，是密码学的一个研究领域，专门研究能够抵抗量子计算机的加密算法，特别是公钥加密（非对称加密）算法。^[1]不同于量子密码学，后量子密码学使用现有的电子计算机，不依靠量子力学，它依靠的是密码学家认为无法被量子计算机有效解决的计算难题。^[1]

时至2021年，计算机与互联网领域广泛使用的公钥加密算法均基于三个计算难题：整数分解问题、离散对数问题或椭圆曲线离散对数问题，如DH、ECDH、RSA、ECDSA。然而，这些难题均可使用量子计算机并应用秀尔算法破解。^[2][1]虽然人类目前还不具备建造如此大型量子计算机的科学技术，但其安全隐患已经引起了学术研究者和政府机构的担忧。许多密码学家都在未雨绸缪，研发全新的公钥加密算法以应对将来的威胁。自第一届后量子密码学大会（PQCrypto）于2006年开办以来，本领域的研究工作愈发活跃，已成为学术和业界的关注焦点。目前，许多学术机构、政府机构、互联网公司都在开展研究，例如美国国家标准技术研究所（NIST）、欧洲电信标准机构（英语：ETSI）（ETSI）^[3]、滑铁卢大学量子计算研究所（英语：Institute for Quantum Computing）、谷歌^[4]、微软^[5]等。

在公钥加密方面，后量子密码学的研究方向包括了格密码学（英语：Lattice-based cryptography）、容错学习问题（LWE）、多变量密码学（英语：Multivariate cryptography）、散列密码学（英语：Hash-based cryptography）、编码密码学（Code-based Cryptography）与超奇异椭圆曲线同源密码学（英语：Supersingular isogeny key exchange）。密码学家认为，基于这些计算难题有望构建出不受量子计算机的威胁的公钥加密系统，替代现有的方案。^[1]

除了公钥加密，量子计算机也威胁对称加密算法和散列函数的安全，如AES、SHA等。但相比公钥加密面临的威胁而言，这一问题并不严重。借助量子计算机，格罗弗算法（Grover's algorithm）可将暴力破解的难度从${\displaystyle N}$次尝试降低到${\displaystyle {\sqrt {N}}}$次尝试。^[6]这样，128位加密（密钥空间${\displaystyle 2^{128}}$）的安全性就变为64位。但只需将密钥长度提升一倍（如使用256位加密）即可抵抗这类攻击。因此面临量子计算机的威胁，公钥加密需要重新设计，对称加密则并不需要大幅度的修改。^[1]

为了推动标准化，NIST在2017年向公众征集后量子密码方案，并最终收到了各学者提交的共69个设计。

公钥密码学

目前，后量子公钥密码学的研究方向如下。

格密码学

 

最短向量问题：格L中，给定向量空间V中的一基向量和一范数N，求V中由N度量的最短非零向量。图中蓝色的是基向量，红色的是最短向量。

主条目：格密码学（英语：Lattice-based cryptography）

格密码学（Lattice-based cryptography）是在算法构造本身或其安全性证明中应用到格的密码学。格（英语：lattice (group)）（lattice），又称点阵，是群论中的数学对象，可以直观地理解为空间中的点以固定间隔组成的排列，它具有周期性的结构。更准确地说，是在n维空间R_n中加法群的离散子群，这一数学对象有许多应用，其中存在几个称为“格问题（英语：Lattice problems）”的难题，如最短向量问题（Shortest Vector Problem）和最近向量问题（Closest Vector Problem）。许多基于格的密码系统利用到了这些难题。

经典的格密码学加密算法包括GGH加密方案（英语：GGH encryption scheme）（基于CVP，已遭破解）和NTRU加密方案（英语：NTRU encryption scheme）（受GGH启发，基于SVP）。由于容错学习问题与格问题存在联系，因此后来基于容错学习问题（LWE）与环容错学习问题（英语：Ring learning with errors）（Ring-LWE）的加密算法也属于格密码学的范畴。

编码密码学

编码密码学（Code-based Cryptography）是应用了编码理论与纠错码的密码学。

其中最早、最有代表性是McEliece密码系统（英语：McEliece cryptosystem）：首先选择一种有已知高效解码算法的纠错码作为私钥，然后对私钥进行变换（用两个随机选择的可逆矩阵${\displaystyle S}$ 与${\displaystyle P}$ “打乱”纠错码的生成矩阵），得到公钥。这样，能高效解码的特殊纠错码就被“伪装”成了一般线性码（general linear code）——一般线性码的解码十分困难，是NP困难问题。其密文就是引入随机错误的码字（codeword），有私钥者可以进行纠错得到明文，无私钥者则无法解码。

McEliece算法首次发表于1978年（仅比RSA晚一年），使用的是二元戈帕码（Binary Goppa code），经历了三十多年的考验，至今仍未能破解。但缺点是公钥体积极大，一直没有被主流密码学界所采纳。但随着后量子密码学提上日程，McEliece算法又重新成为了候选者。许多研究者尝试将二元戈帕码更换为其他纠错码，如里德-所罗门码、LDPC等，试图降低密钥体积，但全部遭到破解，而原始的二元戈帕码仍然安全。

多变量密码学

主条目：多变量密码学（英语：Multivariate cryptography）

多变量密码学（Multivariate cryptography）是应用了有限域${\displaystyle F}$ 上多元多项式的密码学，包括对称加密和非对称加密。当研究对象是非对称加密时，又叫做多变量公钥密码学（Multivariate Public Key Cryptography），缩写MPKC。此外，由于它常使用二次多项式（Multivariate Quadratic），因此又可缩写为MQ。

考虑${\displaystyle q}$ 阶的有限域${\displaystyle F_{q}}$ 。我们在其中建立一个方程组，它由n个变量与m个方程组成。

${\displaystyle {\begin{cases}y_{1}=G_{1}(x_{1},x_{2},...,x_{n})\\y_{2}=G_{2}(x_{1},x_{2},...,x_{n})\\...\\y_{m}=G_{m}(x_{2},x_{2},...,x_{n})\\\end{cases}}}$ 

其中每个方程都是一个多元多项式，通常为二次多项式。

${\displaystyle G_{l}(x_{1},...,x_{n})=\sum _{1\leqslant i\leqslant j\leqslant n}a_{ij}^{(l)}x_{i}x_{j}+\sum _{1\leqslant i\leqslant n}b_{i}^{(l)}x_{i}+c^{(l)}\quad (l=1,2,...,m)}$ 

解一般形式的多元多次方程组是一个计算难题，甚至在只有二次多项式时也是如此，这就是MQ问题。多变量密码学研究的就是基于这类计算难题的密码系统。

散列密码学

主条目：散列密码学（英语：Hash-based cryptography）

散列密码学（Hash-based Cryptography）是应用散列函数的数字签名。散列密码学的研究历史也很长，最早的研究工作包括莱斯利·兰波特于1979年提出的兰波特签名（英语：Lamport signature）（Lamport signature），与瑞夫·墨克提出的墨克树（英语：Merkle tree）（Merkle tree）。后来以此为基础，又出现了Winternitz签名和GMSS签名，近年来的工作则包括SPHINCS签名与XMSS签名方案。

散列密码学的优点是：数字签名的安全性只取决于散列函数，而足够长的散列函数不受量子计算机威胁。其缺点是：第一，密钥体积极大，因此一直没有被主流密码学界所采纳。后量子密码学重新激发了这一领域的研究。第二，许多散列密码系统的私钥是有状态的，签名后都必须更新私钥的计数器，保证同一状态不可重用，否则签名方案就会遭到攻击者破解。例如，将同一私钥同时在两台机器上使用，就会造成巨大的安全问题。SPHINCS签名解决了这一问题。

超奇异椭圆曲线同源密码学

主条目：超奇异同源密钥交换（英语：Supersingular isogeny key exchange）

超奇异椭圆曲线同源密码学（Supersingular elliptic curve isogeny cryptography）是利用超奇异椭圆曲线（英语：supersingular elliptic curves）与超奇异同源图（英语：supersingular isogeny graphs）的数学性质的密码学，可以实现超奇异同源密钥交换（英语：Supersingular isogeny key exchange）（SIDH），具有前向安全性。其使用方法和现有的迪菲－赫尔曼密钥交换相似，曾经有望直接替代当前的常规椭圆曲线密钥交换（ECDH）。

然而于2022年7月，研究人员发现该算法存在重大漏洞，并不安全。^[7][8]

参考资料

1. Daniel J. Bernstein. Introduction to post-quantum cryptography (PDF). Post-Quantum Cryptography. 2009 [2021-02-08]. （原始内容 (PDF)于2009-09-20）. 
2. Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing. 1997, 26 (5): 1484–1509. Bibcode:1995quant.ph..8027S. arXiv:quant-ph/9508027  . doi:10.1137/S0097539795293172. 
3. . ETSI Quantum Safe Cryptography Workshop. ETSI. October 2014 [24 February 2015]. （原始内容存档于2016-08-17）. 
4. Matt Braithwaite. Experimenting with Post-Quantum Cryptography. Google Security Blog. [2021-02-08]. （原始内容于2021-01-07）. 
5. Cryptography in the era of quantum computers. Microsoft. [2021-02-08]. （原始内容于2021-02-03）. 
6. Grover L.K. A fast quantum mechanical algorithm for database search. 28th Annual ACM Symposium on the Theory of Computing Proceedings. 1996. arXiv:quant-ph/9605043  . 
7. An efficient key recovery attack on SIDH (PDF). 
8. Post-quantum encryption contender is taken out by single-core PC and 1 hour. arstechnica.