（转载）清华提出破解后量子密码新算法

[Caravel]

此帖转自 Caravel 在 军事天地（Military） 的帖子：清华提出破解后量子密码新算法

近日清华大学交叉信息研究院陈一镭助理教授在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）后，都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作，预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说：“作为一个青年教师，陈一镭能勇于挑战如格密码这样的世界级科学难题，令人赞佩！”

[FoxMe]

尼玛美国辛辛苦苦搞出来的后量子密码，被中国轻易攻破了？中国真是美国的克星啊，想当年王小云也攻破了美国密码。

[（ヅ）]

尼玛美国辛辛苦苦搞出来的后量子密码，被中国轻易攻破了？中国真是美国的克星啊，想当年王小云也攻破了美国密码。

王博士破解的不是密码，是摘要

[Caravel]

尼玛美国辛辛苦苦搞出来的后量子密码，被中国轻易攻破了？中国真是美国的克星啊，想当年王小云也攻破了美国密码。

NIST的PQC算法竞赛finalist有4个，三个基于lattice。

[FoxMe]

让子弹飞一会。还没通过评审就宣布，有点浮躁。

张益唐的文章估计有问题，到现在还没录用。这些人等一等不行吗？

[Caravel]

让子弹飞一会。还没通过评审就宣布，有点浮躁。

张益唐的文章估计有问题，到现在还没录用。这些人等一等不行吗？

虽然没过评审，但是这文章已经有不少业内专家review过了，包括姚期智。跟老张这种独行侠不一样

搞量子密码今天都很悲观

[Caravel]

让子弹飞一会。还没通过评审就宣布，有点浮躁。

张益唐的文章估计有问题，到现在还没录用。这些人等一等不行吗？

讨论链接
https://news.ycombinator.com/item?id=39998396

[AnonymityFreedom]

NIST的PQC算法竞赛finalist有4个，三个基于lattice。

这个文章自己并没有宣称破译PQC的算法。还没有伤及Kyber or NTRU.

这个结果如果最终确认的话， 会不会在计算机理论上的意义上更重要些？GAPSVP是一个NP Hard的问题，这个结果是说NP Hard也是有可能被量子计算机多项式时间内解决的。

[FoxMe]

如果此文正确，将从根本上动摇格密码的理论基础。但是姚期智不懂格密码。

虽然没过评审，但是这文章已经有不少业内专家review过了，包括姚期智。跟老张这种独行侠不一样

搞量子密码今天都很悲观

[FoxMe]

实际的格密码不是基于NP hard问题。一般认为，量子计算机也无法在多项式时间内解决NP hard问题。

这个文章自己并没有宣称破译PQC的算法。还没有伤及Kyber or NTRU.

这个结果如果最终确认的话， 会不会在计算机理论上的意义上更重要些？GAPSVP是一个NP Hard的问题，这个结果是说NP Hard也是有可能被量子计算机多项式时间内解决的。

[Caravel]

如果此文正确，将从根本上动摇格密码的理论基础。但是姚期智不懂格密码。

你确信他不懂格论？他的主要研究方向就是密码学和量子计算吧

[AnonymityFreedom]

实际的格密码不是基于NP hard问题。

感觉这个理解有偏差。 再来一遍：
【1】GapSVP 被认为是NP Hard 的。
【2】Regev 证明了GapSVP is polynomial-time reducible to LWE；
【3】LWE 是好几个PQC (比如Kyber)的基础

上面的哪个环节有错误吗？

要是没有错误的话， 那么， 这个的结论是什么？

[FoxMe]

可以确定。专家出了他的领域，也就是个凡人。

你确信他不懂格论？他的主要研究方向就是密码学和量子计算吧

[FoxMe]

粗略地说，问题在于这个GAP有多大。

GAP = 常数，是NP hard；
GAP = 多项式，一般认为不是NP hard；
GAP = 指数，是P。

如果此文正确，说明清华的研究水平已经达到世界顶尖了，超过一般图灵奖水平。美国白忙乎了。

感觉这个理解有偏差。 再来一遍：
【1】GapSVP 被认为是NP Hard 的。
【2】Regev 证明了GapSVP is polynomial-time reducible to LWE；
【3】LWE 是好几个PQC (比如Kyber)的基础

上面的哪个环节有错误吗？

要是没有错误的话， 那么， 这个的结论是什么？

[Caravel]

粗略地说，问题在于这个GAP有多大。

GAP = 常数，是NP hard；
GAP = 多项式，一般认为不是NP hard。

如果此文正确，说明清华的研究水平已经达到世界顶尖了，超过一般图灵奖水平。美国白忙乎了。

你好像是这个方向的？

[FoxMe]

略知一二。

你好像是这个方向的？

[AnonymityFreedom]

GAP = 常数，是NP hard；

Agreed.

GAP = 多项式，一般认为不是NP hard；

Not exactly; see below.

如果此文正确，将从根本上动摇格密码的理论基础。

This is premature; see below.

[Caravel]

Agreed.



Not exactly; see below.




This is premature; see below.

这声明估计是审稿人要求加进去的吧，不能把业内前辈打脸太狠

[FoxMe]

这篇文章的状态像是望月新一的ABC猜想证明，没人知道对不对。

已经被人挑出毛病了：他要求O(n)个小于n的整数两两互素，怎么可能？两两互素，要求这些整数的素因子不同，但是小于n的素数只有O(n/log(n))个，显然不可能。所以搞密码，先要学好数论。

[Caravel]

这篇文章的状态像是望月新一的ABC猜想证明，没人知道对不对。

已经被人挑出毛病了：他要求O(n)个小于n的整数两两互素，怎么可能？两两互素，要求这些整数的素因子不同，但是小于n的素数只有O(n/log(n))个，显然不可能。所以搞密码，先要学好数论。

哪里？