我们生活在哪个计算宇宙中？

密码学家想知道我们居住在五个可能的世界中的哪一个，这将揭示真正安全的密码学是否可能。

原文：https://www.quantamagazine.org/which-computational-universe-do-we-live-in-20220418/

翻译：Kurt Pan

许多计算机科学家专注于解决困难的计算问题。但是在计算机科学的一个领域——密码学——中，困难性是一种财富。你希望在你的敌手和你的秘密之间设置困难的障碍。

不幸的是，其实我们并不知道安全的密码学是否真的存在。几千年来，人们创造了无数看似牢不可破的密码，它们最终都被破解了。今天，我们的互联网交易和国家机密都是由看似安全但随时可能失败的加密方法保护着。

为了创建一个真正安全（和永久）的加密方法，我们需要一个足够困难的计算问题，以便为敌手创造一个可证明的不可逾越的障碍。我们知道许多看起来很难的计算问题，但这也许只是因为我们还不够聪明来解决它们。或者它们中的一些可能确实很难，但它们的困难性并不适合于安全加密。从根本上说，密码学家想知道：宇宙中是否有足够的困难性使密码学成为可能？

1995 年，加利福尼亚大学圣地亚哥分校的Russell Impagliazzo将关于困难性的问题分解为一系列子问题，计算机科学家可以一次去解决一个问题。为了总结该领域的知识状况，他描述了五个可能的世界——被称为 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania——困难性越来越高，密码学的可能性也不断扩大。这些中的任何一个都可能是我们所生活的世界。

Algorithmica

在这个世界中，就连最自然的计算问题都很容易，这使得密码学成为不可能。在这里，具有高效解法的问题集 不仅包含我们已经想出如何解决的问题，还包括另一个称为  的集合中的所有问题，该集合包括那些有人将解法给你时可以很容易地去检验的问题。

从表面上看， 和 感觉上就像是不同的类。例如，考虑你的行李箱🧳是否能装下你旅行时要打包的所有物品这个问题。如果有朋友为你打包，那很容易验证是否已将所有物品放入其中——只需检查有无任何物品遗漏即可。所以行李箱打包问题在中。但是自己打包行李箱就要困难得多——你可能要不得不去尝试许多不同的摆放方式。目前尚不清楚是否有一种高效的算法可以对所有可能的物品和行李箱组合解决这个问题。也就是说，我们不知道这个问题是否在 中。

解密加密方案这个问题也在 中。毕竟，如果你有一条加密消息，而一个朋友声称已经解密了它，你可以通过将其解密的消息输入加密机器并查看输出是否与你的原始加密消息匹配来进行检查。（当然，你必须拥有一台加密机器才能做到这一点，但密码学家不认为一个方案是安全的，除非它能够承受来自获得了其中一台机器的敌手的攻击。）

在 Algorithmica 中， 和 是完全相同的问题集合。对这一点的证明将是一个算法方面的富矿，因为这意味着存在快速的算法来解决行李箱打包和 中所有其他看似困难的问题。但这对密码学家来说将是一场灾难，因为我们能够有效解决的问题之一就是解密。

大多数计算机科学家认为 与 不同，原因很简单， 中有很多我们无法高效解决的问题。但从来没有人能够证明（或证伪）这一点，即使“ 与 ”问题已被认为是过去五十年来理论计算机科学中最著名的问题。以色列Technion的Yuval Ishai说，“除了最聪明的人不断地尝试失败这一事实，我们没有证据表明很难证明 不等于 。”

Heuristica

在这个世界中， 中有些问题不容易解决，但 中的每个问题“平均意义上”都很容易，这意味着在大多数情况下都可以高效地解决。例如，如果我们在 Heuristica 中，那么存在一种几乎总是成功的高效的行李箱打包算法，但对于一些罕见的行李箱和物品组合可能会失败。（这些快速且通常成功的算法通常被称为启发式算法。）

从密码学的角度来看，Heuristica 和 Algorithmica 之间并没有太大的区别。如果我们在 Heuristica 中提出一种加密方案，将会有一些可以处理几乎每条消息的快速解密方法，从而使该方案在实际用途中毫无用处。

Pessiland

这是所有可能世界中最糟糕的一个。在 Pessiland 中， 中的一些问题即使在平均意义上也很难。对于这些问题，任何有效的算法不仅会偶尔失败，而且会经常失败。然而，这些困难问题却也并不是对隐藏秘密信息有用的问题。

“我们绝对不想住在Pessiland，”Rutgers大学的Eric Allender说。“在这里，我们得到了计算复杂性带来的所有不利方面，同时还没有带来像密码学这样的好处。”

Minicrypt

在这个世界中，中的一些问题平均意义上是困难的，且这种困难性足以构建密码学最基本的构建组件：单向函数 ，这是一种可以高效地被执行但不能高效的被逆转的函数。密码学家已经证明，安全的密码学需要单向函数。如果我们拥有它们，我们将获得一系列密码学原语，例如私钥加密、数字签名和伪随机数生成器。

“毫无疑问，单向函数是否存在，是密码学中最重要的问题，”康奈尔大学的Rafael Pass说。“如果我们没有它们，所有的这些东西都可以被攻破。”

Cryptomania

在这个世界中，我们有足够的困难性来创建Minicrypt中的所有东西，还要另加上更高级的密码学协议，例如公钥加密（在不知道密钥的情况下发送加密消息）。

1排除世界

Ishai 说，大多数密码学家相信至少有一些密码学确实存在，所以我们很可能生活在 Cryptomania 或 Minicrypt 中。但他们并不指望很快就能证明这一点。这样的证明需要排除其他三个世界——而仅仅排除Algorithmica本身就已经需要先解决计算机科学家几十年来一直在努力解决的“ 与 ”问题。

不过最近，Pass和他的博士生Yanyi Liu发现了一种筛选这些世界的新方法。他们第一次发现了一个自然的问题——称为时间受限 Kolmogorov 复杂度，或简称为——其难度级别在包括密码学的世界和不包括密码学的世界之间创造了一条明亮的分界线。如果平均情况下很容易，Liu 和 Pass 表明，那么安全的密码学就不可能存在，那么我们处于 Algorithmica、Heuristica 或 Pessiland。但如果平均情况下是困难的，那么我们可以制作单向函数，那么我们至少在 Minicrypt 中，并且可能在 Cryptomania 中。

这一新结果还意味着计算机科学家可以排除Pessiland——最糟糕的那个世界——如果他们能证明如下进一步的论断：如果平均情况下是容易的，那么 中的每个问题也是如此。在这种情况下，我们就可以把问题缩小到平均情况下困难的世界（Minicrypt 和 Cryptomania）和 ——以及 中的所有其他问题——平均情况下容易的世界（Algorithmica 和 Heuristica）。

研究人员一直在研究 Pessiland ，麻省理工学院的Ryan Williams说，“我认为普遍的共识是可以排除Pessiland，但我不知道我们何时能做到这一点。”

密码学家也真的很想排除掉Heuristica，这将涉及证明如果平均情况下容易，那么 中的每个问题在所有情况下都很容易（不仅仅是平均情况下）。排除这两个世界意味着我们要么生活在Algorithmica中，那里的一切总是很容易，要么我们有足够的困难性来进行基本的密码学。

密码学家广泛将此目标称为该领域的圣杯。Ishai 不期望在他的有生之年能看到它被证明，但即使这点也不确定。“当难题将被解决时，有时我们会看到它的到来，但有时我们不会，”他说。“毫无疑问，这条崭新的工作路径是我们最好的机会。”