北京時間 4 月 28 日消息，據(jù)國外媒體報道，許多計算機(jī)科學(xué)家都專注于克服困難的計算問題，但在計算機(jī)科學(xué)的一個領(lǐng)域中，“困難”是所有都想要獲得的優(yōu)勢。這就是密碼學(xué)的領(lǐng)域，身處其中的人都希望在對手和自己的秘密之間設(shè)置難以攻破的障礙。
遺憾的是，我們不知道是否存在絕對安全的加密技術(shù)。幾千年來，人們創(chuàng)造了許多看似不可破解的密碼，但最終都被一一破解。如今，從我們?nèi)粘５幕ヂ?lián)網(wǎng)交易到國家機(jī)密，都受到各種加密方法的保護(hù)，這些方法看似安全，但隨時可能失效。
為了創(chuàng)建一個真正安全（且永久）的加密方法，我們就需要一個足夠困難的計算問題，來為對手設(shè)置一個可證實為不可逾越的障礙。我們知道有很多看起來非常難解的計算問題，但也許只是我們還不夠聰明，無法解決它們?；蛘咂渲幸恍﹩栴}可能很難，但困難的程度并不適合用于安全加密。從根本上說，密碼學(xué)家想知道的是：宇宙是否存在足夠的難度，使安全加密成為可能？
1995 年，美國加州大學(xué)圣地亞哥分校的拉塞爾?因帕利亞佐將難度問題分解為一系列子問題，使計算機(jī)科學(xué)家能夠逐步進(jìn)行解決。為了總結(jié)這一領(lǐng)域的知識狀況，他描述了 5 種可能的世界，并富有想象力地命名為 Algorithmica、Heuristica、Pessiland、Minicrypt 和 Cryptomania—— 難度和加密可能性逐漸上升。這其中任何一個都可能是我們生活的世界。
Algorithmica
在這個世界上，最自然的計算問題都很容易，使得加密變得不可能。在這里，可以找到有效解的問題集 —— 稱為 P 集 —— 不僅僅包含我們已經(jīng)想出解決方案的問題，還包括另一個被稱為 NP 的集合中的所有問題。NP 類問題由可以有效檢驗一個解的準(zhǔn)確性的問題組成。粗略地說，P 類問題就是可以在計算機(jī)上快速求解的問題，而對 NP 類問題則可快速確定某個可能的解是否正確。
表面上看，P 和 NP 感覺像是不同的類別。以一個日常問題為例子：決定你的行李箱能否裝下所有要打包的旅行物品。如果有朋友幫你收拾，你很容易就能確認(rèn)他們是否把所有東西都裝好了 —— 只要檢查一下有什么遺漏的東西就行了。因此，這個行李箱打包問題就屬于 NP。但是，自己收拾行李就難多了 —— 你可能要嘗試很多不同的物品擺放方式。目前還不清楚是否有一種有效的算法能夠解決所有可能的物品和行李箱組合的問題。換言之，我們不知道這個問題是否屬于 P 類問題。
加密方案的解密問題也屬于 NP 類問題。畢竟，如果你有一條加密消息，而你的朋友聲稱已經(jīng)對其進(jìn)行了解密，那么你就可以通過將他們解密的消息輸入加密機(jī)，并查看輸出結(jié)果是否與原始加密消息匹配來進(jìn)行檢查。（當(dāng)然，要做到這一點，你必須擁有一臺加密機(jī)；但是，在密碼學(xué)家看來，這種加密方案是否安全，要看它能否經(jīng)受住獲得這種加密機(jī)的敵人的攻擊。）
在 Algorithmica 世界中，P 和 NP 是同一類問題。證明這一點對算法而言是一件幸事，因為這意味著存在快速算法來處理 NP 類問題中諸如手提箱裝箱及其他看似困難的問題。但對密碼學(xué)家來說，這將是一場災(zāi)難，因為在這個世界中，我們可以有效地進(jìn)行解密。
大多數(shù)計算機(jī)科學(xué)家認(rèn)為 P 不同于 NP，原因很簡單，NP 中有很多問題是我們無法有效解決的。然而，沒有人能夠證明（或反駁）這一點，盡管“P / NP”問題被認(rèn)為是 50 年來理論計算機(jī)科學(xué)中最著名的問題，除了最聰明的人不斷失敗之外，我們沒有證據(jù)表明 P 不等于 NP 很難證明。
Heuristica
在這個世界中，有一些 NP 類問題很不容易解決，但每個 NP 類問題“平均”起來都很容易，意即在大多數(shù)情況下都可以有效解決。例如，如果我們生活在 Heuristica 世界中，那就存在一種幾乎總會成功的高效行李箱打包算法，但對于行李箱和物品的一些罕見組合來說，它可能會失?。ㄟ@些快速且通常成功的算法通常被稱為“heuristic”）。
從密碼學(xué)的角度來看，Heuristica 和 Algorithmica 并沒有太大的區(qū)別。如果我們在 Heuristica 世界中提出一種加密方案，就會存在一些快速的解密方法，可以對幾乎每條消息進(jìn)行處理，從而使得該方案在實際場景中毫無用處。
Pessiland
這是所有可能的世界中最糟糕的。在 Pessiland 世界中，一些 NP 類問題即使平均起來也都十分困難。對于這些問題，任何有效的算法都會失敗 —— 不是偶爾失敗，而是經(jīng)常失敗。然而，這些難題對隱藏秘密信息而言卻不是那么有效。
我們絕對不想住在 Pessiland 世界中，在這里，我們得到了（計算）復(fù)雜性的所有不好的方面，同時又沒有任何像密碼學(xué)那樣的優(yōu)勢。
Minicrypt
在這個世界中，NP 中的一些問題平均起來都很難，而這種困難程度足以構(gòu)建密碼學(xué)最基本的構(gòu)建塊：單向函數(shù)。這是一種可以有效執(zhí)行但不能有效逆轉(zhuǎn)的函數(shù)：對于每一個輸入，函數(shù)值都容易計算；但對于一個隨機(jī)的函數(shù)值，算出其對應(yīng)的輸入?yún)s很困難。密碼學(xué)家已經(jīng)證明，安全加密需要單向函數(shù)。如果單向函數(shù)存在，我們就會得到一系列實用的加密工具，比如秘鑰加密、數(shù)字簽名和偽隨機(jī)數(shù)生成器。
毫無疑問，單向函數(shù)是否存在，是密碼學(xué)中最重要的問題，如果沒有單向函數(shù)，所有這一切都可能被破壞。事實上，如果單向函數(shù)存在，將證明 P / NP 問題中，P 不等于 NP；與之對應(yīng)，P 不等于 NP 的假設(shè)并不能直接推出單向函數(shù)的存在。
Cryptomania
在這個世界中，我們有足夠的難度創(chuàng)建出 Minicrypt 世界中的任何東西，甚至還可以創(chuàng)建出更高級的加密協(xié)議，如公鑰加密（在這種協(xié)議中，人們可以在不知道密鑰的情況下發(fā)送加密的消息）。
對這些世界的篩選
大多數(shù)密碼學(xué)家認(rèn)為，至少有一些真正安全的加密方法是存在的，因此我們可能生活在 Cryptomania 或 Minicrypt 世界當(dāng)中。但密碼學(xué)家們并不指望很快就能看到這方面的證據(jù)。如果存在這樣的證據(jù)，首先需要排除其他三個世界，而單單排除 Algorithmica 本身就已經(jīng)需要解決“P / NP”問題。數(shù)十年來，計算機(jī)復(fù)雜度領(lǐng)域的科學(xué)家一直在努力解決這一問題，但至今仍未被解決。
不過，密碼學(xué)家最近發(fā)現(xiàn)了一種篩選這些世界的新方法。他們第一次確定了一個自然問題 —— 有時間限制的柯氏復(fù)雜性（time-bounded Kolmogorov complexity，簡稱 Kt）—— 的難度等級在包含密碼學(xué)的世界和不包含密碼學(xué)的世界之間劃出了一條清晰的分界線，如果 Kt 問題普遍很簡單，那么安全密碼學(xué)就不可能存在，所以我們處于 Algorithmica、Heuristica 或 Pessiland 世界當(dāng)中。但如果 Kt 普遍都很困難，那我們就能找到單向函數(shù)，從而證明我們至少生活在 Minicrypt 世界中，甚至可能處于 Cryptomania 世界。
這個新結(jié)果意味著計算機(jī)科學(xué)家只要能證明另一個命題，“如果 Kt 問題普遍很容易，那么 NP 中的所有問題也都很容易”，就可以消除 Pessland—— 最糟糕的世界。在這種情況下，我們可以簡化為：Minicrypt 和 Cryptomania 是 Kt 問題普遍困難的世界；Algorithmica 和 Heuristica 是 Kt 問題（以及 NP 中其他所有問題）普遍容易的世界。
研究人員已經(jīng)對如何消除 Pessland 世界研究了一段時間，現(xiàn)在的普遍共識是，Pessland 世界可以被排除，但我不知道我們會在什么時候這么做。
密碼學(xué)家也想消除 Heuristica 世界，而這會涉及證明如果 Kt 問題普遍是容易的，那么 NP 中的每個問題在所有情況下都是容易的（不僅僅是普遍）。如果能排除這兩個世界，那將意味著要么我們生活在 Algorithmica 世界，一切都很簡單；要么我們有足夠的難度來進(jìn)行基本的密碼學(xué)加密。
密碼學(xué)家普遍將這個目標(biāo)稱為該領(lǐng)域的“圣杯”，并不認(rèn)為自己在有生之年能看到這些問題被證明，但這也是不確定的。
廣告聲明：文內(nèi)含有的對外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。