格问题的量子算法

清华大学陈一镭教授的一篇突破性研究论文在密码学界引起了震动。这篇题为 “网格问题的量子算法 “的论文描述了一种解决带错误学习（LWE）问题的高效量子算法，该问题是像 Abelian 所使用的那种基于网格的密码系统的基础。

方法论： 陈教授的新方法利用了在量子算法设计中运用具有复杂方差的高斯函数，利用这些函数离散傅里叶变换中的喀斯特波特征。

窗口量子傅里叶变换与复高斯窗口，合并了时域和频域的信息。该技术在第 6–7 页的 “我们解决 LWE 的算法概述 “部分有所描述。

将 LWE 实例转换为具有纯虚高斯振幅的量子态，并将其转换为与 LWE 的秘密和误差项相关联的经典线性方程。

使用高斯消元法求解这些方程并恢复 LWE 秘密。

结果：陈教授的研究成果包括 — —

·一种多项式时间量子算法，可解决某些多项式模数-噪声比的 LWE 问题。

设 n、m、q∈N，α∈（0，1），使得 m≥Ω(n log q)，q∈˜Ω((αq)⁴ m²)。有一种量子算法可以在 poly(m, log q, αq) 时间内求解 LWE_n,m,q,U(Z_q),D_Z,αq。

·在Õ(n⁴.5)的近似因子内解决所有 n 维网格的 GapSVP 和 SIVP 的多项式时间量子算法。

在 γ∈˜O(n⁴.5) 时，存在求解所有 n 维格的 SIVP_γ 和 GapSVP_γ 的多(n)时间量子算法”。这个推论提出了求解所有 n 维格的 GapSVP 和 SIVP 的多项式时间量子算法，其近似因子为 Õ(n⁴.5)，这是定理 1.6 中主要结果的直接后果。

对阿贝尔安全性的影响

基于格的密码学一直被认为是后量子安全的理想候选技术，因为它被认为可以抵御经典计算机和量子计算机的攻击。特别是 LWE 问题，它已被广泛用于构建各种密码基元，包括 NIST 在其后量子密码学 (PQC) 项目中选定的标准化基元。NIST 目前将基于格的 Crystals-Kyber 和 Crystals-Dilithium 作为 “量子安全 “的标准。

陈教授的算法如果被证明是正确的，将意味着基于格的密码系统并不像以前认为的那样具有量子抗性。然而，值得注意的是，高效量子算法的存在并不一定意味着这些密码系统在实践中可以被破解。

首先，尽管苹果等科技巨头已经使用量子安全机制实现了 PQ3 协议来保护 iMessages，而且美国国家安全局报告称，实用的量子计算工具距离劳动力使用仅有 3 到 5 年左右的时间，但能够破解椭圆曲线（广泛应用于区块链技术，但已知易受量子攻击）的通用量子计算机距离应用于现实生活仍有 5 到 10 年的时间，但该算法假设存在通用量子计算机，而这距离实现仍有数年之遥。

其次，即使陈教授的算法在理论上是正确的，其证明也需要时间才能得到密码学界的彻底验证。如果该算法经得起检验，可能会促使 NIST 重新评估其 PQC 标准化流程，并考虑采用其他加密系统。

尽管取得了这些进展，但重要的是要明白，Abelian 使用的基于格的密码系统的量子抗性仍然大大高于椭圆曲线密码系统。陈教授自己也承认，他的算法并没有直接破坏 Kyber 和 Dilithium 等方案中使用的参数，这些方案都是 NIST PQC 竞赛的入围方案。

从这个角度来看，如果需要一台拥有 10 万量子比特的量子计算机才能破解椭圆曲线密码系统，那么需要一台拥有超过 1,000,000,000 量子比特的机器才能破解 Abelian 使用的基于格的方案。这种规模上的差异凸显了基于格的加密技术的持久安全优势，即使面对理论上的进步也是如此。目前，IBM 的量子鹰处理器（Quantum Eagle Processor）可以部署 127 量子比特，而日本的理化学研究所（RIKEN）和富士通（Fujitsu）技术中心已经合作开发出一种新型 64 量子比特超导量子计算机。

Abelian 研究团队正积极关注陈教授工作的相关进展，并将根据事态发展提供最新信息和见解。我们将继续致力于确保我们平台的安全性和可靠性，并在必要时调整我们的加密原语，以保持对用户的最高保护标准。

总之，虽然陈教授的研究是一项重大的理论突破，但它不会对阿贝尔链或其他基于格的密码系统的安全性构成直接的实际威胁。随着量子计算领域不断向动态方向发展，我们将不懈努力，保持领先地位，为我们的用户提供最安全、最先进的加密解决方案。

阿贝尔链基金会欢迎所有关于技术发展和即将发生的变化的反馈意见。点击下方链接，访问我们的社交媒体和社区渠道参与讨论，留下你的宝贵意见

Twitter | Telegram | Discord | YouTube | Linkedin

‍