[自然科学] 如何看待清华大学陈一镭老师设计的量子算法，在多项式时间内解决LWE？

天天财汇购物网址万年历小说 | 三峰软件小游戏视频

TxT小说阅读器
↓小说语音阅读,小说下载↓

一键清除系统垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

图片自动播放器
↓图片自动播放,产品展示↓

首页淘股吧股票涨跌实时统计涨停板选股股票入门股票书籍股票问答分时图选股跌停板选股 K线图选股成交量选股 [平安银行]

股市论谈均线选股趋势线选股筹码理论波浪理论缠论 MACD指标 KDJ指标 BOLL指标 RSI指标炒股基础知识炒股故事

商业财经科技知识汽车百科工程技术自然科学家居生活设计艺术财经视频游戏--

天天财汇 -> 自然科学 -> 如何看待清华大学陈一镭老师设计的量子算法，在多项式时间内解决LWE？ -> 正文阅读

[自然科学]如何看待清华大学陈一镭老师设计的量子算法，在多项式时间内解决LWE？

[收藏本文] 【下载本文】

Quantum Algorithms for Lattice Problems， https://eprint.iacr.org/2024/555

密码学新生。最近在研究基于sis问题的格密码。
请问下各位老师，如果这篇论文被验证通过。是不是代表格密码一系列困难问题都不安全了，不管什么svp，cvp，sivp啥的。对平均情况下困难性和最坏情况下困难性不怎么懂。
是不是格密码整个体制都崩塌了，我应该换研究方向了吧

从论文致谢部分来看的话，引入LWE问题的Oded Regev本人很有可能已经看过论文的手稿了

修改一下对这个结论强度的评价，今天下午具体看了一下，感觉似乎在宣传上是有些overclaim了…………删了一部分吹的（果然还是不应该贸然对不那么了解的subfield光速吹水，过段时间闲了看看paper再更新）
以下为修改后的回答
目前的情况是verify中…………如果证实了的话应该算是很强的结论（当然一切前提都是证实了）
btw，作者本人claim这套方法如果被验证为真的话或许可以尝试一下NP in BQP，当然我不论在crypto还是在quantum上都是门外汉，太细节的东西就不评价了（逃），不过无论如何，能向这种tcs界的传统boss发起挑战都是值得敬佩和赞赏的
总之先观望，顺便花一段看看其他大神的评价先（

如果是真的，意味着目前的大量的后量子密码学相关论文的价值变为了原来的1/1000。
题外话，这将会是对潘建伟老师的公司国盾量子有史以来最大的利好。
因为在原来，无论是长期还是短期，都认为只要使用上了后量子密码学，就不会被量子计算机攻破。从而密码学算法将不会是安全体系短板。
但是如果是真的话，那么后量子密码算法将不再安全，未来还是需要使用量子密码协商从物理机制上来保证密钥分发的安全性。
无疑这极大的扩展了国盾量子的市场面。
原回答链接:
清华大学陈一镭发表量子算法，有望解决世界级算法难题「格密码」，该项工作有怎样的前景和意义？?www.zhihu.com/question/652567682/answer/3461932716?utm_psn=1761758353988898816

这个成果还处于同行评议中啦，还是先蹲一下后续的进展。如果通过了评审，那这一工作的意义一方面，对于量子计算而言，是继大数分解后，量子算法上的重要突破。另一方面，就应对量子计算对经典密码威胁的举措而言，会对美国NIST过去10年来选择后量子密码设计的思路产生颠覆性的影响，去年美国国家标准与技术研究院公布的三种后量子密码（PQC）算法标准草案，有两种都是基于格密码，而这一成果让其安全性再受质疑。量子计算的“矛”越来越锋利，而PQC铸成的“盾”似乎有些不靠谱了。

“以经典抗量子——后量子密码算法（PQC）”和“以量子抗量子——量子密码技术”，是当前抵御量子计算对经典密码破解威胁、实现信息安全机制的两种主要途径。
问题中的格密码便是极具代表性的PQC。PQC基于已知量子算法无法多项式时间求解的数学困难问题而设计，安全性依赖于计算复杂度。但未来PQC依赖的数学难题是否依然难解、算法安全性是否长期有效、面对新出现的量子攻击是否依旧免疫等问题，都是未知的。此次破解格密码量子算法的研究也表明，PQC存在一定脆弱性和不确定性因素。
所以相比较而言，具有长效安全性的量子密码是一劳永逸的解决方案。
量子密码的显著优势在于，基于自身量子物理实现原理，即单量子不可分割、量子态不可克隆所实现的抗量子计算攻击能力。以其中最具代表和实用性的量子密钥分发技术为例，通信双方通过传送量子态的方法，实现信息论安全的密钥生成和分发的方法和过程，即使在攻击者拥有无限强的计算资源下也仍然安全。

