解决难题的最佳方法是什么？这是计算机科学子领域“计算复杂性理论”的核心问题。这是一个很难回答的问题，但是翻转一下，就会变得更容易。最糟糕的方法几乎总是反复试验，其中包括插入可能的解决方案，直到找到可行的解决方案。但对于某些问题，似乎根本就没有其他选择——最糟糕的方法也是最好的方法。

研究人员长期以来一直想知道情况是否真的如此，说 拉胡尔·伊兰戈，麻省理工学院研究复杂性理论的研究生。 “你可能会问，‘是否存在猜测和检查最适合解决的问题？’”

复杂性理论学家研究了许多计算问题，即使是困难的问题也常常承认某种巧妙的程序或算法，这使得找到解决方案比纯粹的试错更容易一些。少数例外是所谓的压缩问题，其目标是找到数据集的最短描述。

但去年 11 月，两组研究人员 独立地 发现 另一种用于压缩问题的算法——比检查所有可能的答案稍快一些。新方法的工作原理是采用密码学家 25 年前发明的算法来解决不同的问题。只有一个限制：您需要根据数据集的大小定制算法。

“它们确实是美丽且重要的结果，”说 埃里克·阿伦德，罗格斯大学理论计算机科学家。

定义硬度

这些新结果是对一个问题的最新研究，这个问题最早是在苏联研究的，早在复杂性理论出现之前。 “在我上小学之前，俄罗斯人就已经制定了这个，”阿伦德说。

这些苏联研究人员研究的具体计算问题称为最小电路尺寸问题，类似于计算机硬件设计者一直面临的问题。如果您获得了电子电路应如何工作的完整规范，您能找到能够完成这项工作的最简单的电路吗？没有人知道如何在没有“perebor”（俄语单词大致相当于“穷举搜索”）的情况下解决这个问题。

最小电路尺寸问题是压缩问题的一个例子。您可以使用一长串位（0 和 1）来描述电路的行为，然后询问是否有一种方法可以使用更少的位来重现相同的行为。检查所有可能的电路布局所需的时间会随着字符串中位数的增加而呈指数增长。

这种指数增长是硬计算问题的定义特征。但并非所有难题都同样困难——有些问题的算法比穷举搜索更快，尽管它们的运行时间仍然呈指数级增长。用现代术语来说，最重要的问题是是否存在针对压缩问题的此类算法。

1959 年，一位名叫 Sergey Yablonsky 的著名研究人员声称已经证明穷举搜索确实是解决最小电路尺寸问题的唯一方法。但他的证明留下了一些漏洞。当时一些研究人员注意到了这些缺陷，但亚布隆斯基的影响力足以阻止大多数其他人研究佩雷博尔问题。

在接下来的几十年里，很少有研究人员研究压缩问题，而 Perebor 问题主要被认为是复杂性理论史前史中的一个脚注。最近，在研究人员发现压缩问题与密码学基础之间存在奇怪的联系之后，这个问题才得到了广泛的关注。

单向行驶

现代密码学使用困难的计算问题来保护秘密消息。但计算难度只有在不对称的情况下才有用——如果很难破译编码消息，但首先编码消息并不困难。

在每种加密方案中，这种不对称性的根源是一种称为单向函数的数学对象，它将输入位串转换为相同长度的输出串。给定单向函数的输入，很容易计算输出，但给定输出很难反转该函数 - 即对其进行逆向工程并恢复输入。

“密码学家真的希望拥有非常非常高效的可计算单向函数，而且这些函数真的非常难以逆，”阿伦德说。许多数学函数似乎都具有这种性质，而求逆这些函数的困难源于解决不同计算问题的明显困难。

不幸的是，密码学家不确定这些函数中的任何一个是否真的很难反转——事实上，真正的单向函数可能不存在。这种不确定性仍然存在，因为复杂性理论家已经 奋斗了50年 证明看似困难的问题确实很难。如果不是这样，并且如果研究人员发现了解决这些问题的超快算法，这对密码学来说将是灾难性的——就像突然在单向街道上为两个方向超速行驶的汽车分配路线一样。

尽管对计算难度的全面理解仍然难以捉摸，但密码学家最近在单向函数的统一理论方面取得了令人兴奋的进展。 2020 年，特拉维夫大学密码学家迈出了一大步 拉斐尔山口 和他的研究生 刘彦一 证明单向函数是 密切相关 一个特定的压缩问题，称为有时间限制的柯尔莫哥洛夫复杂度问题。

如果这个问题对于大多数输入来说确实很难解决，那么 Pass 和 Liu 的结果就提供了一种如何构建可证明困难的单向函数的方法——即使其他计算问题变得容易得多，该函数也能保证安全。超出研究人员的预期。但如果有一种快速算法可以解决有时间限制的柯尔莫哥洛夫复杂性问题，那么密码学就注定失败，任何函数都可以轻松反转。基于这个问题的难度的单向函数是可能的最安全的函数——一种统治所有问题的单向函数。

基于数据结构

Pass 和 Liu 的发现是一系列研究的最新篇章，这些研究利用复杂性理论来更好地理解密码学的基础。但它也提出了一种反转这种关系的方法：有时间限制的柯尔莫哥洛夫复杂性问题和函数反演之间的等价性意味着对任一问题的见解可以揭示更多关于另一个问题的信息。几十年来，密码学家一直在研究函数求逆算法，以更好地理解其加密方法的弱点。研究人员开始想知道这些算法是否可以帮助回答复杂性理论中古老的问题。

