后量子密码算法全面比较：基于格、哈希、编码与多变量的方案

后量子密码学（post-quantum cryptography）（PQC）指的是，即使面对配备强大量子计算机（quantum computers）的对手，也旨在保持安全的密码算法。经典密码学通常依赖整数分解或离散对数问题，而 PQC 系统基于一些被认为对经典计算机和量子计算机都难以求解的数学问题。其目标不仅是理论上的抵抗能力，也包括在互联网、金融系统，以及区块链等去中心化技术的现实基础设施中部署。

在美国国家标准与技术研究院（NIST）等机构的引领下，全球密码学界多年来一直在评估能够取代或补充现有公钥系统的候选算法。过程中出现了多个不同的 PQC 类别，其中最重要的包括基于格（lattice-based）、基于哈希（hash-based）、基于编码（code-based）和多变量多项式（multivariate polynomial）密码学。它们解决的是同一个问题，即抵御量子攻击，但采用的数学构造截然不同。有些方案提供较强的安全证明，却需要很大的密钥；另一些签名紧凑，但实现较复杂。

怎样的密码算法才具有量子抗性？

当支撑密码算法安全性的数学问题，即使借助量子计算机，在计算上仍难以求解时，通常认为该算法具有量子抗性（quantum-resistant）。

许多已广泛部署的公钥密码系统，包括 RSA 和椭圆曲线密码学，都依赖整数分解、离散对数等数论问题。经典计算机很难解决这些问题，但肖尔算法（Shor’s algorithm）等量子算法能够高效求解，使传统密码系统在未来量子计算环境中面临风险。

后量子密码算法转而依赖其他数学问题来应对这一弱点，目前尚无已知高效量子算法能解决这些问题。它们往往涉及复杂代数结构、高维几何空间或组合搜索问题，看起来能抵抗经典与量子计算技术。

例如，基于格的密码学依赖高维格中几何问题的求解难度，尤其是最短向量问题（Shortest Vector Problem，SVP）。基于哈希的密码学依靠密码学哈希函数的基本性质，包括抗原像性和抗碰撞性。基于编码的密码学建立在随机线性纠错码的解码难度之上，多变量多项式密码学则依赖求解有限域上非线性多项式方程组的计算复杂性。

这些数学基础的吸引力在于，目前没有已知量子算法能够高效解决相应问题。尽管量子计算机能显著加速某些计算，尤其是与数论相关的计算，但在这些替代问题领域，其优势似乎要小得多。

不过，密码学安全并非决定系统可行性的唯一因素。实际部署还需认真考虑计算效率、内存需求、密钥大小、签名大小、网络带宽消耗和实现复杂性等因素。一种算法即使理论安全性很强，若需要极大的密钥或过多计算资源，也可能难以广泛采用。

四类主要 PQC 算法展示了取得这种平衡的不同方式。每一类都体现一种独特的数学思路，并在安全保证、计算效率和实现可行性之间作出不同取舍。

基于格的密码学

基于格的密码学（lattice-based cryptography）已成为 PQC 中最有前景、研究最广泛的方向之一。从数学上说，格是多维空间中由基向量的线性组合形成的规则点阵。在二维或三维中，格看起来相对简单；但扩展到数百乃至数千维后，结构就会变得极其复杂，由此产生的计算难题构成了格密码安全性的基础。

基于格的密码方案通常依赖在这些高维空间内求解几何优化问题的难度。最著名的问题之一是最短向量问题（SVP），要求找出格中最短的非零向量。问题定义虽然简单，但随着格维度增加，计算难度会迅速上升。

可以把基于格的密码学想象为：在由完美重复网格线构成的巨大多维迷宫中，寻找最短路径。如果知道布局（私钥），问题尚可处理；但如果没有地图就被放进去，连找出最短的移动方向都极其困难，尤其当迷宫扩展到数百维时。

格密码使用的另一项基本问题是带误差学习（Learning With Errors，LWE）问题。在这个问题中，攻击者试图从一组刻意加入少量随机噪声的线性方程中恢复秘密信息。不知道秘密参数时，求解这些带噪声方程在计算上不可行。

由于 SVP 和 LWE 看起来都能抵抗已知量子算法，基于格的密码学已成为现代后量子密码学研究的核心方向。

