清华提出破解后量子密码新算法(不成立)
版主: Softfist
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
#1 清华提出破解后量子密码新算法(不成立)
近日清华大学交叉信息研究院陈一镭助理教授在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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
解决格上的近似最短向量问题(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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
上次由 Caravel 在 2024年 4月 19日 14:20 修改。
-
- 论坛元老
wanmeishijie 的博客 - 帖子互动: 2039
- 帖子: 68164
- 注册时间: 2022年 12月 10日 23:58
#3 Re: 清华提出破解后量子密码新算法
清~华~出栋~
啊?不对!是上交出栋梁!
啊?不对!是上交出栋梁!
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”

-
- 论坛元老
wanmeishijie 的博客 - 帖子互动: 2039
- 帖子: 68164
- 注册时间: 2022年 12月 10日 23:58
#5 Re: 清华提出破解后量子密码新算法
这人是上交的
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”

-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
#10 Re: 清华提出破解后量子密码新算法
Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
x1

#12 Re: 清华提出破解后量子密码新算法
完了,格论加密都被量子算法破解了,没有什么经典公钥系统是安全的了。
Caravel 写了: 2024年 4月 11日 10:13 近日清华大学交叉信息研究院陈一镭助理教授在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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
#13 Re: 清华提出破解后量子密码新算法
连量子计算机都没有,搞量子算法是不是空中楼阁?Caravel 写了: 2024年 4月 11日 10:27 Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
-
- 论坛元老
wanmeishijie 的博客 - 帖子互动: 2039
- 帖子: 68164
- 注册时间: 2022年 12月 10日 23:58
#15 Re: 清华提出破解后量子密码新算法
相当于高手比剑法,不需要真打,凌空拿树枝子 点几下就知道谁克谁了
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”
viewtopic.php?t=120513
理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当”

#16 Re: 清华提出破解后量子密码新算法
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.
总感觉不太靠谱,似乎是处理了个特例,最后的实用复杂度可能并没用减少,更有可能更高。
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.
总感觉不太靠谱,似乎是处理了个特例,最后的实用复杂度可能并没用减少,更有可能更高。
Caravel 写了: 2024年 4月 11日 10:27 Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
应运而生 在劫难逃
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
#20 Re: 清华提出破解后量子密码新算法
这个如果是真的,影响非常大。NIST花十年选出来4个抗量子密码,3个最好的都是基于lattice。
hackernews 已经热议了
https://news.ycombinator.com/item?id=39998396
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21
-
- 论坛元老
Caravel 的博客 - 帖子互动: 545
- 帖子: 24293
- 注册时间: 2022年 7月 24日 17:21