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

对应老买买提的军事天地,观点交锋比较激烈。因为此版帖子太多,所以新帖不出现在首页新帖列表,防止首页新帖刷屏太快。

版主: Softfist

Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#1 清华提出破解后量子密码新算法(不成立)

帖子 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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
上次由 Caravel 在 2024年 4月 19日 14:20 修改。
wanmeishijie(石昊)
论坛元老
论坛元老
wanmeishijie 的博客
帖子互动: 2039
帖子: 68164
注册时间: 2022年 12月 10日 23:58

#3 Re: 清华提出破解后量子密码新算法

帖子 wanmeishijie(石昊) »

清~华~出栋~
啊?不对!是上交出栋梁!
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513

理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当” :lol:
dreamig
论坛支柱
论坛支柱
帖子互动: 248
帖子: 11735
注册时间: 2022年 7月 26日 22:43

#4 Re: 清华提出破解后量子密码新算法

帖子 dreamig »

RTMD,量子计算机都没有影子,这量子算法是个什么鬼
wanmeishijie(石昊)
论坛元老
论坛元老
wanmeishijie 的博客
帖子互动: 2039
帖子: 68164
注册时间: 2022年 12月 10日 23:58

#5 Re: 清华提出破解后量子密码新算法

帖子 wanmeishijie(石昊) »

Ifloating 写了: 2024年 4月 11日 10:15 清华果然是汉奸 和裤子大对着干
这人是上交的
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513

理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当” :lol:
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#6 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

Ifloating 写了: 2024年 4月 11日 10:15 清华果然是汉奸 和裤子大对着干
这个是利好量子计算机
Drshepherd
论坛精英
论坛精英
帖子互动: 228
帖子: 8531
注册时间: 2022年 7月 22日 00:32

#7 Re: 清华提出破解后量子密码新算法

帖子 Drshepherd »

汉奸为何老是发表

解密算法
dreamig
论坛支柱
论坛支柱
帖子互动: 248
帖子: 11735
注册时间: 2022年 7月 26日 22:43

#8 Re: 清华提出破解后量子密码新算法

帖子 dreamig »

这个量子算法是不是又是给量子计算机画的啥大饼?
头像
laodongzhe18(组长)
论坛元老
论坛元老
帖子互动: 1070
帖子: 30351
注册时间: 2022年 7月 26日 09:36

#9 Re: 清华提出破解后量子密码新算法

帖子 laodongzhe18(组长) »

能发表的解密算法都是没用的。
而生 在难逃
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#10 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

dreamig 写了: 2024年 4月 11日 10:21 这个量子算法是不是又是给量子计算机画的啥大饼?
Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
x1 图片
wttw
论坛点评
论坛点评
帖子互动: 132
帖子: 2943
注册时间: 2022年 8月 2日 01:43

#12 Re: 清华提出破解后量子密码新算法

帖子 wttw »

完了,格论加密都被量子算法破解了,没有什么经典公钥系统是安全的了。
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)后,都经过一年以上专家们方能彻底认证其正确性。陈一镭的工作,预料也需要数月时间才能完成验证认可。我们静候科学界对此工作的后续反应。
清华交叉信息研究院院长姚期智说:“作为一个青年教师,陈一镭能勇于挑战如格密码这样的世界级科学难题,令人赞佩!”
dreamig
论坛支柱
论坛支柱
帖子互动: 248
帖子: 11735
注册时间: 2022年 7月 26日 22:43

#13 Re: 清华提出破解后量子密码新算法

帖子 dreamig »

Caravel 写了: 2024年 4月 11日 10:27 Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
连量子计算机都没有,搞量子算法是不是空中楼阁?
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#14 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

dreamig 写了: 2024年 4月 11日 10:32 连量子计算机都没有,搞量子算法是不是空中楼阁?
量子算法是数学家搞,计算机是物理学家做,不耽误时间
wanmeishijie(石昊)
论坛元老
论坛元老
wanmeishijie 的博客
帖子互动: 2039
帖子: 68164
注册时间: 2022年 12月 10日 23:58

#15 Re: 清华提出破解后量子密码新算法

帖子 wanmeishijie(石昊) »

dreamig 写了: 2024年 4月 11日 10:32 连量子计算机都没有,搞量子算法是不是空中楼阁?
相当于高手比剑法,不需要真打,凌空拿树枝子 点几下就知道谁克谁了
理解了老将是代入狗的视角之后,你就理解了老将
viewtopic.php?t=120513

理解了它们是代入狗的视角之后,它们为什么会嘲笑不愿意当狗的人,以及为什么会害怕想要反抗的人,就都可以理解了:
“放着好好的狗不当” :lol:
头像
laodongzhe18(组长)
论坛元老
论坛元老
帖子互动: 1070
帖子: 30351
注册时间: 2022年 7月 26日 09:36

#16 Re: 清华提出破解后量子密码新算法

帖子 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.

总感觉不太靠谱,似乎是处理了个特例,最后的实用复杂度可能并没用减少,更有可能更高。
Caravel 写了: 2024年 4月 11日 10:27 Peter shor证明了量子算法可以多项式时间破解大数分解,密码学就提出了一系列新的密码认为量子计算机破解不了的加密方法。这篇文章如果正确,就又破解了其中最流行的一种
而生 在难逃
dreamig
论坛支柱
论坛支柱
帖子互动: 248
帖子: 11735
注册时间: 2022年 7月 26日 22:43

#17 Re: 清华提出破解后量子密码新算法

帖子 dreamig »

去年清华大学的另一位教授也发了一种量子算法,很牛逼,后来没有信了
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#18 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

dreamig 写了: 2024年 4月 11日 10:44 去年清华大学的另一位教授也发了一种量子算法,很牛逼,后来没有信了
姚期智就是量子算法的高手
头像
laodongzhe18(组长)
论坛元老
论坛元老
帖子互动: 1070
帖子: 30351
注册时间: 2022年 7月 26日 09:36

#19 Re: 清华提出破解后量子密码新算法

帖子 laodongzhe18(组长) »

比AI如何?
Caravel 写了: 2024年 4月 11日 11:01 姚期智就是量子算法的高手
而生 在难逃
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#20 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

laodongzhe18 写了: 2024年 4月 11日 11:34 比AI如何?
这个如果是真的,影响非常大。NIST花十年选出来4个抗量子密码,3个最好的都是基于lattice。

hackernews 已经热议了

https://news.ycombinator.com/item?id=39998396
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#21 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

算法继续引起压力巨大的反响,很多专家都看了,似乎还没有人发现漏洞
Caravel楼主
论坛元老
论坛元老
Caravel 的博客
帖子互动: 545
帖子: 24293
注册时间: 2022年 7月 24日 17:21

#22 Re: 清华提出破解后量子密码新算法

帖子 Caravel楼主 »

最新更新,被找到bug了,作者认错
回复

回到 “军事天地(Military)”