用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网科技动向学人动向
关键字  范围   
 
关于陈算法的背景以及更新
作者:Matthew Green | 2024/4/20 16:25:57 | 浏览:655 | 评论:0

如果你是一个普通人——也就是说,一个不痴迷于关注最新密码学新闻的人——你可能错过了上周的密码学重磅炸弹。这一消息以陈一镭(Yilei Chen)撰写的e-print论文《格问题的量子算法》的形式发布,引起了密码学学术界的轰动。现在,格和量子算法设计方面的专家正在评估这个结果(需要明确的是,我不是其中之一!),但如果结论成立,对于应用密码学社区来说,这将是非常糟糕的一天/一周/一个月/一年。

这里没有详细阐述,而是快速通过五个要点给出背景。

密码学家喜欢在被认为“困难”的数学问题之上构建现代公钥加密方案。实践中,我们需要具有特定结构的问题:我们可以为那些持有秘密密钥或“陷门”的人构建高效的解法,同时认为对于不持有秘密密钥的人没有高效的解法。虽然已经考虑了许多问题(并且经常被弃用),但我们今天使用的大多数方案都基于三个问题:因子分解(RSA 密码系统)、离散对数(Diffie-Hellman、DSA)和椭圆曲线离散对数问题(EC-Diffie-Hellman、ECDSA 等)。
虽然我们愿意相信我们喜欢的那些问题从根本上来说是“难的”,但我们知道事实并非如此。研究者已经设计出算法(Kurt Pan注:原文链接到Shor算法。)可以非常高效地(即在多项式时间内)解决所有上述问题——前提是有人知道如何构建一台足够强大的量子计算机来运行攻击算法。幸运的是,这样的计算机还没有被制造出来!
尽管量子计算机还没有强大到足以破解我们的公钥密码,但仅仅是未来的量子攻击的威胁已经激励工业界、政府和学术界联手以“护戒使者”式的方式(Kurt Pan 注:原文链接为NIST PQC竞赛,用《魔戒》中人类、精灵、矮人、巫师、霍比特人联合组成的护戒分队进行比喻。)现在就开始进行应对。这不仅仅是为了让我们的系统面向未来:即使量子计算机需要几十年的时间来建造,未来的量子计算机也可能破解我们今天发送的加密消息!
这个联盟的一个显著成果是 NIST 的后量子密码学(PQC)竞赛:这是一项旨在标准化 “后量子”密码方案的公开竞赛。至关重要的是,这些方案必须基于不同的数学问题——尤其显著的是,这些问题要似乎不允许有高效的量子解法。
在这组新方案中,最流行的一类方案是基于与称为格的数学对象相关的问题。 NIST 批准的基于格问题的方案包括 Kyber 和 Dilithium。格问题也是几种高效全同态加密(FHE)方案的基础。
这些是新结果的背景。

陈的(尚未经过同行评议的)预印本提出一种新的量子算法,可以高效解决具有特定参数的格中的“最短独立向量问题”(SIVP 以及 GapSVP)。如果成立,该结果可能(使得未来的量子计算机(带有许多重要需要注意点地)可以攻破依赖于这些问题的特定实例的难度的方案。好消息是,即使结果正确,易受攻击的参数也非常具体:陈的算法并不立即适用于最近标准化的 NIST 算法,比如 Kyber 或 Dilithium。此外,该算法确切的具体复杂度尚不清楚:即使量子计算机变得可用,该算法也可能无法实际运行。

但我们领域有一句话,攻击只会变得更好。如果陈的结果可以得到改进,那么量子算法可能会淘汰一整代基于格的所谓“后量子”方案,迫使密码学家和业界(https://security.apple.com/blog/imessage-pq3/https://signal.org/blog/pqxdh/https://bughunters.google.com/blog/5108747984306176/google-s-threat-model-for-post-quantum-cryptography)重新开始。

换句话说,这既是一项伟大的技术成果,也可能是一场微型灾难。(Kurt Pan注:对于相关方向诸多PhD和项目工程师,可能就是沉重的打击。)

如前所述:我既不是基于格的密码学也不是量子计算方面的专家。这些人正忙于验证这篇文章:之前历史上不少重大的结果经过详细检查后都分崩离析了。对于那些寻找最新进展的人来说,这里是 Nigel Smart 写的一篇不错的文章,没有解决这个问题量子算法的正确性(也请参阅下述更新),但确实讨论了对 FHE 和 PQC 方案的可能影响(简而言之:对某些 FHE 方案不利,但实际上取决于算法运行时间的具体细节。) [[近期量子攻击对 LWE 的影响]]

https://eprint.iacr.org/2024/583.pdf 这是关于发现论文中“错误”的另一个简短笔记,作者陈一镭似乎很快就解决了这个问题。

直到本周,我还打算写另一篇关于复杂性理论、格及其对应用密码学意味着什么的长篇文章。但基于现状,我希望你能原谅我,如果再延迟些发布的话。

Nigel Smart 4月16日更新
https://nigelsmart.github.io/LWE.html

阅读论文的更新
今天我更详细地查看了论文的第 3 节, 其中更详细地给出了攻击参数。

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新

关于陈算法的背景以及更新



相关栏目:『学人动向
冯玉军教授:与俄三次结盟中国损失巨大 2024-05-19 [8]
成立2年产出280篇论文,一个顶尖数学家兼亿万富翁和他打造的新型“科学帝国”|纪念吉姆·西蒙斯(1938-2024) 2024-05-17 [66]
KAN核心团队震撼力作!MIT华人用AI首次发现物理学全新方程 2024-05-17 [64]
图灵奖得主辛顿:坐学术冷板凳的30年 2024-05-18 [52]
詹姆斯·西蒙斯麻省演讲:数学,常识和运气 2024-05-16 [63]
“外籍院士”为何在中国井喷? 2024-05-15 [113]
四位数学家打破了一项长达 75 年之久的纪录,找到了一种更密集地堆积高维球体的方法。 2024-05-09 [132]
丘成桐:中国现今数学还没有达到美国20世纪40年代水平 2024-05-06 [264]
钱理群:想起了七十六年前的纪念 2024-05-05 [240]
画家、版画家威尔•巴尼特作品选 2024-05-05 [226]
相关栏目更多文章
最新图文:
:《2019全球肿瘤趋势报告》 :阿尔茨海默病预防与干预核心讯息图解 :引力波天文台或有助搜寻暗物质粒子 :Sail Through the Mist - SoCal Innovation Forum 2019(10/5) 游天龙:《唐人街》是如何炼成的:UCLA社会学教授周敏的学术之路 :“为什么海外华人那么爱国,但是让他回国却不愿意?...“ :学术出版巨头Elsevier 彻查433名审稿人“强迫引用”黑幕 :中国336个国家重点实验室布局
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2024 ScholarsUpdate.com. All Rights Reserved.