據國外媒體報道，許多計算機科學家專注于解決困難的計算問題，但在計算機科學的一個領域，困難是所有人都想獲得的優(yōu)勢這是密碼學領域，人們希望在對手和他們的秘密之間建立不可逾越的障礙

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

為了創(chuàng)建一個真正安全的加密方法，我們需要一個足夠難的計算問題，給對手設置一個不可逾越的障礙我們知道有許多計算問題似乎很難解決，但也許我們只是不夠聰明來解決它們或者其中的一些問題可能比較難，但是難度不適合安全加密從根本上說，密碼學家想知道:宇宙中是否有足夠的困難使安全加密成為可能

1995年，美國加州大學圣地亞哥分校的Russell Impagliazzo將難度問題分解為一系列子問題，使計算機科學家能夠一步步解決為了總結這一領域的知識狀態(tài)，他描述了五個可能的世界，并將其命名為Algorithmica，Heuristica，Pessiland，Minicrypt和Cryptomania——富有想象力——難度和加密可能性逐漸增加其中任何一個都可能是我們生活的世界

算法a

在這個世界里，最自然的計算問題都很容易，使得加密成為不可能在這里，可以找到有效解決方案的問題集不僅包含我們已經找到解決方案的問題，還包含另一個稱為NP集的所有問題NP類問題由能有效檢驗解的準確性的問題組成大致來說，P類問題是可以在計算機上快速解決的問題，而NP類問題可以快速確定一個可能的解是否正確

從表面上看，P和NP感覺是不同的范疇以一個日常問題為例:決定你的行李箱是否能裝下所有要打包的旅行物品如果你有朋友幫你收拾，你可以很容易地確認他們是否收拾好了所有東西——只需檢查一下少了什么所以這個行李箱打包問題屬于NP可是，自己收拾行李要困難得多——你可能要嘗試許多不同的方式來整理東西目前還不清楚是否有有效的算法來解決物品和行李箱所有可能的組合換句話說，我們不知道這個問題是否屬于P類問題

加密方案的解密問題也屬于NP問題畢竟，如果你有一個加密的消息，而你的朋友聲稱已經解密了它，那么你可以通過將他們解密的消息輸入到加密機中來檢查它，看看輸出結果是否與原始的加密消息匹配

在算法的世界里，P和NP是同一類問題算法能證明這一點是一件幸事，因為這意味著有快速算法來處理行李箱打包等NP級問題以及其他看似困難的問題但對密碼學家來說將是一場災難，因為在這個世界上，我們可以有效地解密

大多數計算機科學家認為P不同于NP，原因很簡單，NP中有許多我們無法有效解決的問題可是，沒有人能證明它，盡管P/NP問題被認為是過去50年理論計算機科學中最著名的問題除了最聰明的人不斷失敗，我們沒有證據證明P不等于NP，這個很難證明

啟發(fā)式

在這個世界上，有一些NP類的問題是不容易解決的，但是每個NP類的問題都是容易平均的，也就是說在大多數情況下都是可以有效解決的例如，如果我們生活在Heuristica世界，有一種高效的行李打包算法幾乎總能成功，但對于一些罕見的行李和物品組合可能會失敗

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

佩西蘭

這是所有可能的世界中最糟糕的在佩西蘭世界，一些NP類的問題即使平均起來也是非常難的對于這些問題，任何有效的算法都會失敗——不是偶爾，而是經常可是，這些問題對于隱藏秘密信息并不那么有效

我們絕對不想生活在偽世界，在那里我們得到了復雜性的所有不好的方面，同時，我們也沒有任何像密碼學這樣的優(yōu)勢。

迷你密碼

在這個世界上，NP中的一些問題平均難度很大，這個難度足以構造密碼學最基本的積木:單向函數這是一個可以有效執(zhí)行但不能有效反轉的函數:對于每一個輸入，函數值都很容易計算，但對于一個隨機函數值，很難計算其對應的輸入密碼學家已經證明，安全加密需要一個單向函數如果單向函數存在，我們將得到一系列實用的加密工具，如密鑰加密，數字簽名，偽隨機數發(fā)生器等

毫無疑問，單向函數的存在是密碼學中最重要的問題如果沒有單向函數，這一切都可能被破壞其實單向函數存在的話，就證明了P/NP問題中P不等于NP，相應的，P不等于NP的假設也不能直接推導單向函數的存在性

神秘躁狂

在這個世界里，我們有足夠的難度去創(chuàng)造Minicrypt世界里的任何東西，甚至創(chuàng)造出更高級的加密協(xié)議，比如公鑰加密。

這些世界的篩選

大多數密碼學家認為，至少存在一些真正安全的加密方法，因此我們可能生活在密碼狂熱或迷你密碼世界中但是密碼學家不指望很快看到這些證據如果有這樣的證據，需要先排除其他三個世界，只排除Algorithmica就能解決P/NP問題幾十年來，計算機復雜性領域的科學家一直在試圖解決這個問題，但至今仍未解決

可是，密碼學家最近發(fā)現(xiàn)了一種篩選這些世界的新方法他們第一次確定了一個自然問題的難度水平——有時間限制的基爾希納復雜性——并在包含加密技術的世界和不包含加密技術的世界之間畫出了一條清晰的分界線如果Kt問題一般很簡單，那么安全密碼學就不可能存在，所以我們處在Algorithmica，Heuristica或者Pessiland的世界里但如果Kt普遍困難，那么我們可以找到一個單向函數，從而證明我們至少生活在Minicrypt的世界里，甚至可能生活在Cryptomania的世界里

這一新結果意味著，計算機科學家只要能證明另一個命題如果Kt問題普遍容易，那么NP中的所有問題都容易，就可以排除Pessland這個最壞的世界在這種情況下，我們可以簡化為:Minicrypt和Cryptomania是Kt問題普遍困難的世界，Algorithmica和Heuristica是Kt問題一般容易解決的世界

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

密碼學家還希望消除啟發(fā)式世界，這將涉及到證明如果Kt問題通常是容易的，那么NP中的每個問題在所有情況下都是容易的如果我們能排除這兩個世界，那將意味著要么我們生活在Algorithmica世界，一切都很簡單，要么我們有足夠的難度來執(zhí)行基本的密碼加密

密碼學家一般將這個目標稱為該領域的圣杯，他們認為在有生之年不會看到這些問題被證明，但這也是不確定的。

本文地址：http://www.dayishuiji.com/xiaofei/25994.html - 轉載請保留原文鏈接。

免責聲明：本文轉載上述內容出于傳遞更多信息之目的，不代表本網的觀點和立場，故本網對其真實性不負責，也不構成任何其他建議；本網站圖片，文字之類版權申明，因為網站可以由注冊用戶自行上傳圖片或文字，本網站無法鑒別所上傳圖片或文字的知識版權，如果侵犯，請及時通知我們，本網站將在第一時間及時刪除。