我们生活在计算宇宙的哪个密码世界当中

北京时间 4 月 28 日消息，据国外媒体报道，许多计算机科学家都专注于克服困难的计算问题，但在计算机科学的一个领域中，"困难"是所有都想要获得的优势。这就是密码学的领域，身处其中的人都希望在对手和自己的秘密之间设置难以攻破的障碍。

遗憾的是，我们不知道是否存在绝对安全的加密技术。几千年来，人们创造了许多看似不可破解的密码，但最终都被一一破解。如今，从我们日常的互联网交易到国家机密，都受到各种加密方法的保护，这些方法看似安全，但随时可能失效。

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

1995 年，美国加州大学圣地亚哥分校的拉塞尔・因帕利亚佐将难度问题分解为一系列子问题，使计算机科学家能够逐步进行解决。为了总结这一领域的知识状况，他描述了 5 种可能的世界，并富有想象力地命名为 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania-- 难度和加密可能性逐渐上升。这其中任何一个都可能是我们生活的世界。

Algorithmica

在这个世界上，最自然的计算问题都很容易，使得加密变得不可能。在这里，可以找到有效解的问题集 -- 称为 P 集 -- 不仅仅包含我们已经想出解决方案的问题，还包括另一个被称为 NP 的集合中的所有问题。NP 类问题由可以有效检验一个解的准确性的问题组成。粗略地说，P 类问题就是可以在计算机上快速求解的问题，而对 NP 类问题则可快速确定某个可能的解是否正确。

表面上看，P 和 NP 感觉像是不同的类别。以一个日常问题为例子：决定你的行李箱能否装下所有要打包的旅行物品。如果有朋友帮你收拾，你很容易就能确认他们是否把所有东西都装好了 -- 只要检查一下有什么遗漏的东西就行了。因此，这个行李箱打包问题就属于 NP。但是，自己收拾行李就难多了 -- 你可能要尝试很多不同的物品摆放方式。目前还不清楚是否有一种有效的算法能够解决所有可能的物品和行李箱组合的问题。换言之，我们不知道这个问题是否属于 P 类问题。

加密方案的解密问题也属于 NP 类问题。毕竟，如果你有一条加密消息，而你的朋友声称已经对其进行了解密，那么你就可以通过将他们解密的消息输入加密机，并查看输出结果是否与原始加密消息匹配来进行检查。（当然，要做到这一点，你必须拥有一台加密机；但是，在密码学家看来，这种加密方案是否安全，要看它能否经受住获得这种加密机的敌人的攻击。）

在 Algorithmica 世界中，P 和 NP 是同一类问题。证明这一点对算法而言是一件幸事，因为这意味着存在快速算法来处理 NP 类问题中诸如手提箱装箱及其他看似困难的问题。但对密码学家来说，这将是一场灾难，因为在这个世界中，我们可以有效地进行解密。

大多数计算机科学家认为 P 不同于 NP，原因很简单，NP 中有很多问题是我们无法有效解决的。然而，没有人能够证明（或反驳）这一点，尽管"P / NP"问题被认为是 50 年来理论计算机科学中最著名的问题，除了最聪明的人不断失败之外，我们没有证据表明 P 不等于 NP 很难证明。

Heuristica

在这个世界中，有一些 NP 类问题很不容易解决，但每个 NP 类问题"平均"起来都很容易，意即在大多数情况下都可以有效解决。例如，如果我们生活在 Heuristica 世界中，那就存在一种几乎总会成功的高效行李箱打包算法，但对于行李箱和物品的一些罕见组合来说，它可能会失败（这些快速且通常成功的算法通常被称为"heuristic"）。

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

Pessiland

这是所有可能的世界中最糟糕的。在 Pessiland 世界中，一些 NP 类问题即使平均起来也都十分困难。对于这些问题，任何有效的算法都会失败 -- 不是偶尔失败，而是经常失败。然而，这些难题对隐藏秘密信息而言却不是那么有效。

我们绝对不想住在 Pessiland 世界中，在这里，我们得到了（计算）复杂性的所有不好的方面，同时又没有任何像密码学那样的优势。

Minicrypt

在这个世界中，NP 中的一些问题平均起来都很难，而这种困难程度足以构建密码学最基本的构建块：单向函数。这是一种可以有效执行但不能有效逆转的函数：对于每一个输入，函数值都容易计算；但对于一个随机的函数值，算出其对应的输入却很困难。密码学家已经证明，安全加密需要单向函数。如果单向函数存在，我们就会得到一系列实用的加密工具，比如秘钥加密、数字签名和伪随机数生成器。

毫无疑问，单向函数是否存在，是密码学中最重要的问题，如果没有单向函数，所有这一切都可能被破坏。事实上，如果单向函数存在，将证明 P / NP 问题中，P 不等于 NP；与之对应，P 不等于 NP 的假设并不能直接推出单向函数的存在。

Cryptomania

在这个世界中，我们有足够的难度创建出 Minicrypt 世界中的任何东西，甚至还可以创建出更高级的加密协议，如公钥加密（在这种协议中，人们可以在不知道密钥的情况下发送加密的消息）。

对这些世界的筛选

大多数密码学家认为，至少有一些真正安全的加密方法是存在的，因此我们可能生活在 Cryptomania 或 Minicrypt 世界当中。但密码学家们并不指望很快就能看到这方面的证据。如果存在这样的证据，首先需要排除其他三个世界，而单单排除 Algorithmica 本身就已经需要解决"P / NP"问题。数十年来，计算机复杂度领域的科学家一直在努力解决这一问题，但至今仍未被解决。

不过，密码学家最近发现了一种筛选这些世界的新方法。他们第一次确定了一个自然问题 -- 有时间限制的柯氏复杂性（time-bounded Kolmogorov complexity，简称 Kt）-- 的难度等级在包含密码学的世界和不包含密码学的世界之间划出了一条清晰的分界线，如果 Kt 问题普遍很简单，那么安全密码学就不可能存在，所以我们处于 Algorithmica、Heuristica 或 Pessiland 世界当中。但如果 Kt 普遍都很困难，那我们就能找到单向函数，从而证明我们至少生活在 Minicrypt 世界中，甚至可能处于 Cryptomania 世界。

这个新结果意味着计算机科学家只要能证明另一个命题，"如果 Kt 问题普遍很容易，那么 NP 中的所有问题也都很容易"，就可以消除 Pessland-- 最糟糕的世界。在这种情况下，我们可以简化为：Minicrypt 和 Cryptomania 是 Kt 问题普遍困难的世界；Algorithmica 和 Heuristica 是 Kt 问题（以及 NP 中其他所有问题）普遍容易的世界。

研究人员已经对如何消除 Pessland 世界研究了一段时间，现在的普遍共识是，Pessland 世界可以被排除，但我不知道我们会在什么时候这么做。

密码学家也想消除 Heuristica 世界，而这会涉及证明如果 Kt 问题普遍是容易的，那么 NP 中的每个问题在所有情况下都是容易的（不仅仅是普遍）。如果能排除这两个世界，那将意味着要么我们生活在 Algorithmica 世界，一切都很简单；要么我们有足够的难度来进行基本的密码学加密。

密码学家普遍将这个目标称为该领域的"圣杯"，并不认为自己在有生之年能看到这些问题被证明，但这也是不确定的。