量子前沿

现代科学的前沿阵地

当前位置:首页>量子前沿

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

时间:2024-04-18   访问量:55

原文:https://blog.cryptographyengineering.com/2024/04/16/a-quick-post-on-chens-algorithm/
作者:Matthew Green
译者:Kurt Pan


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

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


  1. 密码学家喜欢在被认为“困难”的数学问题之上构建现代公钥加密方案。实践中,我们需要具有特定结构的问题:我们可以为那些持有秘密密钥或“陷门”的人构建高效的解法,同时认为对于不持有秘密密钥的人没有高效的解法。虽然已经考虑了许多问题(并且经常被弃用),但我们今天使用的大多数方案都基于三个问题:因子分解(RSA 密码系统)、离散对数(Diffie-Hellman、DSA)和椭圆曲线离散对数问题(EC-Diffie-Hellman、ECDSA 等)。

  2. 虽然我们愿意相信我们喜欢的那些问题从根本上来说是“难的”,但我们知道事实并非如此。研究者已经设计出算法(Kurt Pan注:原文链接到Shor算法。)可以非常高效地(即在多项式时间内)解决所有上述问题——前提是有人知道如何构建一台足够强大的量子计算机来运行攻击算法。幸运的是,这样的计算机还没有被制造出来!

  3. 尽管量子计算机还没有强大到足以破解我们的公钥密码,但仅仅是未来的量子攻击的威胁已经激励工业界、政府和学术界联手以“护戒使者”式的方式(Kurt Pan 注:原文链接为NIST PQC竞赛,用《魔戒》中人类、精灵、矮人、巫师、霍比特人联合组成的护戒分队进行比喻。)现在就开始进行应对。这不仅仅是为了让我们的系统面向未来:即使量子计算机需要几十年的时间来建造,未来的量子计算机也可能破解我们今天发送的加密消息!

  4. 这个联盟的一个显著成果是 NIST 的后量子密码学 (PQC) 竞赛:这是一项旨在标准化 “后量子”密码方案的公开竞赛。至关重要的是,这些方案必须基于不同的数学问题——尤其显著的是,这些问题要似乎允许有高效的量子解法。
  5. 在这组新方案中,最流行的一类方案是基于与称为的数学对象相关的问题。 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 节, 其中更详细地给出了攻击参数。

第3.1节

这部分将输入的LWE问题(现在LWE维度被称为image.png而不是image.png,并且作者设置image.png以便于分析)与选择自错误分布的密钥,但是选择为攻击者所选择的image.png个值的问题相对应。

基本上为, 带有参数image.png的错误分布image.png的输入问题

image.png

与问题

image.png

之间存在映射关系。



第3.2节

然后选择奇互素值image.png , 使得

image.png


其中image.png。对于较小的image.png值,可以预期image.png会等于1或2,除非选择image.png(从而image.png)为很大的值。因此,image.png的选择也会影响需要从多少个LWE样本(即image.png)开始(请参见下面关于增加image.png对具体LWE问题实例意味着什么的评论)。


秘密密钥的image.png个部分被选择为image.png。现在的关键是求解方程

image.png

,其中向量 b 具有特殊形式

image.png

该算法的工作原理是猜测image.png。引理 3.6 告诉我们, 对于image.png至少有image.png个这样的选择。事实上, 有很高概率有

image.png

要点一:这意味着此时的复杂度似乎至少为image.png因为需要从大约image.png大小的范围中猜测image.png


第3.3节

之后,3.3 节定义了一系列常量和约束,使主量子子程序能够工作,并成功解决底层的LWE 问题。

约束 C. 3 似乎是一个问题。对于 image.png的猜测值, 我们需要找到一个值image.png使得

image.png

并且我们需要选择image.png使得

image.png

我能让事情按顺序解决的唯一方法如下(这几乎就是作者所建议的):

  1. image.png选择一个值。

  2. 设置image.png

  3. 使用引理image.png中的界来猜测 image.png的值, 即 image.png。我们有约束 image.png, 因此只需要考虑image.png的粗略估计值image.png 

  4. 现在将 image.png分解为互素的 image.png以获得某个 image.png值。

  5. 设置image.png
  6. 如果image.png则拒绝。也许我们甚至不用拒绝这些值?


尽管使用此方法, 我仍无法使image.png条件成立。注意作者在论文中的示例是 image.png而不是 image.png。所以也许这是一个拼写错误!

假设我们猜测的image.png是素数, 并且是一个正确的值。然后我们必须有image.pngimage.png。此时似乎没有理由应该有 image.png 。还会有

image.png

这显然不能成立。因此, 为了使分解为image.png有意义, 我们确实需要image.png为特殊值。所以有些事情看起来很奇怪!


image.png相关的更新

正如 Vadim Lyubasevksy 向我指出的那样, 论文中考虑的问题实际上是针对通用 LWE的, 即针对可能无限的或大量的样本。在现实世界的密码系统中, 有固定数量的基本样本, 特别是通常我们只给定image.png这样的样本。

如果攻击需要更多样本, 那么我们需要根据给定的样本生成这些样本。这是通过组合现有样本的小线性组合来完成的。但我们不能在线性组合中使用太小的值, 否则会将已知的小向量引入到得到的之后算法将对其进行求解的格中;也就是说,它最终会求解你已经知道的向量。因此,我们需要选择乘数较小但又不能太小的组合。但这本身就会放大噪声(即image.png值)。这使得攻击不太实用。

例如, 假设我们输入的 LWE 样本是对image.png方阵image.png

image.png

然后, 为了生成新样本, 可以将右侧的方程乘以一个矩阵image.png, 该矩阵包含小值, 不是太稀疏, 但小值也不是太小。即将形成系统

image.png

