后量子密码学 - 维基百科，自由的百科全书

此條目需要更新。 (2024年8月19日) 請更新本文以反映近況和新增内容。完成修改後請移除本模板。

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

后量子密码学（英語：Post-quantum cryptography，缩写：PQC），又称為防量子、量子安全、抗量子计算，是密码学的一个研究领域，专门研究能够抵抗量子计算机進行密码分析攻擊的加密算法（特别是公钥加密算法）。计算机与互联网领域广泛使用的公钥加密算法均基于三个计算难题：整数分解问题、离散对数问题或椭圆曲线离散对数问题。然而，这些难题均可使用量子计算机并应用秀尔算法破解^[1][2]，或是比秀爾算法更快，需求量子位元更少的其他演算法破解^[3]。

雖然到2023年為止，量子電腦的電腦性能還無法破解一般使用的加密算法^[4]，不過密碼學研究者已在考慮Y2Q或是Q-Day，也就是可以用量子電腦破解目前使用演算法的一天，並為了那一天設計無法用量子電腦破解的新加密演算法。透過2006年起舉辦的一系列PQCrypto學術研討會，欧洲电信标准协会（ETSI）舉辦的數個Quantum Safe Cryptography工作坊，以及量子計算研究所（英语：Institute for Quantum Computing），后量子密码学上上的研究已受到學術界及產業界的注意^[5][6][7]。據傳目前存在，廣泛的先竊取，後解密（英语：harvest now, decrypt later）程式也視為是早期推動後量子密碼學的動力之一，因為目前記錄的資料可能在未來都仍是敏感資料^[8][9][10]。

目前量子計算的攻擊主要是針對公鑰演算法，大部份目前使用的對稱密鑰加密以及散列函數比較可以抵擋量子電腦的攻擊^[2][11]。量子的格罗弗算法確實可以加速對於對稱加密的攻擊，但密鑰長度加倍即可有效抵抗此攻擊^[12]。後量子的對稱密碼學和現行的對稱密碼學差異不大。

美國國家標準技術研究所（NIST）提出了頭三個後量子加密標準的正式版本^[13]。

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

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

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

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

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

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