，而离散高斯采样问题可以很容易归约到 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, . [11] McGrew, D., Curcio, M., and S. Fluhrer, "Leighton-Micali Hash-Based Signatures", RFC 8554, DOI 10.17487/RFC8554, April 2019, . [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 共同撰写。 来源：金色财经lg...
北美站