一大早起来看到这个，太震撼了。如果是真的，量子密码这十年来的发展看来只是走过了一段小小的弯路。

啊？？卧槽？？要是真的话感觉就是当前（后量子）密码学既shor算法后最重要的突破了。格密码的主流构造基于lwe和rlwe的在量子计算下就都不安全了。希望能见证历史

如果最后证明算法是正确的，那后量子密码领域真要翻天覆地了

似乎文章里说的是解决了某种多项式模数噪声比率的LWE，并不是所有的LWE？我不太懂格密码，不知道这个参数是否涵盖了大部分的应用场景。

然后后面又说他的这个攻击对现有的NIST候选没用，因为参数范围不太符合，所以把这个留作未来的工作。

所以单从这篇论文看，以我一个格密码小白的角度看，似乎没有大家想象中那么的完美，直接把所有格密码都攻破了，但至少这个工作为后续的研究者打开了一个窗口，即格密码并不是无懈可击的，很有可能后续的工作很快就会把他声称的没攻破的那些算法攻破了(有点像张益唐的孪生素数那个工作，开创性的文章出来后，后面就有很多工作缩小gap了)，毕竟万事开头难嘛。所以这个工作的意义还是非常重大的。至少以后大家在使用格密码的时候，一定就会非常谨慎了。
当然前提是这个结果是真的情况下，这个得需要等同行评议了。

陈一镭老师设计的量子算法在多项式时间内解决学习有误差问题（Learning With Errors, LWE）是一个重要的研究成果，对于量子计算和密码学领域都具有潜在的深远影响。根据提供的论文摘要，这项工作展示了如何利用量子算法来解决具有特定多项式模数-噪声比的LWE问题。通过结合Regev在2009年提出的从格问题到LWE的归约，该算法进一步为解决所有维度格的决策最短向量问题（GapSVP）和最短独立向量问题（SIVP）提供了多项式时间的量子算法，并且在近似因子上有显著的改进。
以下是对这项研究的几个关键点的分析：
技术创新：陈一镭老师的研究引入了两种新技术。首先，他在量子算法设计中引入了具有复数方差的高斯函数。特别是，他利用了复数高斯函数在离散傅里叶变换中的Karst波特征。其次，他使用了带有复数高斯窗口的窗口量子傅里叶变换，这使得算法能够结合时间和频率域的信息。算法流程：该算法首先将LWE实例转换为具有纯虚高斯幅度的量子态，然后将纯虚高斯态转换为关于LWE秘密和误差项的经典的线性方程，最后使用高斯消元法解决线性方程组。这个过程为解决LWE问题提供了一个多项式时间的量子算法。对密码学的影响：LWE问题是现代密码学中的一个重要问题，因为它是许多后量子密码学方案的基础。如果能够有效地解决LWE问题，那么它可能会对现有的加密系统构成威胁，促使密码学界寻找更加安全的加密方法。对量子计算的意义：这项研究进一步证明了量子计算在解决特定类型问题上的优势。它展示了量子算法在处理复杂数学问题，特别是与格相关的问题上的潜力，这可能会推动量子计算技术的发展和应用。未来研究方向：这项工作可能会激发更多的研究，探索量子算法在其他数学问题和密码学问题上的应用。同时，它也可能促进对量子算法的进一步改进，以提高其效率和实用性。
综上所述，陈一镭老师设计的量子算法是一个值得关注的突破性成果，它不仅在理论上具有重要意义，也可能对未来的密码学实践和量子计算技术产生实际影响。然而，需要注意的是，量子计算机的实现和量子算法的实际应用仍然面临许多技术挑战，因此这一领域的研究仍在不断发展之中。

[收藏本文] 【下载本文】

自然科学最新文章

海南一村民被眼镜王蛇咬死，多名消防员和村

有哪些不起眼的牢底坐穿兽？

美国耕地面积比中国大，可为什么粮食产量不

如何看待同济大学2024国家科技三大奖颗粒无

加:2024-04-12 13:18:28 更:2024-04-12 13:46:55

股票涨跌实时统计涨停板选股分时图选股跌停板选股 K线图选股成交量选股均线选股趋势线选股筹码理论波浪理论缠论 MACD指标 KDJ指标 BOLL指标 RSI指标炒股基础知识炒股故事

网站联系: qq:121756557 email:121756557@qq.com 天天财汇