但现在噪声值已从image.png上升到image.png。这会增加image.png的值, 从而增加上面的image.png值, 从而增加攻击的复杂度。


Nigel Smart 4月17日更新

https://nigelsmart.github.io/LWE.html

所以昨天我遇到了条件 C. 3 的两个问题。这些都通过和一镭的沟通得到了一定的解决。

重新审视条件 C.3

了解这些后, 考虑假设image.png或假设image.png已固定的这两个修复后,让我们重新审视 C. 3 并提出一种算法,


选项 A:设置 image.png

  1. image.png选择一个值 (待定)。
  2. image.png选择一个值, 例如image.png
  3. 设置image.png, 即image.png
  4. 根据image.png选择奇互素值image.png(也与image.png互素 )。

问题是,我们应该选择多大的image.png?

同样,我们知道image.png,并且也知道(假设image.pngimage.png的大小将由image.png项主导。由于image.pngimage.png相比很小,我们基本上会得到类似这样的东西

image.png

回想一下, 对 Kyber 和 BGV ,image.png, 对Dilithiumimage.png, 对TFHEimage.png如上所述,这是假设image.png对需要生成更多样本不需要增加,  因此对image.png的这些假设是最好的可能情况。

image.png时,需要

image.png

即,

image.png

注意, 要得到image.png,需要image.png比这里的image.png大。不管怎么想, 这都是非常大量的 LWE 样本数。

image.png时,我们得到

image.png

image.png

注意, 这里总是会得到image.png, 无论image.png值如何。

选项 B:设置 image.png


  1. 选择image.png。无论如何选择image.png
  2. image.png选择一个值, 例如image.png
  3. 设置image.png,即image.png
  4. 选择奇互素值image.png(也与image.png互素)。

现在的问题是,我们应该选择多大的互素值image.png?

同样, 我们知道image.png并且我们也知道(假设image.pngimage.png的大小将由image.png项主导。由于image.png相比image.png很小,我们基本上会得到类似下式的东西

image.png

所以

image.png

使用image.png,需要

image.png

image.png

但是要获得image.png这样的互素值我们需要image.png, 即image.png。这又是大量的样本数。

使用image.png,需要

image.png

image.png

任意image.png值都会导致这样的互素值存在。


C. 3小节的总结

通过削弱近似因子, 我们可以为互素的image.png和值image.png选择实用值。我们看到, 对于 Kyber、Dilthium 和 BGV, 需要的样本数量image.png将非常大才能选择此类互素值, 但是对于 TFHE,  image.png值非常大,这种互素数的存在是直接的, 因为这迫使image.png确实非常大。

第二个要点:对于较小的image.png值, 使攻击起作用所需的样本数量确实会非常大。

继续第 3.3 节

选择了image.png的值后, 我们就固定了对image.png的猜测。但这个猜测可能是错误的。事实上, 其正确的概率约为

image.png

因此, 我们需要继续执行攻击, 通过随机化输入样本来调整参数(如上所述)。直到攻击起作用。

所以需要重申上述的要点一。要点一(回顾),复杂度至少为image.png因此, 如果image.png很大, 比如在TFHE中, 这已经是不行的了。我们继续假设image.png是正确的。因此, 选择互素值后, 需要为image.png选择一个值, 论文称该值应该是奇数以及 image.png。目前我们假设它已被选择。

然后设置

image.png

现在我们需要确定image.png以确保条件C.2满足,定义为

image.png

注意到

image.png

所以条件 C. 1 已经满足。条件 C. 1 中唯一不满足的是image.png

然后需要从条件 C. 4 中选择image.png的值。相关的不等式是

image.png

image.png

注意第二个不等式蕴含下式

image.png

image.png

代入我们上面的值, 有

image.png

image.png值我们可以忽略 。

要点三:注意这意味着该攻击不适用于 TFHE 的标准参数, 因为image.png, 并且TFHE中乘以image.png得到的image.png太小, 无法应用攻击。

要点四:该攻击不适用于 Kyber、Dilithium 或 BGV,因为此处所需的image.png的大值(如上所述)也意味着这些方案中使用的image.png值太小了。

在条件 C. 7 中,image.png的值实际上被选择为

image.png

最后要选择的参数是image.png, 它是通过

image.png

从条件 C. 5 中选择的。

然后还有一些额外的条件, 即条件 C. 6 和 C.7, 它们定义了各种参数的范围。我的理解是这些会影响算法获得的近似因子。


4月17日总结

  1. 该算法肯定需要image.png次重复。因此对于大image.png(TFHE) 这是不可行的。(要点一)
  2. 对于较小的image.png值(Kyber、Dilithium、BGV),该算法需要大量的 LWE 样本image.png。 (要点二)
  3. 该算法需要image.png, 这要么因为image.png很大 (TFHE), 要么因为image.png很大(根据上个要点,因为image.png很小)而太高。(要点三/四)
  4. 从公钥方案中拥有的固定数量的样本中生成大量样本, 会生成比此处考虑的更大的image.png值。这使得攻击不太实用。




上一篇:MEPs call for ‘urgent action’ to implement post-quantum encryption standards

下一篇:美国共和党正式提出国防量子加速法案

发表评论:

评论记录:

未查询到任何数据!

免责声明

本站的内容为ABC爱好者收集编辑,仅供参考学习,不能作为实际操作使用!

浏览本站后,你的任何尝试都与站长本人无关,盈亏自负,也请为自己的行为负责。

本站提及的所有内容和项目,请自行判断风险,不作为任何投资建议。

本站除捐助外,不存在任何的交易以及售卖行为,请擦亮眼睛谨防被骗!

投资有风险,交易需谨慎。如果你无法认同上面的内容,请关闭本页面并停止浏览本站!

免责声明

微信扫一扫

微信联系
返回顶部