后量子密码学

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

虽然到2023年为止，量子电脑的电脑性能还无法破解一般使用的加密算法，不过密码学研究者已在考虑Y2Q或是Q-Day，也就是可以用量子电脑破解目前使用算法的一天，并为了那一天设计无法用量子电脑破解的新加密算法。透过2006年起举办的一系列PQCrypto学术研讨会，欧洲电信标准协会（ETSI）举办的数个Quantum Safe Cryptography工作坊，以及量子计算研究所，后量子密码学上上的研究已受到学术界及产业界的注意。据传目前存在，广泛的先窃取，后解密程式也视为是早期推动后量子密码学的动力之一，因为目前记录的资料可能在未来都仍是敏感资料。

目前量子计算的攻击主要是针对公钥算法，大部分目前使用的对称密钥加密以及散列函数比较可以抵挡量子电脑的攻击。量子的格罗弗算法确实可以加速对于对称加密的攻击，但密钥长度加倍即可有效抵抗此攻击。后量子的对称密码学和现行的对称密码学差异不大。

美国国家标准技术研究所（NIST）提出了头三个后量子加密标准的正式版本。

## 公钥密码学

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

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

### 格密码学

<image>

格密码学（Lattice-based cryptography）是在算法构造本身或其安全性证明中应用到格的密码学。格 (群论)（lattice），又称点阵，是群论中的数学对象，可以直观地理解为空间中的点以固定间隔组成的排列，它具有周期性的结构。更准确地说，是在n维空间Rn中加法群的离散子群，这一数学对象有许多应用，其中存在几个称为“格问题”的难题，如最短向量问题（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）。

## 外部链接

- PQCrypto, 后量子密码学会议
- ETSI Quantum Secure Standards Effort
- NIST的后量子密码学项目
- PQCrypto Usage & Deployment
- ISO 27001 Certification Cost
- ISO 22301:2019 – Security and Resilience in the United States
- 常用加密算法的漏洞评分
- Dilithium and SPHINCS+, Tim Wambach 在Excel中（不使用宏macro）的讲解和演示