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

据国外媒体报道，许多计算机科学家专注于解决困难的计算问题，但在计算机科学的一个领域，困难是所有人都想获得的优势这是密码学领域，人们希望在对手和他们的秘密之间建立不可逾越的障碍

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

为了创建一个真正安全的加密方法，我们需要一个足够难的计算问题，给对手设置一个不可逾越的障碍我们知道有许多计算问题似乎很难解决，但也许我们只是不够聪明来解决它们或者其中的一些问题可能比较难，但是难度不适合安全加密从根本上说，密码学家想知道:宇宙中是否有足够的困难使安全加密成为可能

1995年，美国加州大学圣地亚哥分校的Russell Impagliazzo将难度问题分解为一系列子问题，使计算机科学家能够一步步解决为了总结这一领域的知识状态，他描述了五个可能的世界，并将其命名为Algorithmica，Heuristica，Pessiland，Minicrypt和Cryptomania——富有想象力——难度和加密可能性逐渐增加其中任何一个都可能是我们生活的世界

算法a

在这个世界里，最自然的计算问题都很容易，使得加密成为不可能在这里，可以找到有效解决方案的问题集不仅包含我们已经找到解决方案的问题，还包含另一个称为NP集的所有问题NP类问题由能有效检验解的准确性的问题组成大致来说，P类问题是可以在计算机上快速解决的问题，而NP类问题可以快速确定一个可能的解是否正确

从表面上看，P和NP感觉是不同的范畴以一个日常问题为例:决定你的行李箱是否能装下所有要打包的旅行物品如果你有朋友帮你收拾，你可以很容易地确认他们是否收拾好了所有东西——只需检查一下少了什么所以这个行李箱打包问题属于NP可是，自己收拾行李要困难得多——你可能要尝试许多不同的方式来整理东西目前还不清楚是否有有效的算法来解决物品和行李箱所有可能的组合换句话说，我们不知道这个问题是否属于P类问题

加密方案的解密问题也属于NP问题毕竟，如果你有一个加密的消息，而你的朋友声称已经解密了它，那么你可以通过将他们解密的消息输入到加密机中来检查它，看看输出结果是否与原始的加密消息匹配

在算法的世界里，P和NP是同一类问题算法能证明这一点是一件幸事，因为这意味着有快速算法来处理行李箱打包等NP级问题以及其他看似困难的问题但对密码学家来说将是一场灾难，因为在这个世界上，我们可以有效地解密

大多数计算机科学家认为P不同于NP，原因很简单，NP中有许多我们无法有效解决的问题可是，没有人能证明它，尽管P/NP问题被认为是过去50年理论计算机科学中最著名的问题除了最聪明的人不断失败，我们没有证据证明P不等于NP，这个很难证明

启发式

在这个世界上，有一些NP类的问题是不容易解决的，但是每个NP类的问题都是容易平均的，也就是说在大多数情况下都是可以有效解决的例如，如果我们生活在Heuristica世界，有一种高效的行李打包算法几乎总能成功，但对于一些罕见的行李和物品组合可能会失败

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

佩西兰

这是所有可能的世界中最糟糕的在佩西兰世界，一些NP类的问题即使平均起来也是非常难的对于这些问题，任何有效的算法都会失败——不是偶尔，而是经常可是，这些问题对于隐藏秘密信息并不那么有效

我们绝对不想生活在伪世界，在那里我们得到了复杂性的所有不好的方面，同时，我们也没有任何像密码学这样的优势。

迷你密码

在这个世界上，NP中的一些问题平均难度很大，这个难度足以构造密码学最基本的积木:单向函数这是一个可以有效执行但不能有效反转的函数:对于每一个输入，函数值都很容易计算，但对于一个随机函数值，很难计算其对应的输入密码学家已经证明，安全加密需要一个单向函数如果单向函数存在，我们将得到一系列实用的加密工具，如密钥加密，数字签名，伪随机数发生器等

毫无疑问，单向函数的存在是密码学中最重要的问题如果没有单向函数，这一切都可能被破坏其实单向函数存在的话，就证明了P/NP问题中P不等于NP，相应的，P不等于NP的假设也不能直接推导单向函数的存在性

神秘躁狂

在这个世界里，我们有足够的难度去创造Minicrypt世界里的任何东西，甚至创造出更高级的加密协议，比如公钥加密。

这些世界的筛选

大多数密码学家认为，至少存在一些真正安全的加密方法，因此我们可能生活在密码狂热或迷你密码世界中但是密码学家不指望很快看到这些证据如果有这样的证据，需要先排除其他三个世界，只排除Algorithmica就能解决P/NP问题几十年来，计算机复杂性领域的科学家一直在试图解决这个问题，但至今仍未解决

可是，密码学家最近发现了一种筛选这些世界的新方法他们第一次确定了一个自然问题的难度水平——有时间限制的基尔希纳复杂性——并在包含加密技术的世界和不包含加密技术的世界之间画出了一条清晰的分界线如果Kt问题一般很简单，那么安全密码学就不可能存在，所以我们处在Algorithmica，Heuristica或者Pessiland的世界里但如果Kt普遍困难，那么我们可以找到一个单向函数，从而证明我们至少生活在Minicrypt的世界里，甚至可能生活在Cryptomania的世界里

这一新结果意味着，计算机科学家只要能证明另一个命题如果Kt问题普遍容易，那么NP中的所有问题都容易，就可以排除Pessland这个最坏的世界在这种情况下，我们可以简化为:Minicrypt和Cryptomania是Kt问题普遍困难的世界，Algorithmica和Heuristica是Kt问题一般容易解决的世界

一段时间以来，研究人员一直在研究如何消除害虫现在普遍的共识是可以排除佩斯兰世界，但不知道什么时候能做到

密码学家还希望消除启发式世界，这将涉及到证明如果Kt问题通常是容易的，那么NP中的每个问题在所有情况下都是容易的如果我们能排除这两个世界，那将意味着要么我们生活在Algorithmica世界，一切都很简单，要么我们有足够的难度来执行基本的密码加密

密码学家一般将这个目标称为该领域的圣杯，他们认为在有生之年不会看到这些问题被证明，但这也是不确定的。