遺憾的是，我們不知道是否存在絕對(duì)安全的加密技術(shù)。幾千年來，人們創(chuàng)造了許多看似不可破解的密碼，但最終都被一一破解。如今，從我們?nèi)粘５幕ヂ?lián)網(wǎng)交易到國家機(jī)密，都受到各種加密方法的保護(hù)，這些方法看似安全，但隨時(shí)可能失效。

為了創(chuàng)建一個(gè)真正安全（且永久）的加密方法，我們就需要一個(gè)足夠困難的計(jì)算問題，來為對(duì)手設(shè)置一個(gè)可證實(shí)為不可逾越的障礙。我們知道有很多看起來非常難解的計(jì)算問題，但也許只是我們還不夠聰明，無法解決它們。或者其中一些問題可能很難，但困難的程度并不適合用于安全加密。從根本上說，密碼學(xué)家想知道的是：宇宙是否存在足夠的難度，使安全加密成為可能？

1995年，美國加州大學(xué)圣地亞哥分校的拉塞爾·因帕利亞佐將難度問題分解為一系列子問題，使計(jì)算機(jī)科學(xué)家能夠逐步進(jìn)行解決。為了總結(jié)這一領(lǐng)域的知識(shí)狀況，他描述了5種可能的世界，并富有想象力地命名為Algorithmica、Heuristica、Pessiland、Minicrypt和Cryptomania——難度和加密可能性逐漸上升。這其中任何一個(gè)都可能是我們生活的世界。

Algorithmica

在這個(gè)世界上，最自然的計(jì)算問題都很容易，使得加密變得不可能。在這里，可以找到有效解的問題集——稱為P集——不僅僅包含我們已經(jīng)想出解決方案的問題，還包括另一個(gè)被稱為NP的集合中的所有問題。NP類問題由可以有效檢驗(yàn)一個(gè)解的準(zhǔn)確性的問題組成。粗略地說，P類問題就是可以在計(jì)算機(jī)上快速求解的問題，而對(duì)NP類問題則可快速確定某個(gè)可能的解是否正確。

表面上看，P和NP感覺像是不同的類別。以一個(gè)日常問題為例子：決定你的行李箱能否裝下所有要打包的旅行物品。如果有朋友幫你收拾，你很容易就能確認(rèn)他們是否把所有東西都裝好了——只要檢查一下有什么遺漏的東西就行了。因此，這個(gè)行李箱打包問題就屬于NP。但是，自己收拾行李就難多了——你可能要嘗試很多不同的物品擺放方式。目前還不清楚是否有一種有效的算法能夠解決所有可能的物品和行李箱組合的問題。換言之，我們不知道這個(gè)問題是否屬于P類問題。

加密方案的解密問題也屬于NP類問題。畢竟，如果你有一條加密消息，而你的朋友聲稱已經(jīng)對(duì)其進(jìn)行了解密，那么你就可以通過將他們解密的消息輸入加密機(jī)，并查看輸出結(jié)果是否與原始加密消息匹配來進(jìn)行檢查。（當(dāng)然，要做到這一點(diǎn)，你必須擁有一臺(tái)加密機(jī)；但是，在密碼學(xué)家看來，這種加密方案是否安全，要看它能否經(jīng)受住獲得這種加密機(jī)的敵人的攻擊。）

在Algorithmica世界中，P和NP是同一類問題。證明這一點(diǎn)對(duì)算法而言是一件幸事，因?yàn)檫@意味著存在快速算法來處理NP類問題中諸如手提箱裝箱及其他看似困難的問題。但對(duì)密碼學(xué)家來說，這將是一場災(zāi)難，因?yàn)樵谶@個(gè)世界中，我們可以有效地進(jìn)行解密。

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

Heuristica

在這個(gè)世界中，有一些NP類問題很不容易解決，但每個(gè)NP類問題“平均”起來都很容易，意即在大多數(shù)情況下都可以有效解決。例如，如果我們生活在Heuristica世界中，那就存在一種幾乎總會(huì)成功的高效行李箱打包算法，但對(duì)于行李箱和物品的一些罕見組合來說，它可能會(huì)失敗（這些快速且通常成功的算法通常被稱為“heuristic”）。

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