这一框架下已发展出多种重要密码方案。其中，ML-KEM（CRYSTALS-Kyber）和 ML-DSA（CRYSTALS-Dilithium）被 NIST 分别选为加密和数字签名的标准后量子算法。另一项有影响力的系统是 NTRU，它是一种比许多现代 PQC 构造更早出现的格密码方案，数十年来经历了广泛的安全分析。

基于格的密码学具有多项实际优势，包括较高的计算效率、对不同密码学原语的灵活支持，以及扎实的理论安全基础。此外，格数学还支持全同态加密（fully homomorphic encryption）等先进技术，让计算直接在加密数据上进行，而不披露底层信息。

尽管如此，格密码系统仍有一些实现挑战。其密钥通常比经典公钥密码系统的密钥更大，不过对于多数现代计算环境而言，仍在可处理范围内。

基于哈希的密码学

基于哈希的密码学（hash-based cryptography）是后量子数字签名中最早出现、概念最简单的方向之一。这些方案不依赖复杂代数结构，而是直接根据密码学哈希函数的安全性质构建安全数字签名。设计良好的哈希函数仍能抵抗量子攻击，除了格罗弗算法（Grover’s algorithm）带来的平方级加速，因此基于哈希的密码学提供了特别强的安全保证。

密码学哈希函数把任意长度的输入转换为固定长度的输出，并保有几项关键安全性质：抗原像性（preimage resistance）防止攻击者从哈希输出重建输入；抗第二原像性（second-preimage resistance）防止找到产生同一哈希值的替代输入；抗碰撞性（collision resistance）防止找到两个产生相同哈希输出的不同输入。

基于哈希的密码学，就像把消息封在带有唯一指纹、防篡改的信封中。你很容易验证信封没有被打开或修改，但仅凭指纹重建原始消息，或找到两条指纹相同的消息，在实践中几乎不可能。

基于哈希的签名方案利用这些性质构建数字签名，而不依赖易受量子计算攻击的数论假设。

这类方案最早的例子之一，是 20 世纪 70 年代末提出的 Lamport 签名方案。Lamport 签名虽然具有极强安全保证，却有一个显著局限：每个密钥对只能签署一条消息。

为克服这一限制，研究人员开发了基于 Merkle 树的更复杂构造，将许多一次性签名密钥组合为分层结构，使单个公钥能够支持多次签名。

SPHINCS+ 等现代哈希签名方案进一步扩展了这一理念，构建无状态签名系统，无须跟踪哪些密钥已经使用。这种无状态设计简化了实现，同时维持强安全保证。

基于哈希的密码学的一项主要优势，是其保守的安全模型。这类系统几乎完全依赖已经得到充分理解的密码学哈希函数性质，因此底层安全假设相对较少。

但与其他后量子密码算法相比，基于哈希的签名方案往往生成较大的签名。在某些实现中，签名大小可达数十千字节，这可能给带宽受限或存储有限的环境带来挑战。

基于编码的密码学

基于编码的密码学（code-based cryptography）是最早的 PQC 形式之一，可以追溯到 20 世纪 70 年代末。这类系统的安全性建立在随机线性纠错码解码的计算难度之上，这一问题四十多年来一直抵御着高效攻击。

纠错码（error-correcting codes）广泛用于通信系统，检测和纠正噪声或干扰造成的传输错误。基于编码的密码学借用了这一概念，刻意隐藏精心选择的纠错码的结构。

可以想象，把一条消息藏进一句被严重打乱的话中，只有知道原始语法规则的人，才能纠正错误并正确阅读。对其他人，它看起来像随机噪声；不知道隐藏规则，就很难推断原意。

这一理念最著名的实现是 1978 年首次提出的 McEliece 密码系统。系统通过对结构化的码施加随机变换来构造公钥，使其看起来与随机线性码无法区分；私钥则保留隐藏结构，让合法用户能够高效解码加密消息。

对于不知道隐藏结构的攻击者，破解系统需要解决随机线性码的一般解码问题，而这被广泛认为在计算上不可行。

基于编码的密码学最吸引人的特点之一，是其悠久的安全分析历史。经过数十年的密码分析研究（cryptanalytic research），参数设置合理的 McEliece 系统仍能抵抗实际攻击。

