清华提出破解后量子密码新算法（不成立）

[Caravel]

近日清华大学交叉信息研究院陈一镭助理教授在eprint上发布了重要论文，给出了一个破解格密码的量子算法。论文标题为Quantum Algorithms for Lattice Problems。 链接：https://eprint.iacr.org/2024/555。
解决格上的近似最短向量问题（Approximate Shortest Vector Problems in Lattices, 简称Lattice Problems）以及与之等价的带错误学习问题（Learning with Errors,简称LWE）是经典的算法难题，科学界普遍认为它们超出了传统计算机的能力范围。那么，量子计算机有望能破解Lattice Problems以及LWE吗？这个问题一直受到广大关注，但鲜有显著进展。陈一镭的工作提出了一个全新的量子算法来解决LWE以及与之等价的格问题。这项工作仍在同行评议中。如果被验证为正确，将为这个悬而未决的问题给出肯定的答复。它在科学上的意义将是双层的: 第一，这将是自30年前Peter Shor提出大数分解的量子算法以来，最重要的量子算法突破。第二，这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响，因为多数选出的后量子密码方案都是基于Lattice Problems 或LWE。 陈一镭的工作无疑将使他们安全性受到质疑。
这篇论文提出的算法及分析极为新颖而深奥。回想Wiles 1994年解决费马大定理（Fermat's Last Theorem），以及Perelman 2002年解决庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”

[wanmeishijie]

清~华~出栋~
啊？不对！是上交出栋梁！

[dreamig]

RTMD，量子计算机都没有影子，这量子算法是个什么鬼

[wanmeishijie]

清华果然是汉奸 和裤子大对着干

这人是上交的

[Caravel]

清华果然是汉奸 和裤子大对着干

这个是利好量子计算机

[Drshepherd]

汉奸为何老是发表

解密算法

[dreamig]

这个量子算法是不是又是给量子计算机画的啥大饼？

[laodongzhe18]

能发表的解密算法都是没用的。

[Caravel]

这个量子算法是不是又是给量子计算机画的啥大饼？

Peter shor证明了量子算法可以多项式时间破解大数分解，密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确，就又破解了其中最流行的一种

[wttw]

完了，格论加密都被量子算法破解了，没有什么经典公钥系统是安全的了。

近日清华大学交叉信息研究院陈一镭助理教授在eprint上发布了重要论文，给出了一个破解格密码的量子算法。论文标题为Quantum Algorithms for Lattice Problems。 链接：https://eprint.iacr.org/2024/555。
解决格上的近似最短向量问题（Approximate Shortest Vector Problems in Lattices, 简称Lattice Problems）以及与之等价的带错误学习问题（Learning with Errors,简称LWE）是经典的算法难题，科学界普遍认为它们超出了传统计算机的能力范围。那么，量子计算机有望能破解Lattice Problems以及LWE吗？这个问题一直受到广大关注，但鲜有显著进展。陈一镭的工作提出了一个全新的量子算法来解决LWE以及与之等价的格问题。这项工作仍在同行评议中。如果被验证为正确，将为这个悬而未决的问题给出肯定的答复。它在科学上的意义将是双层的: 第一，这将是自30年前Peter Shor提出大数分解的量子算法以来，最重要的量子算法突破。第二，这将对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响，因为多数选出的后量子密码方案都是基于Lattice Problems 或LWE。 陈一镭的工作无疑将使他们安全性受到质疑。
这篇论文提出的算法及分析极为新颖而深奥。回想Wiles 1994年解决费马大定理（Fermat's Last Theorem），以及Perelman 2002年解决庞佳莱猜想（Poincaré Conjecture）后，都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”

[dreamig]

Peter shor证明了量子算法可以多项式时间破解大数分解，密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确，就又破解了其中最流行的一种

连量子计算机都没有，搞量子算法是不是空中楼阁？

[Caravel]

连量子计算机都没有，搞量子算法是不是空中楼阁？

量子算法是数学家搞，计算机是物理学家做，不耽误时间

[wanmeishijie]

连量子计算机都没有，搞量子算法是不是空中楼阁？

相当于高手比剑法，不需要真打，凌空拿树枝子 点几下就知道谁克谁了

[laodongzhe18]

Here is a high level overview of our quantum algorithm for solving LWE. In fact, the entire quantum
algorithm we use just consists of QFTs, complex Gaussian windows, and other standard quantum
computation tools. However, how to combine them together is highly non-trivial, the detail calculations
are very complicated. So here we will only mention the most important ideas. We will provide a more
detailed overview in §3.4 after all parameters used in the algorithm are defined.
Our quantum algorithm runs a quantum subroutine consisting of nine steps for O(n) times. Every time
we run the quantum subroutine, we will obtain a classical linear equation with random coefficients and
the unknown variables are the LWE secrets and error terms. After running the quantum subroutine for
O(n) times we will get a full rank system of linear equations and compute the LWE secret and error
terms by Gaussian elimination.

总感觉不太靠谱，似乎是处理了个特例，最后的实用复杂度可能并没用减少，更有可能更高。

Peter shor证明了量子算法可以多项式时间破解大数分解，密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确，就又破解了其中最流行的一种

[dreamig]

去年清华大学的另一位教授也发了一种量子算法，很牛逼，后来没有信了

[Caravel]

去年清华大学的另一位教授也发了一种量子算法，很牛逼，后来没有信了

姚期智就是量子算法的高手

[laodongzhe18]

比AI如何？

姚期智就是量子算法的高手

[Caravel]

比AI如何？

这个如果是真的，影响非常大。NIST花十年选出来4个抗量子密码，3个最好的都是基于lattice。

hackernews 已经热议了

https://news.ycombinator.com/item?id=39998396

[Caravel]

算法继续引起压力巨大的反响，很多专家都看了，似乎还没有人发现漏洞

[Caravel]

最新更新，被找到bug了，作者认错