不幸的是，我們不知道是否存在絕對安全的加密技術(shù)。幾千年來，人們創(chuàng)造了許多看似牢不可破的密碼，但最終都被一一破解。如今，從日?；ヂ?lián)網(wǎng)交易到國家機密，一切都受到各種看似安全但隨時可能失敗的加密方法的保護。

為了創(chuàng)建真正安全（且永久）的加密方法，我們需要一個足夠困難的計算問題，足以為對手創(chuàng)造一個不可逾越的障礙。我們知道有很多計算問題看起來很難解決，但也許我們只是不夠聰明，無法解決它們?；蛘咂渲幸恍﹩栴}可能很困難，但沒有達到適合安全加密的難度水平。從根本上來說，密碼學家想知道的是：宇宙中是否存在足夠的難度來使安全加密成為可能？

1995年，加州大學圣地亞哥分校的Russell Impagliazo將難題分解為一系列子問題，讓計算機科學家一步步解決。為了總結(jié)該領(lǐng)域的知識狀況，他描述了5 個可能的世界，富有想象力地將它們命名為Algorithmica、Heuristica、Pessiland、Minicrypt 和Cryptomania ——，難度和加密可能性不斷增加。其中任何一個都可能是我們生活的世界。

算法

在這個世界上，最自然的計算問題都很簡單，使得加密成為不可能。這里，可以找到有效解決方案的問題——的集合稱為P。集合——不僅包含我們已找到解決方案的問題，還包含另一個稱為NP的集合中的所有問題。 NP 型問題由能夠有效測試解決方案準確性的問題組成。粗略地講，P型問題是可以在計算機上快速解決的問題，而對于NP型問題，可以快速確定一個可能的解決方案是否正確。

從表面上看，P和NP感覺像是不同的類別。以一個日常問題為例：決定您的行李箱是否能容納您旅行時要攜帶的所有物品。如果您有一個朋友包，那么很容易確保他們已經(jīng)收拾好所有東西。只需檢查一下是否缺少任何東西。因此，這個行李箱打包問題屬于NP問題。然而，自己收拾行李要困難得多。您可能需要嘗試許多不同的方式來安排您的物品。目前尚不清楚是否存在一種有效的算法可以解決所有可能的物品和行李組合的問題。換句話說，我們不知道這個問題是否屬于P類型。

該加密方案的解密問題也屬于NP類。畢竟，如果您有一條加密消息，并且您的朋友聲稱已對其進行解密，您可以通過將其解密消息輸入加密機并查看輸出是否與原始加密消息匹配來進行檢查。 （當然，要做到這一點，你必須有一個加密機；但是，在密碼學家看來，這樣的加密方案的安全性取決于它是否能夠抵御獲得加密機的敵人的攻擊。）

在Algorithmica的世界中，P和NP是同一類型的問題。證明這一點對算法來說是一件幸事，因為這意味著有快速算法可以解決類似NP 的問題，例如手提箱打包和其他看似困難的問題。但對于密碼學家來說，這將是一場災難，因為在這個世界上，我們可以高效地解密。

大多數(shù)計算機科學家認為P與NP不同，原因很簡單，NP中有很多問題我們無法有效解決。然而，沒有人能夠證明（或反駁）這一點，盡管“P/NP”問題被認為是50 年來理論計算機科學中最著名的問題，但除了最聰明的人不斷失敗之外，我們沒有任何證據(jù)證明P不等于NP是很困難的。

啟發(fā)式

這個世界上，有一些NP型問題非常難解決，但每個NP型問題“平均”來說都很容易，這意味著大多數(shù)情況下都可以有效解決。例如，如果我們生活在Heuristica 的世界中，就會有一種高效的手提箱打包算法，幾乎總是成功，但對于一些罕見的手提箱和物品組合，它可能會失?。ㄟ@些快速且通常成功的算法通常被稱為“啟發(fā)式算法”） ”）。

從密碼學的角度來看，Heuristica 和Algorithmica 之間沒有太大區(qū)別。如果我們在Heuristica 的世界中提出一種加密方案，就會有一些快速解密方法可以對幾乎每條消息進行，從而使該方案在實際場景中毫無用處。

