朗讀我們生活在計算宇宙的哪個密碼世界當中？第我們生活在計算宇宙的哪個密碼世界當中？

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

《我們生活在計算宇宙的哪個密碼世界當中？》完，請繼續朗讀精采文章。
喜歡 科學報 cn-n.net，請記得按讚、收藏及分享。