但基于编码的密码算法的主要缺点，是公钥极大。在某些实现中，公钥可达数百千字节，使其难以部署到存储空间或网络带宽有限的环境中。

多变量多项式密码学

多变量多项式密码学（multivariate polynomial cryptography）是后量子密码算法中的另一重要方向。这类方案依赖求解有限域上非线性多变量多项式方程组的计算难度。

从计算复杂性的角度看，求解这类方程组在一般情况下是已知的 NP-hard 问题。随着变量和方程数量增加，求解所需计算资源呈指数增长，即使采用适当参数，经典计算机和量子计算机也都难以实际通过暴力穷举求解。

多变量密码方案的公钥通常由一组二次多项式方程组成，私钥则包含精心设计的变换，让合法用户能够高效求出方程的解。

对于无法获得私有变换的外部观察者，公开系统看起来是一组随机的非线性方程，必须同时求解，计算难度很高。

这种方式就像给你一大组相互纠缠、包含许多未知数的方程，要求全部一起解出。如果拥有秘密捷径（私钥），就很容易；没有它，就只能尝试无数种组合，像在没有任何提示的情况下解决一个巨型谜题。

多变量密码学最有吸引力的特点之一，是可能实现极快的签名生成和验证。由于底层计算主要依赖有限域上相对简单的代数运算，这类系统在某些计算环境中能达到很高性能。

不过，多变量密码学历史上曾遭遇安全挑战。研究人员发现了隐藏的代数结构，使攻击者能够简化多项式系统，导致若干早期提案后来被破解。

因此，现代多变量密码学研究格外重视审慎的方案设计和严格安全分析，以消除可被利用的结构模式。

主要后量子密码学类别比较

比较四类主要后量子密码学方案可以看出，没有一种在所有指标上都占优。每一类都有独特优势，也有各自的实际取舍。

基于格的密码学，将扎实的安全基础、计算效率和灵活性较为均衡地结合起来。这些算法既支持加密，也支持数字签名，同时保持适中的密钥大小和较高性能。

基于哈希的密码学安全性主要依靠密码学哈希函数已确立的性质，因此提供特别强的安全保证。但许多哈希方案的签名相对较大，可能限制其在某些网络环境中的应用。

基于编码的密码学受益于极为悠久的安全分析历史，McEliece 密码系统四十多年来仍未被破解。不过，这类系统所需的巨大公钥，也带来了显著部署挑战。

多变量多项式密码学提供极快的数字签名操作，但必须回应历史上隐藏代数漏洞引发的担忧。

因此，许多密码学专家认为，未来的安全数字基础设施将采用多样化的后量子密码算法生态，而非单一通用方案。并行部署多种密码学方法，能够在某一算法类别日后暴露漏洞时，增加一层抵御风险的能力。

常见问题

什么是后量子密码学？

后量子密码学指旨在抵御量子计算机攻击的密码算法，量子计算机可能破解 RSA、ECC 等传统加密系统。

NIST 选择了哪些后量子算法？

在评估全球研究人员提交的数十种候选算法后，NIST 于 2024 年 8 月 13 日公布了首批正式标准化的后量子密码算法，包括 ML-KEM（源于 Kyber）、ML-DSA（源于 Dilithium）和 SLH-DSA（基于 SPHINCS+）。

结语

后量子密码学的发展带来了多类前景可期的算法。它们基于不同的数学原理，在保护数字系统免受未来量子计算威胁方面各有优势。

基于格的密码学凭借扎实的理论基础、高效性能，以及对多种密码学应用的支持，目前在实际部署中占据领先地位。基于哈希的密码学依靠密码学哈希函数，提供极强安全保证；基于编码的密码学则积累了数十年抵御密码分析攻击的实证。多变量多项式密码学虽然仍在发展，却继续为高性能数字签名系统提供颇具吸引力的可能。

密码学的未来很可能不会收敛到一个通用算法，而是形成多样化的抗量子密码技术生态，分别适应不同的应用、性能要求和安全模型。随着量子计算技术不断进步，这些后量子密码算法在维护全球数字基础设施安全与完整性方面，将发挥越来越核心的作用。