solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看 4343 次
基于格的后量子算法可能无法抵御量子计算机
美国国家标准技术局(NIST)在 2022 年宣布了后量子加密和签名算法竞赛的首批获胜者,一共四种,其中三种是基于格的算法,还有一种是基于哈希的算法,其中基于格的算法包括了 Kyber 和 CRYSTALS-Dilithium。后量子加密流行基于格的算法是因为寻找格上的最短向量被认为是计算机领域最困难的问题之一,至今没有经典或量子算法能在多项式时间内解决该问题。清华大学助理教授、上海期智研究院的陈一镭于 4 月 10 日发表的一篇尚未通过同行评议的预印本《Quantum Algorithms for Lattice Problems》在加密学社区引发了热议,论文提出了一种多项式时间量子算法,能有效解决有特定参数的格的“最短独立向量问题”。如果成立,将降低量子计算机破解特殊格问题的难度。陈的算法并不立刻适用于 Kyber 和 Dilithium 等 NIST 标准化的格算法,其确切复杂性也不清楚,可能未必能在量子计算机上运行。但如果得以改进,那么后量子加密可能将要淘汰基于格的方案,需要重新研究新的算法去抵御量子计算机。
https://sqz.ac.cn/password-50
https://eprint.iacr.org/2024/555
https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/
https://sqz.ac.cn/password-50
https://eprint.iacr.org/2024/555
https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/