后量子密码学

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

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

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

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

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

公钥密码学

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

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

格密码学

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

主条目：格密码学

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

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

编码密码学

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

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

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

多变量密码学

主条目：多变量密码学

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

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

${\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}}$

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

$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），与瑞夫·墨克提出的墨克树（Merkle tree）。后来以此为基础，又出现了Winternitz签名和GMSS签名，近年来的成果则包括SPHINCS签名与XMSS签名方案。

散列密码学的优点：

数字签名的安全性仅依赖于散列函数，而足够长的散列函数能抵御量子计算机的攻击。并且散列函数自20世纪以来已在多个加密协议中广泛使用，经过长期实践验证，被认为具有高度稳固的安全性基础。相比其他后量子算法（如格密码）仍在接受理论与实战检验，散列密码体系的未知风险较小，未来被新兴理论或实践手段破解的可能性也较低。

缺点则包括：

第一，密钥体积通常较大，这一限制使得其在传统密码系统中长期未被广泛采纳，直到后量子密码学的发展重新激发了相关研究兴趣。

第二，许多后量子散列签名方案为有状态的（stateful），每次签名后必须更新私钥状态（例如计数器），以确保每个状态仅使用一次；若状态被重复使用，可能导致私钥泄露。例如，在多台设备上同时使用同一私钥，若状态未能同步更新，就可能引发严重的安全漏洞。SPHINCS+ ，一种典型的无状态（stateless）散列签名方案解决了该问题，但代价是签名体积更大、计算开销也更高。

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

主条目：超奇异同源密钥交换

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

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

安全規約

在密碼學研究中，我們希望找到與特定演算法等價、且已知的數學難題。當這個等價的數學難題之解法被提出，就意味著該密碼演算法是可行、可被計算的。這個尋找等價數學難題的研究領域就被稱為安全規約（security reductions）。