清华学者陈一镭新突破：格密码学面临颠覆？
清华学者陈一镭新突破：格密码学面临颠覆？
近日，清华大学交叉信息研究院助理教授陈一镭在eprint平台上发表了一篇关于破解格密码的量子算法论文，引发了全球计算机领域的广泛关注。这项研究如果被验证正确，不仅将推进量子计算进入新时代，还将对密码学、安全等领域产生深远的影响。
格密码学的基本原理
格密码学是后量子密码学的重要分支，其安全性基于格上困难问题，如最短向量问题（SVP）和最近向量问题（CVP），这些问题在经典计算机及量子计算机上均难以解决。格是由一组线性无关的向量生成的整数线性组合构成的点集，其基中向量的数量决定格的维度。
格密码的安全性依赖于以下难题：
- 最短向量问题（SVP）：找到格中最短的非零向量
- 最近向量问题（CVP）：给定一个目标点，找到距离该点最近的格点
- 学习同余问题（LWE）：从噪声数据中恢复隐藏结构，用于构建加密方案
格密码学利用上述难题设计加密算法，确保密钥交换、数字签名等操作的安全性。例如，通过构造复杂的格结构，使得攻击者难以从公开信息中推导出私钥或解密数据，从而实现对量子计算攻击的有效防御。
陈一镭的突破性研究
陈一镭教授的论文提出了多项式时间量子算法，用于求解具有特定多项式模数-噪声比的有误学习问题（LWE）。具体而言，论文展示了LWE的三种变体，最后一个变体在Def. 3.4中正式定义，本文提出的量子算法最终将解决这个问题。
为了开发求解LWE的量子算法，这篇论文主要引入了两种新技术：
- 在量子算法的设计中引入了具有复杂方差的高斯函数，特别是利用了复高斯函数离散傅里叶变换中的卡斯特波特征
- 使用带有复高斯窗口的窗口量子傅里叶变换，这使得能够结合时域和频域的信息
利用这些技术，陈一镭将LWE实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为LWE秘密和误差项的经典线性方程，最后利用高斯消元法求解线性方程组。
对后量子密码学的影响
这一突破如果被验证正确，将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响。因为多数选出的后量子密码方案都是基于Lattice Problems或LWE，陈一镭的工作无疑将使它们的安全性受到质疑。
这项工作在科学上的意义将是双层的：
- 这将是自30年前Peter Shor提出大数分解的量子算法以来，最重要的量子算法突破
- 这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响
目前，RSA（Rivest-Shamir-Adleman）算法是最为广泛采用的一种非对称加密技术，它允许信息发送者使用公开密钥进行信息加密，而只有持有相应私钥的接收者才能解密信息。这样的设计确保了即便信息在传输过程中被截获，也无法被未授权的第三方解密。密钥的安全性主要依赖于其长度，即所用密钥的位数。
基于RSA的密钥协议和密钥传送计划的批准状态。目前，美国国家标准与技术研究院（NIST）推荐的RSA密钥长度为2048位
RSA算法依赖于一个基于两个大素数乘积的复杂数学公式，该乘积构成了生成安全密钥的基础。RSA的安全性核心在于因式分解的计算难度，即确定两个原始质数的难度。对于足够大的数，即便是基础乘法运算也无法轻易实现其因式分解。
然而，这一切在1994年发生了变化，麻省理工学院的数学家Peter Shor提出了一种算法，解决了离散对数问题，从而为攻破RSA加密铺平了道路。离散对数问题本质上是一种计算简单但难以逆向的函数，如因式分解。在量子计算机上应用Shor算法，寻找RSA的因子由此可能变得可行。
瑞士苏黎世IBM研究院的安全研究小组经理Michael Osborne指出：“量子计算机擅长处理的问题类型非常有限。它们并不适合解决所谓的精确问题，因为它们的运行基于概率性。不幸的是，由于Shor算法本质上适合量子计算机处理问题的不同方式，因此得以从量子加速中受益。”
椭圆曲线加密（ECC）是另一种流行的非对称加密技术，基于椭圆曲线数学。ECC在速度和复杂性上都优于RSA，并构成了区块链安全的基础。然而，量子计算机的速度潜力同样可能威胁到ECC的安全性，因为它们的数学基础与Diffie-Hellman密钥交换相似。
另一方面，对称加密使用单一密钥进行加密和解密，其中最著名的例子是美国国家安全局批准的AES。基于哈希值的这些加密方法相对不易受到Shor算法的影响，但可能面临其他类型的攻击。
NIST的后量子密码学项目负责人、数学家Dustin Moody解释道：“总体而言，Shor算法几乎可以破解我们目前使用的所有公钥密码体系，包括RSA、Diffie-Hellman及其椭圆曲线版本。对于AES这样的对称算法以及SHA2和SHA3等哈希函数，我们不必更换算法，因为它们尚未被破解。在最坏的情况下，我们只需要使用稍长的密钥即可。”
广泛部署的经典密码系统及其针对已知最佳前量子和后量子攻击的安全级别摘要
去年，纽约大学教授Oded Regev的研究可能进一步加快了Shor算法的执行速度，引发了对现有加密方法安全性的进一步关注。
至今，RSA加密技术的挑战赛一直在搜寻最佳的安全措施，但发现许多看似有希望的解决方案实际上仍存在漏洞。
Flex Logix的副总裁Jayson Bethurem表示：“NIST最初收到了69项竞赛提案，经过5年的筛选，如今只剩下4个备选方案。最终的选定结果预期将在今年夏季公布。目前，仍有一些基于哈希的算法持续进展。在这场持久战中幸存下来的，往往是那些通过增加密钥长度来提高安全性的算法：这意味着数据路径变宽，相应地，因为数据路径的潜力巨大，所需时间来破解这些组合也会大大增加。”
后量子密码学（PQC）的基本类型
后量子密码学不同技术之间的比较
二维结构中基于格的加密（LBC）示例：秘密“对称基”（symmetrical base）为[𝑆0→,𝑆1→]；公开“非对称基”（asymmetrical base）为[P0→,P1→]。发送方利用[P0→,P1→]将信息勾勒到格点m，并添加误差向量，得到结果点[𝐶→]。与其他格点相比，[𝐶→]点与[m→]点相邻。因此，接收者可以利用完善的“秘密基”（secret-base）[𝑆0→,𝑆1→]，轻松检索[m→]（点向量）；而对于只拥有“扰乱基”（scrambled base）[P0→,P1→]的攻击者来说，这是一项艰巨的计算。对于量子安全方案来说，格的n维数必须远远大于2，就像这个例子一样
格密码系统使用称为“格”（lattice）的几何结构构建，并使用称为矩阵的数学阵列表示
似乎，既能有效抵抗已知的攻击方式，又能实际应用的加密方法，落在了基于格的算法上。
目前流行的基于格的算法是对旧技术的标准化。Rambu公Best司的贝斯特说：“有一种更新的密钥交换机制，称为CRYSTALS-Kyber算法，还有一种更新的数字签名算法，称为CRYSTALS-Dilithium算法。”
NIST的Moody也表示：“虽然基于晶格的加密技术无疑是最有前途的，但我们还是选择了四种算法进行标准化。”——不过，其中三种基于格。
格密码学的安全性根植于格问题的计算复杂性，比如寻找最短向量问题（SVP）和最近向量问题（CVP）。这些问题即便面对量子计算机的挑战，也被认为是难以直接解决的。与依赖于传统数学难题的加密技术相比，格密码学因其对量子攻击的天生抵抗力而成为后量子密码学的强有力候选。
格中的近似最短向量问题（Approximate Shortest Vector Problems in Lattices，简称Lattice Problems）及其等价问题——带错误的学习
学术界的反应
清华大学在官方公告中表示：“这项工作仍在同行评议中。如果被验证为正确，这一突破不仅会将量子计算推进到了一个新的时代，还将对密码学、安全等领域产生深远的影响。”
图灵奖得主、量子计算领域权威、清华交叉信息研究院院长姚期智对此给出了高度评价：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”
从论文致谢部分的内容来看，为理论计算机领域引入格密码和容错学习问题的纽约大学计算机科学家、2018年哥德尔奖得主Oded Regev本人应该已经看过论文手稿。
这篇论文提出的算法及分析极为新颖而深奥。回想Wiles 1994年解决费马大定理（Fermat"s Last Theorem），以及Perelman 2002年解决庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上专家们方能彻底认证其正确性。
陈一镭的工作，预料也需要数月时间才能完成验证认可，我们静候科学界对此工作的后续反应。
陈一镭简介
陈一镭是清华大学交叉信息学院助理教授，上海期智研究院PI。曾任VISA研究员。于2018年获得波士顿大学计算机博士学位，本