科学探索|我们生活在计算宇宙的哪个密码世界当中？我们生活在计算宇宙的哪个密

北京时间4月28日消息，据国外媒体报道，许多计算机科学家都专注于克服困难的计算问题，但在计算机科学的一个领域中， “困难”是所有都想要获得的优势。这就是密码学的领域，身处其中的人都希望在对手和自己的秘密之间设置难以攻破的障碍。
遗憾的是，我们不知道是否存在绝对安全的加密技术。几千年来，人们创造了许多看似不可破解的密码，但最终都被一一破解。如今，从我们日常的互联网交易到国家机密，都受到各种加密方法的保护，这些方法看似安全，但随时可能失效。
为了创建一个真正安全（且永久）的加密方法，我们就需要一个足够困难的计算问题，来为对手设置一个可证实为不可逾越的障碍。我们知道有很多看起来非常难解的计算问题，但也许只是我们还不够聪明，无法解决它们。或者其中一些问题可能很难，但困难的程度并不适合用于安全加密。从根本上说，密码学家想知道的是：宇宙是否存在足够的难度，使安全加密成为可能？
1995年，美国加州大学圣地亚哥分校的拉塞尔·因帕利亚佐将难度问题分解为一系列子问题，使计算机科学家能够逐步进行解决。为了总结这一领域的知识状况，他描述了5种可能的世界，并富有想象力地命名为Algorithmica、Heuristica、Pessiland、Minicrypt和Cryptomania——难度和加密可能性逐渐上升。这其中任何一个都可能是我们生活的世界。
Algorithmica
在这个世界上，最自然的计算问题都很容易，使得加密变得不可能。在这里，可以找到有效解的问题集——称为P集——不仅仅包含我们已经想出解决方案的问题，还包括另一个被称为NP的集合中的所有问题。NP类问题由可以有效检验一个解的准确性的问题组成。粗略地说， P类问题就是可以在计算机上快速求解的问题，而对NP类问题则可快速确定某个可能的解是否正确。
【科学探索|我们生活在计算宇宙的哪个密码世界当中？】表面上看， P和NP感觉像是不同的类别。以一个日常问题为例子：决定你的行李箱能否装下所有要打包的旅行物品。如果有朋友帮你收拾，你很容易就能确认他们是否把所有东西都装好了——只要检查一下有什么遗漏的东西就行了。因此，这个行李箱打包问题就属于NP 。但是，自己收拾行李就难多了——你可能要尝试很多不同的物品摆放方式。目前还不清楚是否有一种有效的算法能够解决所有可能的物品和行李箱组合的问题。换言之，我们不知道这个问题是否属于P类问题。
加密方案的解密问题也属于NP类问题。毕竟，如果你有一条加密消息，而你的朋友声称已经对其进行了解密，那么你就可以通过将他们解密的消息输入加密机，并查看输出结果是否与原始加密消息匹配来进行检查。（当然，要做到这一点，你必须拥有一台加密机；但是，在密码学家看来，这种加密方案是否安全，要看它能否经受住获得这种加密机的敌人的攻击。）
在Algorithmica世界中， P和NP是同一类问题。证明这一点对算法而言是一件幸事，因为这意味着存在快速算法来处理NP类问题中诸如手提箱装箱及其他看似困难的问题。但对密码学家来说，这将是一场灾难，因为在这个世界中，我们可以有效地进行解密。