Pessiland

這是所有可能的世界中最糟糕的。在Pessiland世界中，一些NP類問題即使平均起來也都十分困難。對(duì)于這些問題，任何有效的算法都會(huì)失敗——不是偶爾失敗，而是經(jīng)常失敗。然而，這些難題對(duì)隱藏秘密信息而言卻不是那么有效。

我們絕對(duì)不想住在Pessiland世界中，在這里，我們得到了（計(jì)算）復(fù)雜性的所有不好的方面，同時(shí)又沒有任何像密碼學(xué)那樣的優(yōu)勢。

Minicrypt

在這個(gè)世界中，NP中的一些問題平均起來都很難，而這種困難程度足以構(gòu)建密碼學(xué)最基本的構(gòu)建塊：單向函數(shù)。這是一種可以有效執(zhí)行但不能有效逆轉(zhuǎn)的函數(shù)：對(duì)于每一個(gè)輸入，函數(shù)值都容易計(jì)算；但對(duì)于一個(gè)隨機(jī)的函數(shù)值，算出其對(duì)應(yīng)的輸入?yún)s很困難。密碼學(xué)家已經(jīng)證明，安全加密需要單向函數(shù)。如果單向函數(shù)存在，我們就會(huì)得到一系列實(shí)用的加密工具，比如秘鑰加密、數(shù)字簽名和偽隨機(jī)數(shù)生成器。

毫無疑問，單向函數(shù)是否存在，是密碼學(xué)中最重要的問題，如果沒有單向函數(shù)，所有這一切都可能被破壞。事實(shí)上，如果單向函數(shù)存在，將證明P/NP問題中，P不等于NP；與之對(duì)應(yīng)，P不等于NP的假設(shè)并不能直接推出單向函數(shù)的存在。

Cryptomania

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

對(duì)這些世界的篩選

大多數(shù)密碼學(xué)家認(rèn)為，至少有一些真正安全的加密方法是存在的，因此我們可能生活在Cryptomania或Minicrypt世界當(dāng)中。但密碼學(xué)家們并不指望很快就能看到這方面的證據(jù)。如果存在這樣的證據(jù)，首先需要排除其他三個(gè)世界，而單單排除Algorithmica本身就已經(jīng)需要解決“P/NP”問題。數(shù)十年來，計(jì)算機(jī)復(fù)雜度領(lǐng)域的科學(xué)家一直在努力解決這一問題，但至今仍未被解決。

不過，密碼學(xué)家最近發(fā)現(xiàn)了一種篩選這些世界的新方法。他們第一次確定了一個(gè)自然問題——有時(shí)間限制的柯氏復(fù)雜性（time-bounded Kolmogorov complexity，簡稱Kt）——的難度等級(jí)在包含密碼學(xué)的世界和不包含密碼學(xué)的世界之間劃出了一條清晰的分界線，如果Kt問題普遍很簡單，那么安全密碼學(xué)就不可能存在，所以我們處于Algorithmica、Heuristica或Pessiland世界當(dāng)中。但如果Kt普遍都很困難，那我們就能找到單向函數(shù)，從而證明我們至少生活在Minicrypt世界中，甚至可能處于Cryptomania世界。

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

研究人員已經(jīng)對(duì)如何消除Pessland世界研究了一段時(shí)間，現(xiàn)在的普遍共識(shí)是，Pessland世界可以被排除，但我不知道我們會(huì)在什么時(shí)候這么做。

密碼學(xué)家也想消除Heuristica世界，而這會(huì)涉及證明如果Kt問題普遍是容易的，那么NP中的每個(gè)問題在所有情況下都是容易的（不僅僅是普遍）。如果能排除這兩個(gè)世界，那將意味著要么我們生活在Algorithmica世界，一切都很簡單；要么我們有足夠的難度來進(jìn)行基本的密碼學(xué)加密。

密碼學(xué)家普遍將這個(gè)目標(biāo)稱為該領(lǐng)域的“圣杯”，并不認(rèn)為自己在有生之年能看到這些問題被證明，但這也是不確定的。（任天）