后量子密码学

后量子密码学开发公钥方案，其安全性基于即使对于量子计算机也难以解决的问题，旨在取代Shor算法可能破解的RSA和椭圆曲线密码学。

Definition

后量子密码学包括经典（非量子）密码算法，旨在通过依赖于尚无已知高效量子算法的问题，来确保其在面对配备大规模量子计算机的对手时仍能保持安全。

Scope

本主题涵盖量子威胁（Shor算法和Grover算法）、抗量子方案的主要家族——基于格、基于编码、基于哈希和多元——NIST标准化工作及其选定的算法（ML-KEM、ML-DSA、SLH-DSA），以及迁移问题，例如“先收集后解密”和混合部署。它不包括量子密码学本身（量子密钥分发），后者使用量子硬件而非经典算法。

Core questions

• 为什么量子计算机能破解RSA和椭圆曲线密码学，但对对称密码的影响不那么严重？
• 哪些难题（格、编码、哈希）被认为能抵抗量子攻击？
• NIST选择了哪些方案进行标准化，它们的权衡是什么？
• “先收集后解密”的威胁是什么，为什么它会带来紧迫性？
• 在迁移过程中，后量子方案和经典方案如何在混合部署中结合？

Key concepts

• Shor算法
• Grover算法
• 基于格的密码学（学习误差）
• 基于编码的密码学
• 基于哈希的签名
• ML-KEM (Kyber) 和 ML-DSA (Dilithium)
• 先收集后解密
• 密码敏捷性
• 混合密钥交换

Key theories

Shor算法带来的量子威胁

Shor量子算法能在多项式时间内分解整数和计算离散对数，从而破解RSA、Diffie-Hellman和椭圆曲线密码学；Grover算法仅能将暴力破解速度提高二次方，因此对称密钥只需加倍即可。

抗量子难题家族

后量子安全性寻求在格中的学习误差问题和最短向量问题、解码随机线性编码以及哈希函数的安全性等问题中实现——这些问题目前都没有已知的有效量子算法。

Mechanisms

基于格的方案，如ML-KEM（源自CRYSTALS-Kyber），其密钥封装基于模学习误差问题的难度，通过添加只有私钥才能移除的微小随机“误差”来实现。基于哈希的签名（SLH-DSA/SPHINCS+）完全基于哈希函数的安全性来构建签名。基于编码的方案将可解码结构隐藏在看似随机的线性编码中。迁移通常采用混合构造，结合经典方案和后量子方案，以确保只要其中一个方案安全，整体就安全。

Clinical relevance

迁移已在部署系统中进行：主要浏览器和TLS库已启用混合ML-KEM密钥交换，消息应用（Signal的PQXDH）和SSH已添加后量子握手，并且标准机构敦促组织清点密码学并规划过渡。“先收集后解密”的风险意味着需要长期保密的数据应立即受到量子攻击的保护。

Evidence & guidelines

NIST于2024年最终确定了其首批后量子标准：FIPS 203（ML-KEM）用于密钥封装，FIPS 204（ML-DSA）和FIPS 205（SLH-DSA）用于签名。NIST、NSA（CNSA 2.0）和国家机构的指导设定了迁移时间表。过渡期间的最佳实践倾向于采用结合后量子和经典算法的混合方案。

History

Peter Shor于1994年提出的算法表明量子计算机可以破解主流的公钥系统，从而促使人们寻找替代方案。基于格的密码学通过Ajtai的最坏情况硬度结果和Regev的学习误差问题（2005年）取得了进展。NIST于2016年启动了公开标准化流程；经过多轮筛选，它选择了CRYSTALS-Kyber等算法，并于2024年发布了首批标准（FIPS 203-205）。

Key figures

• Peter Shor
• Daniel J. Bernstein
• Tanja Lange
• Oded Regev
• Chris Peikert

Seminal works

• shor1997
• nist2024mlkem
• bernstein2017

Frequently asked questions

目前是否存在可以破解RSA的量子计算机？

没有。当前的量子计算机规模太小且噪声太大，无法在实际密钥大小上运行Shor算法。人们担心的是未来的机器，以及今天加密的数据一旦此类机器出现就可能被存储和解密的事实。

后量子密码学是否需要量子硬件？

不需要。后量子方案在普通的经典计算机上运行；它们只是依赖于即使对于量子攻击者也难以解决的数学问题。量子密钥分发确实使用量子硬件，但它是一种独立的方法。