清华叉院教授扔量子密码学论文炸弹！业界颤动，但算法被发现bug
【新智元导读】前段时间，由清华叉院助理教授陈一镭提出的全新「破解格暗码的量子算法」，一经宣布便引发了业界颤动。但是就在最近，要害的第9步被发现有无法修正的bug，导致算法无法建立。
一直以来，处理格上的近似最短向量问题（Lattice Problems）以及带过错学习问题（LWE），都是核算机范畴的经典算法难题。
尤其是在科学界看来，它们远远超出了传统核算机的才能规模。
那么，量子核算机有望能破解Lattice Problems以及LWE吗？
前段时间，来自清华大学穿插信息研讨院陈一镭助理教授，便针对这些问题提出了一种全新的「破解格暗码的量子算法」。
预印本论文一经宣布，便在整个核算机界引起了巨大的颤动。
如闻名暗码学家N. P. Smart，就在第一时间发了篇博客文章，具体评论了论文所带来的影响。
文章地址：https://nigelsmart.github.io/LWE.html
具体来说，陈教授提出的这种多项式时间量子算法，首要用于求解具有特定多项式模数-噪声比的「带过错学习问题」（LWE）。
通过结合Regev所提出的从网格问题到LWE的复原，便能够取得多项式时间量子算法，并能够在的近似因子内求解一切n维网格的决议计划最短向量问题（GapSVP）和最短独立向量问题（SIVP）。
在此之前，还没有已知的多项式乃至亚指数时间量子算法能够在任何多项式近似因子内求解一切网格的GapSVP 或SIVP。
论文地址：https://eprint.iacr.org/2024/555.pdf
为了开发求解LWE的量子算法，作者提出了两种新的技能：
首要，在量子算法的规划中引进具有杂乱方差的高斯函数。特别是，运用复高斯函数离散傅里叶变换中的卡斯特波特征。
其次，运用带有复高斯窗口的窗口量子傅里叶变换，然后能够结合时域和频域的信息。
基于此，便能够先将LWE实例转换为具有纯虚高斯振幅的量子态，然后将纯虚高斯态转换为LWE隐秘和差错项的经典线性方程，终究运用高斯消元法求解线性方程组。
但惋惜的是，Hongxun Wu（UC伯克利博二学生）和Thomas Vidick（量子范畴专家）发现，算法的第9步实际上存在一个尚不能修正的bug。
也就是说，这个通过多项式模数-噪声比，来求解LWE的多项式时间量子算法，无法建立了。
对此作者表明，期望像复高斯（Complex Gaussian）和窗口QFT（windowed QFT）这样的主意，会在量子核算中找到其他运用，而LWE问题或许会将有其他处理办法。
9大要害过程
首要进行参数的设置，之后需求运转一个由九个过程组成的量子子程序，共运转O(n)次。
论文中最要害的，是一个需求调用O(n)次的，由九个过程组成的量子子程序。
其间，每次调用都会得到一个经典线性方程，其随机系数是中最短的向量（与LWE隐秘向量和过错向量相关）。
在调用完O(n)次之后，便能够得到一个全秩线性方程组，并通过高斯消元法核算出LWE隐秘和过错项。
过程 1：在上进行叠加，并运用复高斯窗口
过程 2：在|φ1⟩上运用
过程 3：在|φ2⟩上运用复高斯窗口，得到|φ3⟩和z′
过程 4：在|φ3⟩上运用
过程 5：将|φ4⟩分割成高阶|h′⟩和低阶|h′′⟩，然后对|h′′⟩进行丈量
过程 6：在|φ5⟩上运用
过程 7：提取|φ6⟩的中心，得到纯虚高斯状况|φ7⟩
过程 8：提取并保存|φ8⟩=|φ7⟩
在过程8中，作者首要进行四次运算（可逆），然后进行部分丈量，终究将四次运算回转。也就是说，需求在不折叠或修正|φ7⟩的情况下，学习。
过程 9：从和|φ8⟩中提取隐秘的线性方程
第9步的方针是将|φ8⟩转换为隐秘的经典线性方程，并终究得到主Lemma（3.8）的证明。
其间，过程9运用过程8中取得的信息，以及刺进LWE隐秘中的已知项的κ-1坐标。
这里，bug来了：|φ8.f⟩的振幅不满足M2周期性。
或许，另一种解说是：|φ8.f⟩包括p1...pκ向量。通过域扩展后，本应得到p1p2...pκ-p2...pκ向量，但依照|φ8.g⟩的写法，它只包括p1...pκ向量。因而|φ8.g⟩的表达式是过错的。
作者介绍
陈一镭是清华大学穿插信息学院（IIIS）的一名助理教授。
此前，他在波士顿大学取得博士学位，指导老师是Ran Canetti教授和Leonid Reyzin教授。并在上海交通大学取得学士学位。在那里，一个风趣的问题引导他走上了科研之路。
他的研讨爱好是暗码学，特别是在伪随机，格暗码，数论，和量子核算等方向。
首要效果有：规划了格问题的量子算法，建立了多线性映射和代码混杂在格问题上安全完成的根底，提出了证明Fiat-Shamir假定的办法，以及提出了一个不可逆群的结构。
相关文章
你最近发送的电子邮件很或许是运用一种经典加密办法进行加密的，这种办法根据这样一个主意：即使是最快的核算机也无法高效地将一个巨大的数字分化成因数。
可是，量子核算机则有潜力能够快速破解传统核算机或许永久无法处理的杂乱暗码体系。这或许会根据 1994 年由彼得·肖尔（现为麻省理工学院教授）提出的量子分化算法完结。
虽然曩昔 30 年来研讨人员取得了巨大发展，但科学家们仍未制作出满足强壮的量子核算机来运转肖尔的算法。
一些研讨人员正在尽力制作更大的量子核算机，而另一些研讨人员则测验改善肖尔的算法，以便它能够在较小的量子电路上运转。大约一年前，纽约大学核算机科学家 Oded Regev 提出了一项严重理论改善。他的算法运转速度更快，但需求更多内存。
根据这些研讨成果，麻省理工学院的研讨人员提出了一种结合了 Regev 算法速度和肖尔算法内存功率的折中办法。这个新算法与 Regev 的算法相同快，但需求更少的量子构件（称为量子比特），而且对量子噪声的容忍度更高，这或许使其在实践中更简略完结。
从长远来看，这种新算法或许为开发能够反抗量子核算机破解才干的全新加密办法供给辅导。
“假如大规模的量子核算机终究被制作出来，那么分化算法就失效了，咱们有必要找到其他的加密办法。但这真的会是个要挟吗？咱们能让量子分化算法变得有用吗？咱们的研讨或许让咱们离有用化更近了一步，”福特基金会工程学教授、核算机科学与人工智能实验室（CSAIL）成员兼该论文的资深作者 Vinod Vaikuntanathan 说。
该论文的首要作者是麻省理工学院电子工程与核算机科学系的研讨生 Seyoon Ragavan。这项研讨将在 2024 年世界暗码学会议上宣布。
量子核算新打破：密码学迎来大考
（来历：MIT News）你最近发送的电子邮件很或许是运用一种经典加密办法进行加密的，这种办法根据这样一个主意：即使是最快的核算机也无法高效地将一个巨大的数字分化成因数。可是，量子核算机则有潜力能够快...