(转载)清华提出破解后量子密码新算法
版主: verdelite, Tlexander
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
#1 (转载)清华提出破解后量子密码新算法
此帖转自 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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
近日清华大学交叉信息研究院陈一镭助理教授在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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
#2 Re: (转载)清华提出破解后量子密码新算法
尼玛美国辛辛苦苦搞出来的后量子密码,被中国轻易攻破了?中国真是美国的克星啊,想当年王小云也攻破了美国密码。
-
- 论坛精英
- 帖子: 5374
- 注册时间: 8月 21, 2022, 2:20 pm
#3 Re: (转载)清华提出破解后量子密码新算法
王博士破解的不是密码,是摘要
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
#5 Re: (转载)清华提出破解后量子密码新算法
让子弹飞一会。还没通过评审就宣布,有点浮躁。
张益唐的文章估计有问题,到现在还没录用。这些人等一等不行吗?
张益唐的文章估计有问题,到现在还没录用。这些人等一等不行吗?
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
-
- 正式写手
- 帖子: 153
- 注册时间: 1月 30, 2023, 9:47 am
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
#10 Re: (转载)清华提出破解后量子密码新算法
实际的格密码不是基于NP hard问题。一般认为,量子计算机也无法在多项式时间内解决NP hard问题。
AnonymityFreedom 写了: ↑4月 11, 2024, 9:15 pm 这个文章自己并没有宣称破译PQC的算法。还没有伤及Kyber or NTRU.
这个结果如果最终确认的话, 会不会在计算机理论上的意义上更重要些?GAPSVP是一个NP Hard的问题,这个结果是说NP Hard也是有可能被量子计算机多项式时间内解决的。
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
-
- 正式写手
- 帖子: 153
- 注册时间: 1月 30, 2023, 9:47 am
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
#15 Re: (转载)清华提出破解后量子密码新算法
粗略地说,问题在于这个GAP有多大。
GAP = 常数,是NP hard;
GAP = 多项式,一般认为不是NP hard;
GAP = 指数,是P。
如果此文正确,说明清华的研究水平已经达到世界顶尖了,超过一般图灵奖水平。美国白忙乎了。
GAP = 常数,是NP hard;
GAP = 多项式,一般认为不是NP hard;
GAP = 指数,是P。
如果此文正确,说明清华的研究水平已经达到世界顶尖了,超过一般图灵奖水平。美国白忙乎了。
AnonymityFreedom 写了: ↑4月 12, 2024, 8:31 pm 感觉这个理解有偏差。 再来一遍:
【1】GapSVP 被认为是NP Hard 的。
【2】Regev 证明了GapSVP is polynomial-time reducible to LWE;
【3】LWE 是好几个PQC (比如Kyber)的基础
上面的哪个环节有错误吗?
要是没有错误的话, 那么, 这个的结论是什么?
上次由 FoxMe 在 4月 14, 2024, 10:26 am,总共编辑 1 次。
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
-
- 正式写手
- 帖子: 153
- 注册时间: 1月 30, 2023, 9:47 am
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm
#19 Re: (转载)清华提出破解后量子密码新算法
这声明估计是审稿人要求加进去的吧,不能把业内前辈打脸太狠AnonymityFreedom 写了: ↑4月 14, 2024, 12:31 pm Agreed.
Not exactly; see below.
This is premature; see below.
-
- 著名点评
- 帖子: 3282
- 注册时间: 7月 26, 2022, 4:46 pm
- 昵称(选填): 令狐
#20 Re: (转载)清华提出破解后量子密码新算法
这篇文章的状态像是望月新一的ABC猜想证明,没人知道对不对。
已经被人挑出毛病了:他要求O(n)个小于n的整数两两互素,怎么可能?两两互素,要求这些整数的素因子不同,但是小于n的素数只有O(n/log(n))个,显然不可能。所以搞密码,先要学好数论。
已经被人挑出毛病了:他要求O(n)个小于n的整数两两互素,怎么可能?两两互素,要求这些整数的素因子不同,但是小于n的素数只有O(n/log(n))个,显然不可能。所以搞密码,先要学好数论。
-
- 论坛支柱
Caravel 的博客 - 帖子: 12338
- 注册时间: 7月 24, 2022, 5:21 pm