格密码的量子危机？一文带你解析格密码学术风波

文章转载来源： ZAN Team

区块链的量子安全威胁以及应对

2024 年 3 月 10 日，以太坊联合创始人 Vitalik Buterin 在以太坊研究论坛（ethresear.ch）发布最新文章《How to hard-fork to save most user's funds in a quantum emergency》[1]，文中表示：以太坊生态系统面临的量子计算攻击威胁，可以通过恢复性分叉策略和抗量子密码技术来保护用户资金安全。

对于区块链来说，量子安全威胁到底是什么？

量子计算[2]作为利用量子力学调控量子信息单元进行计算的新型计算模式，在 20 世纪 80 年代被提出，在其概念提出后的十年内，量子计算机也只是停留在抽象理论阶段。直到 20 世纪 90 年代中期的两个量子算法：Shor 算法[3]（多项式时间内解决大数分解及离散对数困难问题）和Grover算法[4]（针对非结构化数据的穷举搜索问题提供平方加速）的提出，使得量子计算跳出抽象理论阶段，转而进入到物理载体研发的新阶段，也就是目前所说的量子计算机。下图展示了从 1998 年到 2026 年量子计算机的物理量子比特发展路线图：

量子计算不是万能的，它并非能解决所有计算问题。目前可在模拟（模拟自然界发生的过程，适用于化学与生物工程）、破译（打破大部分传统密码体系，适用于网络安全）、优化（寻找可行选项中的最优解，适用于金融、供应链）等特定领域问题上发挥其计算优越性。

区块链目前得到广泛应用来自于它给不同诉求方间的协作带来新的信任基础，而这种信任基础建立在底层密码学所提供的安全性保障之上：

• 可信身份与交易确权：基于非对称公私钥对建立用户可信身份，统一管理身份信息。通过数字签名实现数字资产的确权，有效签名的私钥持有者实际拥有资产所有权。

• 核心共识和运行安全：基于哈希函数、门限签名、可验证随机函数等现代密码技术构建共识机制，保障共识机制使用安全。

• 隐私保护与安全共享：基于零知识证明、安全多方计算、全同态等富功能密码技术构建隐私保护方案，实现区块链上数据的安全共享。

• 可控监管与合规应用：集成部署环签名、同态密码方案、隐地址和秘密共享等密码技术，确保区块链交易的安全监管。

这其中涉及到公钥密码的用法可粗略分为：链上交易防篡改使用的数字签名机制，以及节点间通信使用的安全传输协议。受 Shor 算法的影响，上述公钥密码在使用上的安全性无法得到有效保障。在考虑专用密码破译量子计算机大规模应用所需时间的同时，还需考虑存储在区块链上的数据需要保存多长时间以及现有区块链系统升级到量子安全级别的时间。如果后两者相加的时间和大于前者，那么区块链上的数据就会受到量子计算带来的严重安全威胁。

考虑到量子计算飞速发展带来的算力不断提升的现状，目前可以有效应对安全风险的主要有两种技术途径：

1. 不借助物理设备的基于新型数学难题的后量子密码[5]技术路线；

2. 借助专用物理设备的基于物理原理的量子密码[6]技术路线。

综合考虑落地实施验证等多种因素，为确保区块链长期演进下的安全性保证，在兼容现有密码安全的前提下，可考虑通过后量子密码迁移将区块链提前部署升级到量子安全级别。理想情况下，将现有区块链使用的公钥密码算法升级为量子安全的后量子密码算法，应尽可能满足以下特点：

• 密钥小且签名短：区块链上的每笔交易都会包含签名信息，而验证任意一笔交易的公钥也存储在链上。若密钥以及签名尺寸过大，都将大大加剧区块链的存储成本以及通信开销；

• 计算效率高：区块链运行时每一时间段可处理的交易数量很大程度上与算法的运行时间有关，特别是签名验签算法。算法更快的计算效率可以更好地支持高性能的区块链应用。

后量子密码发展现状

后量子密码，一句话概括就是能够抵抗量子计算机对现有密码算法攻击的第一代密码算法：

• 面向公钥密码体系；

• 依赖新型数学问题；

• 不需要专用设备支持；

• 经典计算以及量子计算条件下安全；

目前主流的构造技术路线有五种，如下图所示，从左到右分别是格、编码、多变量、哈希以及同源：

1. 格：基于格上的困难问题。

2. 编码：基于解码的困难性。

3. 多变量：基于有限域上多元二次多项式组的难解性。

4. 哈希：基于哈希函数的抗碰撞性。

5. 同源：基于超奇异椭圆曲线的伪随机游走。

新一代密码算法然会涉及到标准密码体系的建立。关于后量子密码标准最值得关注的则是：美国国家标准技术研究所（NTST）的后量子密码标准化项目[7]，从 2016 年启动到现在已基本进入后量子密码标准化制定的尾声。回顾这接近十年的标准化时间线，NIST 在：

2022 年 7 月 5 日，正式官宣四个后量子密码标准候选算法[8]：

• 公钥加密/密钥封装：CRYSTALS-KYBER；

• 数字签名：CRYSTALS-Dilithium、FALCON；SPHINCS+；

这其中，CRYSTALS-KYBER、CRYSTALS-Dilithium、FALCON 均为格密码算法，但三者的安全性基础有所区别，KYBER 基于模格的 MLWE 困难问题，Dilithium 基于模格的 MLWE 和 MSIS 困难问题，FALCON 则基于 NTRU 格的 SIS 困难问题；除此之外，SPHINCS+ 是无状态哈希签名算法。