与许多计算问题一样，函数反演可以通过穷举搜索来解决。给定一个输出字符串，只需将所有可能的输入插入到函数中，直到找到能产生正确答案的输入。

1980 年，密码学家 Martin Hellman 开始研究是否可以做得更好——这与几十年前苏联数学家就压缩问题提出的问题相同。海尔曼 发现 是的，这是可能的——只要您愿意提前投入一些额外的工作，使用称为数据结构的数学对象。

数据结构本质上是一张表，存储有关要反转的函数的信息，构建数据结构需要针对某些战略选择的输入计算函数的输出。所有这些计算“可能需要很长时间”，他说 瑞安·威廉姆斯（Ryan Williams），麻省理工学院的复杂性理论家。 “但我们的想法是，这是一次、一劳永逸的。”如果您尝试在给定许多不同输出的情况下反转同一函数（例如，解码以相同方式加密的许多不同消息），那么提前完成这项工作可能是值得的。

当然，存储额外的信息需要空间，因此将这种策略发挥到极致，您最终可能会得到一个无法安装在任何计算机上的快速程序。 Hellman 设计了一种巧妙的数据结构，使他的算法能够比穷举搜索稍微快一点地反转大多数函数，而不会占用太多空间。然后在 2000 年，密码学家 Amos Fiat 和 Moni Naor 扩展 Hellman 对所有函数的论证。

2020 年帕斯和刘的突破之后，这些旧的结果突然变得新的相关性。 Fiat-Naor 算法可以比穷举搜索更快地反转任意函数。它也可以解决压缩问题吗？

不穿制服

第一个提出这个问题的研究人员是复杂性理论家 拉胡尔桑塔南 牛津大学教授和他的研究生 任翰林。他们这样做是在 2021纸 证明压缩问题和函数反演的相互关系比研究人员意识到的更加紧密。

Pass和Liu证明，如果有时间限制的Kolmogorov复杂度问题是困难的，那么函数反演也一定是困难的，反之亦然。但问题可能很困难，但仍然需要比穷举搜索更好的解决方案。 Santhanam 和 Ren 表明，一个问题是否需要穷举搜索与另一个问题是否需要穷举搜索之间存在密切的联系。

他们的结果对研究人员经常研究的两大类算法（称为“均匀”和“非均匀”算法）有不同的影响。统一算法对每个输入都遵循相同的过程——例如，用于对数字列表进行排序的统一程序，无论列表中有 20 个条目还是 20,000 个条目，都将以相同的方式工作。相反，非均匀算法对不同长度的输入使用不同的过程。

Fiat-Naor 算法使用的数据结构始终针对特定功能进行定制。要反转扰乱 10 位字符串的函数，您需要一个与反转扰乱 20 位字符串的函数所需的数据结构不同的数据结构，即使扰乱是以类似的方式完成的。这使得 Fiat-Naor 成为一种非均匀算法。

Santhanam 和 Ren 的结果表明，有可能将 Fiat-Naor 算法转变为解决压缩问题的算法。但将算法从一个问题应用到另一个问题并不简单，他们也没有进一步研究这个问题。

一年后，帕斯在一次庆祝 Naor 对密码学贡献的研讨会上听到 Fiat 关于经典算法的演讲后，偶然发现了同样的想法。 “从那时起，使用函数反转的想法就一直在我的脑海中，”他说。后来他开始与特拉维夫大学的研究人员认真研究这个问题 诺姆·马佐尔.

与此同时，在访问加州伯克利西蒙斯计算理论研究所时，Ilango 在与包括 Santhanam 在内的其他研究人员讨论后，受到启发，开始解决这个问题。 “这是一次非常偶然的谈话，你只是在乱扔东西，”桑塔南说。伊兰戈后来与威廉姆斯联手， 平原秀一，东京国家信息研究所的复杂性理论家。

困难的部分是弄清楚如何将 Fiat-Naor 算法核心的数据结构嵌入到解决压缩问题的非均匀算法中。有一个执行这种嵌入的标准程序，但它会减慢算法速度，消除其相对于穷举搜索的优势。两个团队找到了更聪明的方法来合并 Fiat-Naor 数据结构，并获得了适用于所有输入且比穷举搜索更快的压缩问题算法。

两种算法的细节略有不同。即使将搜索限制为最简单的可能性，Ilango 和他的合著者提出的方法也比穷举搜索更快，并且它适用于所有压缩问题 - 受时间限制的 Kolmogorov 复杂性、最小电路尺寸问题以及许多其他问题。但两种算法的核心思想是相同的。密码学技术已经证明了它们在这个新领域的价值。

反演收敛

非均匀算法的新证明提出了一个自然的问题：均匀算法怎么样？有没有一种方法可以比使用它们进行穷举搜索更快地解决压缩问题？

最近的一系列结果表明，任何此类算法都相当于用于反转任意函数的统一算法——密码学家几十年来一直在寻求这种算法，但未能成功。正因为如此，许多研究人员发现这种可能性不大。

“我会非常惊讶，”桑塔南说。 “这需要一个全新的想法。”

但阿伦德表示，研究人员不应忽视这种可能性。 “对我来说，一个很好的工作假设是，如果有一种非统一的方式来做某事，那么很可能存在一种统一的方式，”他说。

不管怎样，这项工作让复杂性理论家对密码学中的老问题重新产生了兴趣。 尤瓦尔·伊沙伊（Yuval Ishai）以色列海法理工学院的密码学家表示，这才是最令人兴奋的地方。

“我真的很高兴看到不同社区之间的利益趋同，”他说。 “我认为这对科学很有好处。”