追踪量子分解的计算成本

谷歌量子AI的使命是为无法解决的问题构建顶尖的量子计算技术。数十年来，量子计算与安全领域已知大规模量子计算机未来可能破解当前多数公钥密码算法（如RSA）。谷歌长期与美国国家标准技术研究院（NIST）及政府、产业界、学术界合作，开发并过渡至能抵抗量子计算攻击的后量子密码学（PQC）。

为规划从现有密码系统向PQC时代的过渡，必须准确评估未来可能破解当前密码算法的量子计算机规模与性能。近日我们发布的预印本研究表明，2048位RSA加密理论上可被拥有100万个噪声量子比特的量子计算机在一周内破解，较2019年估算的量子比特数量降低了20倍。值得注意的是，当前具备相关错误率的量子计算机仅拥有约100至1000个量子比特，且NIST近期已发布能抵御未来大型量子计算机的标准PQC算法。然而，新结果凸显了按NIST建议时间线迁移至这些标准的重要性。

因子分解资源估算持续下降

量子计算机通过Shor算法分解数字来破解RSA。自Peter Shor于1994年发布该算法以来，其所需量子比特数量的估算持续下降。例如2012年估算破解2048位RSA密钥需10亿物理量子比特，2019年基于相同物理假设（略优于谷歌量子AI当前量子计算机的错误率）降至2000万物理量子比特。

本次物理量子比特数量的减少源于两方面：更优算法和更佳纠错技术。算法层面的关键改进是计算近似模幂运算而非精确运算，Chevignard、Fouque和Schrottenloher于2024年发现的算法虽使操作量增加1000倍，但我们成功将开销降至2倍。纠错层面则通过添加第二层纠错将空闲逻辑量子比特的存储密度提升三倍，并结合2024年提出的"魔术态培育"技术减少特定量子操作的工作空间需求。

安全影响

NIST近期完成的PQC竞赛产生了首套PQC标准，这些算法可在密码学相关量子计算机建成前部署防御。针对非对称算法（如RSA和椭圆曲线Diffie-Hellman），需关注其用于传输加密（包括消息服务加密）和数字签名（如网站身份验证）的场景。对于非对称加密，“现在存储、以后解密"攻击使得向PQC迁移更为紧迫，谷歌已在Chrome和内部通信中部署标准版ML-KEM。

签名迁移更为复杂，特别是当公钥固定在硬件中时。由于签名密钥使用场景多样且生命周期长于临时加密密钥，其替换难度更大，更易成为量子计算资源受限时的攻击目标。NIST内部报告草案建议易受攻击系统在2030年后弃用、2035年后禁用，我们的研究强调了遵循该时间线的重要性。

延伸阅读：谷歌后量子密码资源页