2023 年 8 月 24 日，已将 CRYSTALS-KYBER、CRYSTALS-Dilithium、SPHINCS+分别形成FIPS203、FIPS 204、FIPS205 标准草案 [9]，FALCON 标准草案也将在 2024 年公布。

不难看出目前 NIST 选择的标准算法大多基于格密码的技术路线。但是 NIST 并没有把鸡蛋放在同一个篮子中，他们也在积极需要除了格构造以外的多种选择：2022 年公布四个标准算法的同时，也宣布启动了第四轮后量子密码标准算评估工作，这一轮则关注于公钥加密/密钥封装算法，入选的算法并没有基于格构造。此外，还发起新一轮数字签名算法的征集，此轮征集独立于第四轮评估独立进行，旨在丰富后量子签名算法组合，所以更关注于算法构造上不同与现有的基于结构格，且算法签名尺寸小、验证速度快的新提案。

除了 NIST 标准外，国际互联网标准化组织 IETF 在 2018 年和 2019 年分别标准化有状态哈希签名算法 XMSS 为 RFC 8391[10]、LMS 为 RFC 8554[11] 且被 NIST 接受。

破解格密码的量子算法

2024 年 4 月 10 日，陈一镭老师在 eprint 上的文章《Quantum Algorithms for Lattice Problems》[12] 引起了学术界的轰动。论文中给出了一种多项式时间求解格上困难问题的量子算法，该算法对很多基于格困难问题的密码方案有着较大冲击，可导致很多算法不再具备抗量子计算机攻击的能力，例如，目前广泛使用的基于 LWE 假设的同态加密算法。论文中算法的正确性暂未可知。

LWE 问题的困难性由 Oded Regev 在论文《On lattices, learning with errors, random linear codes, and cryptography》[13]中给出了严格的论证，具体地说，作者在论文中将 LWE 问题的困难性归约到格上的离散高斯采样问题，而离散高斯采样问题可以很容易归约到 GapSVP, SIVP 等经典问题（当然，每个具体问题都是有其具体参数的，这里忽略），这说明 LWE 问题要比这些经典的格问题还要困难。在 LWE 问题的困难性有了严格的归约后，由于其结构简单，一大批基于 LWE 的密码方案也随之而来，涵盖（同态）加密，签名，密钥交换等基础密码原语，以及基于身份加密，属性加密等高级密码原语等。其中，在业界使用较多的主要集中在全同态加密和上面所提到的 NIST 公布的后量子标准算法（KYBER， Dilithium等）。

总结

该论文公开后，对学术界造成了很大的轰动，引起很多专业人士的讨论。但由于论文的理解难度极大，全世界可能也就不到 5 位学者可以完全理解论文的内容，可能需要 1-2 年的时间才能完全验证论文的正确性。目前一些论坛、公众号、知乎等平台也有很多人发表了一些相关见解，大家都是在分析如果论文中的算法是正确的，会带来哪些影响，至于论文算法的正确性问题，还没人能下定结论。其中，著名密码学家 N. P. Smart 发表了博客文章《Implications of the Proposed Quantum Attack on LWE》[14]，详细介绍了此攻击的影响和一些观点，总结如下：

• 这篇论文目前尚未经过同行评审，即使被验证是正确的，也要依赖于量子计算机，因此只要量子计算机还未问世，对目前在使用的密码方案均无影响。

• 按照论文中给出的结果：仍无法攻破此前 NIST 给出的标准化算法 Kyber, Dilithium，但 NIST 可能会重新评估这些算法的参数。

• 对于常用的 RLWE 同态加密算法，如 BFV/CKKS/BGV，这些算法是在这篇论文的攻击能力之内的。不过，不管从是学术界还是工业界的视角，同态加密技术的“同态性”比其“抗量子性”更具吸引力，很少人会为追求“抗量子性”而使用 RLWE 同态加密算法，就像基于椭圆曲线的密码方案依赖于离散对数困难问题，而求解该问题的量子算法很早就被提出了，但学术界，工业界仍然在研究、使用这些方案。

最新消息：陈老师论文计算存在问题，格密码警报暂时解除。

[1] https://ethresear.ch/t/how-to-hard-fork-to-save-most-users-funds-in-a-quantum-emergency/18901/9

[2] Benioff P. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines[J]. Journal of statistical physics, 1980, 22: 563-591.

[3] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proceedings 35th annual symposium on foundations of computer science. Ieee, 1994: 124-134.

[4] Grover L K. A fast quantum mechanical algorithm for database search[C]//Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996: 212-219.

[5] Bernstein, D.J. (2009). Introduction to post-quantum cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg.

[6] Gisin N, Ribordy G, Tittel W, et al. Quantum cryptography[J]. Reviews of modern physics, 2002, 74(1): 145.

[7]https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization

[8]https://csrc.nist.gov/News/2022/pqc-candidates-to-be-standardized-and-round-4

[9]https://csrc.nist.gov/News/2023/three-draft-fips-for-post-quantum-cryptography

[10] Huelsing, A., Butin, D., Gazdag, S., Rijneveld, J., and A. Mohaisen, "XMSS: eXtended Merkle Signature Scheme", RFC 8391, DOI 10.17487/RFC8391, May 2018, <https://www.rfc-editor.org/info/rfc8391>.

[11] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, April 2019, <https://www.rfc-editor.org/info/rfc8554>.

[12] Chen Y. Quantum Algorithms for Lattice Problems[J]. Cryptology ePrint Archive, 2024.

[13] Regev O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM (JACM), 2009, 56(6): 1-40.

[14]https://nigelsmart.github.io/LWE.html

本文由 ZAN Team（X 账号 @zan_team）的 Dongni 和 Jiaxing 共同撰写。