【译文】关于陈一镭算法的简短文章

| 2024-04-18

如果你是一个正常人–也就是说，一个不痴迷于关注最新密码学新闻的人–你可能错过了上周的密码学重磅新闻。这条新闻是由陈轶磊撰写的新电子版论文 “Quantum Algorithms for Lattice Problems 网格问题的量子算法 “发布的，它激怒了密码学研究界。格子和量子算法设计方面的专家们正在对这一成果进行评估（需要说明的是，我不是专家！），但如果这一成果成立，应用密码学界将会度过糟糕的一天/一周/一月/一年。

与其长篇大论，不如在此用五个要点简要介绍一下背景情况。

(1) 密码学家喜欢把现代公钥加密方案建立在被认为 “很难 “的数学问题之上。在实践中，我们需要具有特定结构的问题：我们可以为持有秘钥或 “陷阱门 “的人构建有效的解决方案，但也承认没有秘钥的人没有有效的解决方案。虽然我们考虑过很多问题（但往往都放弃了），但今天我们使用的大多数方案都基于三个问题：因式分解（RSA 密码系统）、离散对数（Diffie-Hellman、DSA）和椭圆曲线离散对数问题（EC-Diffie-Hellman、ECDSA 等）。

(2) 虽然我们愿意相信我们最喜欢的问题从根本上来说是 “困难 “的，但我们知道这并不是真的。研究人员已经设计出了能相当高效地（即在多项式时间内）解决所有这些问题的算法–前提是有人能想出办法，制造出足以运行攻击算法的量子计算机。幸运的是，这样的计算机还没有制造出来！

(3) 尽管量子计算机还没有强大到足以破解我们的公钥密码，但仅仅是未来量子攻击的威胁，就已经激发了产业界、政府和学术界联合起来，以 Fellowship-of-the-Ring-style 来解决当前的问题。这不仅仅是为了让我们的系统面向未来：即使量子计算机的制造需要几十年的时间，未来的量子计算机也可能破解我们今天发送的加密信息！

(4) 这项奖学金的一个显著成果就是 NIST 的后量子密码学（PQC）竞赛：这是一项旨在规范 “后量子 “密码方案的公开竞赛。至关重要的是，这些方案必须基于不同的数学问题–最值得注意的是，这些问题似乎并不承认有效的量子解决方案。

(5) 在这一系列新方案中，最流行的方案是基于与称为网格的数学对象相关的问题。NIST 批准的基于晶格问题的方案包括 Kyber 和 Dilithium（我最近写过一篇文章）。网格问题也是几种高效全同态加密（FHE）方案的基础。

这些背景为新成果的产生奠定了基础。

陈博士的预印本（尚未经过同行评审）声称，一种新的量子算法可以高效地解决具有特定参数的网格中的 “最短独立向量问题”（SIVP，以及 GapSVP）。如果这一结果成立，那么未来的量子计算机就能破解依赖于这些问题特定实例的难易程度的方案（但有许多重要的注意事项）。好消息是，即使结果是正确的，易受攻击的参数也是非常具体的：陈的算法并不能立即应用于最近标准化的 NIST 算法，如 Kyber 或 Dilithium。此外，该算法的具体复杂度也不是一目了然的：即使量子计算机出现了，运行它也可能是不切实际的。

但是，在我们的领域有这样一句话：攻击只会变得更好。如果陈博士的研究成果能够得到改进，那么量子算法就会淘汰整整一代基于网格的 “后量子 “方案，从而迫使密码学家和产业界重新回到绘图板上。

换句话说，这既是一项伟大的技术成果，也可能是一场轻微的灾难。

如前所述：我既不是基于网格的密码学专家，也不是量子计算专家。这些领域的专家们正忙于验证这篇报道：经过详细检查，许多重大成果都不尽人意。对于那些想了解最新进展的人来说，奈杰尔-斯马特（Nigel Smart）在这里写了一篇不错的文章，虽然没有讨论量子算法的正确性（见底部的更新），但确实谈到了对 FHE 和 PQC 方案的可能影响（TL;DR：对某些 FHE 方案不利，但确实取决于算法运行时间的具体细节）。这里还有一个关于论文中发现的一个 “错误 “的简短说明，作者似乎很快就解决了这个问题。

直到本周，我还打算再写一篇关于复杂性理论、网格以及这一切对应用密码学的意义的冗长文章。但现在，我希望你们能原谅我，让我再坚持一下。

本文文字及图片出自 A quick post on Chen’s algorithm