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

许多计算机科学家专注于克服困难的计算问题。但是在计算机科学的一个领域中，硬度是一种资产：密码学，你希望在你的对手和你的秘密之间设置硬障碍。

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

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

1995 年，加利福尼亚大学圣地亚哥分校的Russell Impagliazzo将硬度问题分解为一组子问题，计算机科学家可以一次解决一个问题。为了总结该领域的知识状况，他描述了五个可能的世界——分别命名为 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania——难度和密码学的可能性都在上升。这些中的任何一个都可能是我们生活的世界。

算法

在这个世界上，最自然的计算问题都很容易，这使得密码学成为不可能。在这里，具有有效解决方案的问题集——称为 P 的集合——不仅包含我们已经想出如何解决的问题。它还包括另一个称为 NP 的集合中的所有问题，其中包含如果有人将建议的解决方案交给您时很容易检查的问题。

大多数计算机科学家认为 P 与 NP 不同，原因很简单，NP 中有很多我们无法有效解决的问题。但从来没有人能够证明（或反驳）这一点，即使“P 与 NP”问题已被认为是 5 年来理论计算机科学中最著名的问题。再说一次，以色列海法理工学院的Yuval Ishai说，“除了最聪明的人不断失败，我们没有证据表明很难证明 P 不等于 NP。”

启发式

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

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

佩西兰

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

“我们绝对不想住在佩西兰，”罗格斯大学的埃里克艾伦德说。 “在这里，我们得到了 [计算] 复杂性的所有不利方面，但没有像密码学这样的优势。”

迷你密码

在这个世界上，NP中的一些问题平均来说是很难的，而这种硬度足以构建密码学最基本的构建块：“ 单向函数”，这是一个可以高效执行但不能执行的函数被有效地逆转。密码学家已经证明，安全密码学需要单向函数。如果我们拥有它们，我们将获得一系列加密产品，例如密钥加密、数字签名和伪随机数生成器。

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

迷信症

在这个世界上，我们有足够的硬度在 Minicrypt 中创建所有内容，以及更高级的加密协议，例如公钥加密（人们可以在不知道密钥的情况下发送加密消息）。

消除世界

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

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

这一新结果意味着计算机科学家可以消除 Pessiland——最糟糕的世界——如果他们能证明更多的陈述：如果K ^t平均而言是容易的，那么 NP 中的每个问题也是如此。在这种情况下，我们将把事情缩小到K ^t平均困难的世界（Minicrypt 和 Cryptomania）和K ^t ——以及 NP 中的所有其他问题——平均容易的世界（Algorithmica 和 Heuristica）。

麻省理工学院的瑞恩·威廉姆斯说，研究人员一直在研究 Pessiland。 “我认为普遍的共识是可以排除佩西兰，但我们迟早会这样做，我不知道。”

密码学家也真的很想消除启发式算法，这将涉及证明如果K ^t平均起来很容易，那么 NP 中的每个问题在所有情况下都很容易（不仅仅是平均）。排除这两个世界意味着我们要么生活在算法中，那里的一切总是很容易，要么我们有足够的硬度来进行基本的密码学。

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