據(jù)國(guó)外媒體報(bào)道，許多計(jì)算機(jī)科學(xué)家專注于解決困難的計(jì)算問(wèn)題，但在計(jì)算機(jī)科學(xué)的一個(gè)領(lǐng)域，困難是所有人都想獲得的優(yōu)勢(shì)這是密碼學(xué)領(lǐng)域，人們希望在對(duì)手和他們的秘密之間建立不可逾越的障礙

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

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

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

算法a

在這個(gè)世界里，最自然的計(jì)算問(wèn)題都很容易，使得加密成為不可能在這里，可以找到有效解決方案的問(wèn)題集不僅包含我們已經(jīng)找到解決方案的問(wèn)題，還包含另一個(gè)稱為NP集的所有問(wèn)題NP類問(wèn)題由能有效檢驗(yàn)解的準(zhǔn)確性的問(wèn)題組成大致來(lái)說(shuō)，P類問(wèn)題是可以在計(jì)算機(jī)上快速解決的問(wèn)題，而NP類問(wèn)題可以快速確定一個(gè)可能的解是否正確

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

加密方案的解密問(wèn)題也屬于NP問(wèn)題畢竟，如果你有一個(gè)加密的消息，而你的朋友聲稱已經(jīng)解密了它，那么你可以通過(guò)將他們解密的消息輸入到加密機(jī)中來(lái)檢查它，看看輸出結(jié)果是否與原始的加密消息匹配

在算法的世界里，P和NP是同一類問(wèn)題算法能證明這一點(diǎn)是一件幸事，因?yàn)檫@意味著有快速算法來(lái)處理行李箱打包等NP級(jí)問(wèn)題以及其他看似困難的問(wèn)題但對(duì)密碼學(xué)家來(lái)說(shuō)將是一場(chǎng)災(zāi)難，因?yàn)樵谶@個(gè)世界上，我們可以有效地解密

大多數(shù)計(jì)算機(jī)科學(xué)家認(rèn)為P不同于NP，原因很簡(jiǎn)單，NP中有許多我們無(wú)法有效解決的問(wèn)題可是，沒(méi)有人能證明它，盡管P/NP問(wèn)題被認(rèn)為是過(guò)去50年理論計(jì)算機(jī)科學(xué)中最著名的問(wèn)題除了最聰明的人不斷失敗，我們沒(méi)有證據(jù)證明P不等于NP，這個(gè)很難證明

啟發(fā)式

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

從密碼學(xué)的角度來(lái)看，Heuristica和Algorithmica A并沒(méi)有太大的區(qū)別，如果我們?cè)贖euristica的世界里提出一個(gè)加密方案，會(huì)有一些快速的解密方法，幾乎可以處理每一條消息，從而使得方案在實(shí)際場(chǎng)景中毫無(wú)用處。

佩西蘭

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

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

迷你密碼

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

毫無(wú)疑問(wèn)，單向函數(shù)的存在是密碼學(xué)中最重要的問(wèn)題如果沒(méi)有單向函數(shù)，這一切都可能被破壞其實(shí)單向函數(shù)存在的話，就證明了P/NP問(wèn)題中P不等于NP，相應(yīng)的，P不等于NP的假設(shè)也不能直接推導(dǎo)單向函數(shù)的存在性

神秘躁狂

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

這些世界的篩選

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

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

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

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

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

密碼學(xué)家一般將這個(gè)目標(biāo)稱為該領(lǐng)域的圣杯，他們認(rèn)為在有生之年不會(huì)看到這些問(wèn)題被證明，但這也是不確定的。

本文地址：http://www.dayishuiji.com/xiaofei/25994.html - 轉(zhuǎn)載請(qǐng)保留原文鏈接。

免責(zé)聲明：本文轉(zhuǎn)載上述內(nèi)容出于傳遞更多信息之目的，不代表本網(wǎng)的觀點(diǎn)和立場(chǎng)，故本網(wǎng)對(duì)其真實(shí)性不負(fù)責(zé)，也不構(gòu)成任何其他建議；本網(wǎng)站圖片，文字之類版權(quán)申明，因?yàn)榫W(wǎng)站可以由注冊(cè)用戶自行上傳圖片或文字，本網(wǎng)站無(wú)法鑒別所上傳圖片或文字的知識(shí)版權(quán)，如果侵犯，請(qǐng)及時(shí)通知我們，本網(wǎng)站將在第一時(shí)間及時(shí)刪除。