著名的密码算法得到升级

在我们日益数字化的生活中，安全取决于密码学。发送私人消息或在线支付账单，您需要依靠旨在保密您的数据的算法。当然，有些人想揭开这些秘密，因此研究人员致力于测试这些系统的强度，以确保它们不会在聪明的攻击者手中崩溃。

这项工作中的一个重要工具是 LLL 算法，以 1982 年发布该算法的研究人员 Arjen Lenstra、Hendrik Lenstra Jr. 和 László Lovász 的名字命名。 LLL 及其许多后代在某些情况下可以破解加密方案；研究它们的行为方式有助于研究人员设计不易受到攻击的系统。该算法的才能超出了密码学的范围：它也是计算数论等高级数学领域的有用工具。

多年来，研究人员不断改进 LLL 的变体，使该方法更加实用——但只是在一定程度上。现在，两位密码学家构建了一种新的 LLL 式算法，其效率显着提高。这项新技术在2023 年国际密码学会议上获得了最佳论文奖，扩大了计算机科学家和数学家可以使用类似 LLL 的方法的场景范围。

“这真的令人兴奋，”密歇根大学密码学家克里斯·佩克特（Chris Peikert）说，他没有参与这篇论文。他说，几十年来，该工具一直是研究的焦点。 “当一个已经研究了很长时间的目标表明仍然有惊喜可以发现时，这总是很好的。”

这是 LLL 的一项工作：给它（或其兄弟）一个多维晶格的基础，它会吐出一个更好的晶格。这个过程称为晶格基约简。

这一切与密码学有什么关系？事实证明，在某些情况下，破解密码系统的任务可以被重新定义为另一个问题：在格中找到相对较短的向量。有时，该向量可以从 LLL 式算法生成的简化基中提取。这一策略帮助研究人员推翻了表面上似乎与晶格无关的系统。

从理论上讲，原始的 LLL 算法运行速度很快：运行时间不会随着输入的大小（即格子的维度和数组中数字的大小（以位为单位））呈指数级增长。基向量。但它确实会随着多项式函数的增加而增加，而且“如果你真的想这样做，多项式时间并不总是那么可行，”荷兰国家研究机构 CWI 的密码学家Léo Ducas说。

实际上，这意味着原始 LLL 算法无法处理太大的输入。 “数学家和密码学家希望能够做更多的事情，”加州大学圣地亚哥分校的博士生基根·瑞安 (Keegan Ryan)说。研究人员致力于优化 LLL 式算法以适应更大的输入，通常会取得良好的性能。尽管如此，一些任务仍然顽固地遥不可及。

这篇新论文由 Ryan 和他的顾问Nadia Heninger撰写，结合了多种策略来提高其 LLL 式算法的效率。一方面，该技术使用递归结构将任务分解为更小的块。另一方面，算法仔细管理所涉及数字的精度，在速度和正确结果之间找到平衡。这项新工作使研究人员可以减少数千维晶格的基数。

过去的工作也遵循了类似的方法： 2021 年的一篇论文也结合了递归和精度管理来快速处理大型格，但它仅适用于特定类型的格，而不适用于密码学中重要的所有格。新算法在更广泛的范围内表现良好。 “我真的很高兴有人做到了，”PQShield 公司的密码学研究员、2021 版本的作者Thomas Espitau说。他说，他的团队的工作提供了“概念验证”。新的结果表明“你可以以合理的方式进行非常快速的晶格缩减。”

这项新技术已经开始被证明是有用的。法国国家研究所 Inria 的数学家Aurel Page表示，他和他的团队已经对该算法进行了改进，以解决一些计算数论任务。

LLL 风格的算法还可以在与基于格的密码系统相关的研究中发挥作用，该系统旨在即使在未来拥有强大的量子计算机的情况下也能保持安全。它们不会对此类系统构成威胁，因为摧毁它们需要找到比这些算法所能实现的更短的向量。但波尔多大学密码学家Wessel van Woerden表示，研究人员所知的最好的攻击是使用 LLL 风格的算法作为“基本构建块”。在研究这些攻击的实际实验中，该构建块可以减慢一切速度。使用新工具，研究人员或许能够扩大他们在攻击算法上运行的实验范围，从而更清楚地了解它们的表现。

广达正在进行一系列调查，以更好地服务我们的受众。参加我们的计算机科学读者调查，您将有机会赢得免费的广达商品。