佩西蘭

這是所有可能的世界中最糟糕的一個。在Pesiland 世界中，一些NP 型問題即使平均起來也非常困難。對于這些問題，任何高效的算法都會失敗—— 不是偶爾，而是經(jīng)常。然而，這些謎題在隱藏秘密信息方面并不那么有效。

我們絕對不想生活在Pessiland 世界中，在那里我們得到了（計算）復雜性的所有不好的方面，而沒有任何像密碼學這樣的優(yōu)勢。

迷你密碼

在這個世界上，NP 中的一些問題平均起來足以構(gòu)建密碼學最基本的構(gòu)建塊：單向函數(shù)。這是一個可以高效執(zhí)行但無法有效反轉(zhuǎn)的函數(shù)：對于每個輸入，函數(shù)值很容易計算；但對于隨機函數(shù)值，計算相應(yīng)的輸入是困難的。密碼動物學家已經(jīng)證明，安全加密需要單向函數(shù)。如果存在單向函數(shù)，我們將擁有一系列有用的加密工具，例如密鑰加密、數(shù)字簽名和偽隨機數(shù)生成器。

毫無疑問，單向函數(shù)的存在性是密碼學中最重要的問題。如果沒有單向功能，所有這一切都可能被破壞。事實上，如果存在單向函數(shù)，就證明在P/NP問題中，P不等于NP；相應(yīng)地，P不等于NP的假設(shè)不能直接推導出單向函數(shù)的存在。

加密狂熱

在這個世界上，我們有足夠的難度來創(chuàng)建Minicrypt 世界中的任何東西，甚至更高級的加密協(xié)議，例如公鑰密碼學（其中人們可以在不知道密鑰的情況下創(chuàng)建加密）。發(fā)送加密消息）。

篩選這些世界

大多數(shù)密碼學家認為至少存在一些真正安全的加密方法，因此我們可能生活在Cryptomania 或Minicrypt 世界中。但密碼學家預計不會很快看到這方面的證據(jù)。如果存在這樣的證據(jù)，則需要首先排除其他三個世界，而僅排除Algorithmica 就已經(jīng)需要解決“P/NP”問題。幾十年來，計算機復雜性領(lǐng)域的科學家們一直在努力解決這個問題，但仍未得到解決。

然而，密碼學家最近發(fā)現(xiàn)了一種篩選這些世界的新方法。他們第一次發(fā)現(xiàn)了一個自然問題，即有時間限制的柯爾莫哥洛夫復雜性（Kt），其難度水平在包含密碼學的世界和不包含密碼學的世界之間劃出了一條界線。一條清晰的分界線，如果Kt 問題普遍簡單，那么安全密碼學將不可能實現(xiàn)，因此我們將處于Algorithmica、Heuristica 或Pessiland 的世界中。但如果Kt 普遍困難，那么我們可以找到單向函數(shù)，證明我們至少生活在一個Minicrypt 世界，甚至可能是一個Cryptomania 世界。

這個新結(jié)果意味著，如果計算機科學家能夠證明另一個命題：“如果Kt 問題普遍容易，那么NP 中的所有問題也很容易”，他們就可以消除Pessland—— 最糟糕的世界。在這種情況下，我們可以簡化為：Minicrypt 和Cryptomania 是Kt 問題普遍困難的世界；在Algorithmica 和Heuristica 中，Kt 問題（以及NP 中的所有其他問題）普遍都很容易。

一段時間以來，研究人員一直在研究如何消除佩斯蘭世界，現(xiàn)在普遍的共識是，佩斯蘭世界是可以消除的，但我不知道我們什么時候能做到這一點。

密碼動物學家還希望消除啟發(fā)式世界，這將涉及證明如果Kt 問題普遍容易，那么NP 中的每個問題在所有情況下都是容易的（不僅僅是普遍的）。如果這兩個世界可以被排除，那就意味著我們要么生活在一個一切都很簡單的算法世界，要么我們有足夠的困難來執(zhí)行基本的密碼加密。

神秘動物學家通常將這一目標稱為該領(lǐng)域的“圣杯”，并且不期望在他們的有生之年看到這些問題得到證實，但這也是不確定的。 （任天堂）