当前位置: 华文问答 > 科学

清华大学陈一镭发表量子算法,有望解决世界级算法难题「格密码」,该项工作有怎样的前景和意义?

2024-04-11科学

有点受不了上面有些答案了。先叠个buff,个人lattice的水平相当于本科生的水平,如果错误还轻大佬指出我好修正。

评价这个工作的意义可以有几方面角度:

首先,这篇文章不是第一个来question LWE hardness的文章,上面已经有哥们提到了。但是前面的文章要么有fundamental的错误要么过于简化问题了。但是纠结是不是第一个来做这个意义不大,第一个作出有意义的结果意义比较大。

其次,假设整篇文章的提供了一个sound的结果。是不是意味着lattice base cryptograph无了?

这一点感觉还不是很清晰。文章作者也提到了,即使这个结果正确也不意味着现在的这些lattice proposal直接无了。 但是, 攻击在多数情况下都是可以被改进的,甚至数学证明也是可以被改进的。正面例子如张益唐证明相邻素数间隔有限的文章,文章已经发出验证后很快bound就从几千万被改进到几千了(如果我记得没错)。另一个正面例子是王小云院士的hash collision工作,也被后面的人在2017年改进到能实际进行攻击了。

进一步,如果这篇工作导致lattice base cryptography无了,是不是直接利好量子加密(个人不是很懂什么是量子加密)?

个人觉得这个问题答案是否定的,先不说什么美国政府已经有报告说量子密钥分发实际意义不大以及种种阴谋论。要我说NIST那帮人还是有两把刷子的,可能以前就吃过亏。我记得NIST explictly说到过最终的post-quantum candidates一定要一个非lattice based,这样押宝不押一个免得到时候出问题了手忙脚乱。所以,post-quantum的方案不仅仅是lattice-based,还有其他五六种可供选择的困难问题,比较promising的也还有两三个。所以未来即使lattice base cryptography无了,也还有其他问题可以用来构造post-quantum的算法。

再次,在文章正确的前提下,怎么看待这篇的科学贡献?

首先,什么CRYPTO/EUROCRYPT,FOCS/STOC最佳论文 test-of-time预定一波。可供参考的是去年EUROCRPYT上攻击SIKE的团建,毫无疑问的直接拿下了best paper。但是上述这些论文能不能够的上test-of-time我还持怀疑态度。这篇可能预定15年后的test-of-time的 关键 是它的target是 困难性问题,而上述SIKE的攻击只是针对的特定构造方案。 一个不是很恰当的比喻是困难性问题如同给出了二氧化碳+糖水的组合是万千肥宅的快乐水,特定构造方案就相当于你来调个可乐我来调个雪碧,他来加点果汁弄个芬达。一个更直观的说法可能是,这篇文章可以使得近来几乎所有的post-quantum的炼丹成为一炉废丹,而前面去年的SIKE攻击paper只是说有一粒丹(SIKE)是废丹,二其他丹(基于isogeny)可能还是好的。

最后,这篇论文能得图灵奖吗?

个人感觉几乎不可能,虽然基于朴素的民族情绪我也希望能。本质上说,整篇文章的可能贡献就是证明lattice的喜闻乐见的难题LWE不能再被认为是困难的了。同等贡献的有Peter Shor证明大数分解不那么安全,并且他还有第一个用量子计算来研究密码学的困难性问题的buff。所以即便颁奖也应该给他。还有,整篇文章并不能够全盘否定lattice based cryptography(在我看来),LWE等问题解决应该不能直接证明SIS及其变种解决,虽然SIS能玩的花样很少并且整个lattice的安全会受到质疑。另外个人觉得同等地位的工作还是有不少的,比如Coppersmith,LLL reduction,Paul Kosher的side channel。

修正1:根据https:// web.eecs.umich.edu/~cpe ikert/pubs/slides-abit2.pdf 46/94, LWE可以在有quantum 的条件下reduct TO SIS. 因此quantum的LWE快速算法能够攻击SIS。(这一点欢迎大家来指正)

修正2: 是其他基于isogeny的protocol不是SIDH.