这是ll的工作:给它(或它的兄弟)一个多维晶格的基础，它会吐出一个更好的。这个过程被称为格基约简。
这和密码学有什么关系?事实证明，在某些情况下，破解密码系统的任务可以被重新定义为另一个问题:在晶格中找到一个相对较短的向量。有时候，这个向量可以从lll算法生成的约简基中提取出来。这一策略帮助研究人员推翻了表面上看起来与晶格关系不大的系统。
从理论上讲，最初的LLL算法运行得很快:运行所需的时间不随输入的大小(即晶格的维数和基向量中数字的大小(以位为单位)呈指数级增长。但它确实会以多项式函数的形式增加，“如果你真的想这么做，多项式时间并不总是那么可行，”荷兰国家研究机构CWI的密码学家lsamao Ducas说。
在实践中，这意味着最初的ll算法不能处理太大的输入。“数学家和密码学家希望有能力做更多的事情，”加州大学圣地亚哥分校(University of California, San Diego)的博士生基根·瑞安(Keegan Ryan)说。研究人员致力于优化lll风格的算法，以适应更大的输入，通常会获得良好的性能。尽管如此，一些任务仍然难以实现。
这篇由Ryan和他的顾问Nadia Heninger撰写的新论文结合了多种策略来提高其lll风格算法的效率。首先，该技术使用递归结构将任务分解为更小的块。另一方面，该算法仔细管理所涉及数字的精度，在速度和正确结果之间找到平衡。这项新工作使研究人员能够减少具有数千维的晶格的基。
过去的工作也采用了类似的方法:2021年的一篇论文也结合了递归和精度管理来快速处理大型格，但它只适用于特定类型的格，而不是所有在密码学中重要的格。新算法在更广的范围内表现良好。“我真的很高兴有人做到了，”PQShield公司的密码学研究员、2021年版本的作者之一托马斯·埃斯皮托(Thomas Espitau)说。他说，他的团队的工作提供了一个“概念证明”;新的结果表明，“你可以用一种合理的方式进行非常快速的晶格缩减。”
这项新技术已经开始证明是有用的。法国国家研究机构Inria的数学家Aurel Page说，他和他的团队已经对该算法进行了调整，用于一些计算数论任务。
lll风格的算法也可以在与基于格的密码系统相关的研究中发挥作用，这些系统旨在即使在未来拥有强大的量子计算机也能保持安全。它们不会对这样的系统构成威胁，因为要摧毁它们需要找到比这些算法更短的向量。但波尔多大学(University of Bordeaux)的密码学家韦塞尔·范·韦尔登(Wessel van Woerden)说，研究人员所知道的最好的攻击都是使用lll风格的算法作为“基本构建块”。在研究这些攻击的实际实验中，这种构建块可以减慢一切。使用这个新工具，研究人员可能能够扩大他们对攻击算法进行实验的范围，从而更清楚地了解它们的表现。
《量子杂志》是西蒙斯基金会出版的独立编辑刊物，其使命是通过报道数学、物理和生命科学的研究发展和趋势，提高公众对科学的理解。
