使难题更容易的密码学技巧
原文： https://www.quantamagazine.org/cryptography-tricks-make-a-hard-problem-a-little-easier-20240418/
作者：Ben Brubaker
译者：Kurt Pan
对于一个重要的问题，似乎辛苦地尝试每一种可能性就是最好的方法。现在，研究者已经证明了有更好的方法。
解决难题的最佳方法是什么？这是计算机科学的一个子领域——计算复杂性理论所关心的问题。这是一个难以回答的问题，但如果反过来看，就变得更容易了。最差的方法几乎总是试错法，即尝试可能的解，直到找到一个有效的。但对于一些问题，似乎就没有其他选择——最差的方法也是最好的方法。
研究人员长期以来一直在思考是否真的是这样的，麻省理工学院的研究生 Rahul Ilango 说：“你可以问，‘是否存在猜测和检查就是最优的问题？’”
复杂性理论家已经研究了许多计算问题，甚至困难的问题通常都会有一些巧妙的程序，或者算法，使得找到解比纯粹的试错要容易一些。少数的一个例外就是所谓的压缩问题，其目标是找到数据集的最短描述。
但是去年 11 月，两组研究者独立地发现了对压缩问题另外的算法——一种比检查所有可能答案稍微快一点的算法。这种新方法是通过改造密码学家 25 年前为解决不同问题而发明的算法而得到的。只有一个限制：你需要根据你的数据集大小来定制算法。
https://eccc.weizmann.ac.il/report/2023/171/ https://eccc.weizmann.ac.il/report/2023/175/
"真的是很美丽且重要的结果，"Rutgers大学的理论计算机科学家Eric Allender说。
定义困难性
这些新结果其实是对一个早在复杂性理论出现之前就在苏联首次研究的问题的最新研究。"在我上小学之前，俄罗斯人就在研究这个，"Allender 说。
苏联研究者研究的那个计算问题，称为最小电路尺寸问题，类似于计算机硬件设计师经常面临的问题。如果给你一份电子电路应该如何运行的完整规格书，你能找到最简单的能完成任务的电路吗？没有人知道如何在不用“perebor”（一个俄语词，大致相当于“穷举搜索”）的情况下解决这个问题。
最小电路尺寸问题是一个压缩问题的例子。你可以用一长串的比特——0 和 1——来描述一个电路的行为，然后问是否有一种方法可以用更少的比特来复现同样的行为。检查所有可能的电路布局需要的时间随着串中比特数的增加而呈指数增长。
这种指数增长是一个困难计算问题的典型特征。但并非所有的困难问题都一样困难——有些问题有比穷举搜索更快的算法，尽管它们的运行时间仍然呈指数增长。用现代术语来说，perebor 问题就是是否存在任何对压缩问题的这样的算法。
1959 年，一位著名的研究者Sergey Yablonsky声称他已经证明了穷举搜索确实是解决最小电路尺寸问题的唯一方法。但他的证明留有一些漏洞。一些研究者当时就注意到了这些漏洞，但Yablonsky的影响力足以大到劝退大多数其他人去研究 perebor 问题了。
在随后的几十年里，很少有研究者去研究压缩问题，perebor问题则被认为是复杂性理论前史中的一个脚注。对这个问题的广泛关注直到最近才出现，这是在研究者发现了压缩问题与密码学的基础之间的一个奇特联系之后。
单行道
现代密码学使用计算困难问题来保护秘密信息。但是，计算困难性只有在它是不对称的情况下才有用 - 解密密文很难，但一开始对消息加密并不困难。
在每一个密码学方案中，这种不对称性的起源是一个被称为单向函数的数学对象，它将输入的比特串转换为等长的输出比特串。给定一个单向函数的输入，很容易计算输出，但给定一个输出，很难对函数求逆 - 也就是说，很难对其进行逆向工程并恢复输入。
“密码学家真的希望有非常非常高效可计算的单向函数，而且这些函数非常非常难以求逆，” Allender 说。许多数学函数似乎具有这种属性，而这些函数的求逆难度则源于解决不同计算问题的明显困难性。
遗憾的是，密码学家并不确定这些函数是否真的难以求逆 - 实际上，真正的单向函数可能并不存在。这种不确定性一直存在，复杂性理论家们已经努力了50年来证明看似困难的问题是真的很难。如果它们其实并不困难，而且研究者发现了这些问题的超快速算法，那将对密码学产生灾难性的影响 - 就像突然在单行道上双向行驶的超速汽车一样。
尽管仍然难以达到对计算困难性的全面理解，但密码学家最近在单向函数的统一理论方面已经取得了令人兴奋的进展。2020年，Tel Aviv大学的密码学家Rafael Pass和他的研究生Yanyi Liu证明了单向函数与一个特定的压缩问题——时间有界Kolmogorov复杂度问题——有着密切的联系。
如果那个问题对于大多数输入来说确实很难解决，那么Pass和Liu的结果就提供了一种如何构造可证明困难的单向函数的方法——即使其他计算问题比研究者预期的要容易得多，这个函数也能保证是安全的。但是，如果存在一个快速算法来解决时间有界Kolmogorov复杂度问题，那么密码学就在劫难逃，任意函数都可以轻易地求逆。基于这个问题的困难性的单向函数是可能的最安全的函数——一个统御众函数的单向函数。
数据结构上的构造
Pass 和 Liu 的发现是使用复杂性理论来更好地理解密码学基础这一研究路线的最新篇章。但这也给出了一种反转这种关系的方法：时间有界Kolmogorov复杂度问题与函数求逆的等价性意味着对任一问题的洞察都可以揭示更多关于另一问题的信息。密码学家已经研究了几十年的函数求逆算法，以更好地理解他们的加密方法中的弱点。研究者开始思考这些算法是否也可以帮助回答复杂性理论中的古老问题。
像许多计算问题一样，函数求逆可以通过穷举搜索来解决。给定一个输出串，只需将所有可能的输入代入到函数中，直到找到能得到正确答案的那一个。
1980 年，密码学家Martin Hellman开始研究是否有可能做得更好 - 这是和苏联数学家几十年前对压缩问题提出的同样的问题。Hellman发现，是的，这是可能的 - 只要你愿意提前做一些额外的工作，使用被称为数据结构的数学对象。
M. Hellman, "A cryptanalytic time-memory trade-off," in IEEE Transactions on Information Theory, vol. 26, no. 4, pp. 401-406, July 1980, http://ieeexplore.ieee.org/document/1056220/
数据结构本质上是一个存储有关待求逆函数信息的表，构造一个数据结构需要计算函数在某些策略性选择的输入上的输出。所有这些计算“可能需要很长时间，”MIT的复杂性理论家Ryan Williams说。“但是，这里的想法是只需计算一次，一劳永逸。”如果你试图给定许多不同的输出去求逆同一个函数——比如，对用同一种方式加密的许多不同的消息解密——提前做这项工作可能是值得的。
当然，存储那些额外的信息需要空间，所以如果将这种策略推向极端，你可能会得到一个快速的程序，但它无法在任何计算机里运行。Hellman设计了一个巧妙的数据结构，使他的算法能够比穷举搜索稍微快一些地求逆大多数函数，而不会占用太多额外的空间。然后在2000年，密码学家 Amos Fiat 和 Moni Naor 将 Hellman 的结论扩展到了所有函数。
Rigorous Time/Space Trade-offs for Inverting Functions https://epubs.siam.org/doi/10.1137/S0097539795280512
在Pass和Liu在2020年的突破之后，这些旧结果突然变得重新有意义了起来。Fiat-Naor算法可以比穷举搜索更快地求逆任意函数。那它也能用于压缩问题吗？
均匀之外
首先提出这个问题的研究者是牛津大学的复杂性理论家Rahul Santhanam和他的研究生Hanlin Ren。他们在2021年的一篇论文中证明，压缩问题和函数求逆要比研究者们已经意识到的更加紧密地交织在一起。
Hardness of KT Characterizes Parallel Cryptography https://eccc.weizmann.ac.il/report/2021/057/
Pass 和 Liu已经证明，如果时间有界Kolmogorov复杂度问题很难，那么函数求逆也一定很难，反之亦然。然而问题可能很难，但仍然可以找到比穷举搜索稍好一些的解法。Santhanam和Ren说明了一个问题是否需要穷举搜索和另一个问题是否需要穷举搜索之间存在着紧密的联系。
他们的结果对研究者经常研究的两大类算法——“均匀”和“非均匀”算法——有着不同的意义。均匀算法对每个输入都遵循相同的程序——例如，对数字列表进行排序的均匀程序，无论列表上有20项还是20,000项，都会以相同的方式工作。非均匀算法则对不同长度的输入使用不同的程序。
Fiat-Naor算法使用的数据结构总是要针对特定函数定制的。要对一个打乱10位比特串的函数求逆，你需要的数据结构与对一个打乱20位比特串的函数求逆所需的数据结构是不同的，即使打乱的方式是相似的。这使得Fiat-Naor是一个非均匀的算法。
Santhanam和Ren的结果表明，可能可以将Fiat-Naor算法转化为解决压缩问题的算法。但是，将算法从一个问题适应到另一个问题并不直接，他们也没有进一步追问这个问题。
一年后，Pass在庆祝 Naor 对密码学贡献的研讨会上听Fiat关于这个经典算法的演讲后，偶然发现了同样的想法，“从那时起，使用函数求逆的想法一直在我脑中萦绕，”他说。后来，他开始与Tel Aviv大学的研究员 Noam Mazor 认真研究这个问题。
与此同时，Ilango在访问加利福尼亚伯克利的Simons计算理论研究所时，与包括Santhanam在内的其他研究人员的讨论中受到启发，开始研究这个问题。“这是在我们随意讨论的过程中产生的非常偶然的灵感，”Santhanam说。之后，Ilango与Williams和位于东京的国家信息学研究所的复杂性理论家Shuichi Hirahara开始联手。
难点在于如何将Fiat-Naor算法核心的数据结构嵌入到解决压缩问题的非均匀算法中。有一种标准的嵌入方法，但这会减慢算法的速度，抵消其对穷举搜索的优势。两个团队找到了更巧妙的方法来整合Fiat-Naor的数据结构，并得到了适用于所有输入且仍然比穷举搜索更快的压缩问题算法。
这两种算法的细节略有不同。Ilango及其合作者的算法比穷举搜索更快，即使你将搜索限制在最简单的可能性上，它也适用于所有压缩问题——包括时间有界Kolmogorov复杂性，最小电路尺寸问题，以及许多其他问题。但是，这两种算法的核心思想是相同的。密码学技术在这个新领域证明了其价值。
汇聚在求逆
这个新的非均匀算法的证明引发了一个自然的问题：均匀算法呢？有没有一种方法可以使用之以比穷举搜索更快地解决压缩问题？
最近的一系列结果表明，任何此类算法都将等同于求逆任意函数的均匀算法 - 这是密码学家几十年来一直未能找到的东西。由此，许多研究人员认为这种可能性不大。
“我会感到非常惊讶的，”Santhanam 说。“这需要全新的想法。”
但是 Allender 表示，研究者不应该忽视这种可能性。“对我来说，一个好的工作假设一直就是，如果有一种非均匀的方式来做某事，很可能也有一种均匀的方式，”他说。
无论如何，这项工作使复杂性理论家们对密码学中的旧问题产生了新的兴趣。以色列Haifa理工学院的密码学家Yuval Ishai表示，这正是最让人兴奋的地方。
“我真的很高兴看到不同社区之间的这种兴趣的汇聚，”他说。“我认为这对科学来说是非常好的事情。”