有沒有牢不可破的代碼？
這個問題幾千年來一直是密碼學的中心問題，並且是保護互聯網上私人信息的努力的核心。在一份新論文中，康奈爾大學的研究人員發現了一個問題，該問題是所有加密是否都可以破解的關鍵-以及與旨在定義和測量隨機性的數學概念的驚人聯繫。
“我們的結果不僅表明密碼學有一個自然的’母親’問題，而且還表明了數學和計算機科學這兩個非常獨立的領域之間的深層聯繫-密碼學和算法信息論，”拉斐爾·帕斯（Rafael Pass）表示，康奈爾科技公司。
Pass是“單向函數和Kolmogorov複雜性”的合著者，該論文將在11月16日至19日在北卡羅來納州達勒姆舉行的IEEE計算機科學基礎研討會上發表。
他說：“結果是，1960年代在蘇聯引入的自然計算問題表徵了基本密碼學的可行性，例如，私鑰加密，數字簽名和身份驗證。”
幾千年來，密碼學被認為是一個週期：有人發明了密碼，直到有人最終破解密碼，然後密碼失效，密碼才有效。在1970年代，尋求更好密碼學理論的研究人員引入了單向功能的概念-單向功能很容易完成，而另一個方向則不可能實現。
例如，點燃火柴很容易，但是如果不重新排列原子就不可能將燃燒的火柴恢復到熄滅狀態，這是一項極為艱鉅的任務。
“想法是，如果我們有這樣的單向功能，也許這是理解密碼學的一個很好的起點，” Pass說。“對消息進行加密非常容易。而且，如果您擁有密鑰，也可以對其進行解密。但是，不知道密鑰的人應該做的事情與恢復點燃的火柴相同。”
但是研究人員無法證明單向函數的存在。最知名的候選人-也是互聯網上最常用的加密方案的基礎-依賴整數分解。將兩個隨機質數（例如23和47）相乘很容易，但是如果僅給定乘積1,081，則很難找到這兩個因子。
Pass說，儘管研究人員可能尚未找到正確的算法，但人們認為沒有有效的分解因子算法可用於大量數據。
“我們要解決的中心問題是：它是否存在？是否存在一些自然現象來表徵單向功能的存在？” 他說。“如果這樣做，那就是所有問題的源頭，如果您有解決該問題的方法，則可以打破所有聲稱的單向功能。而且，如果您不知道如何解決該問題，那麼您實際上可以安全密碼術。”
同時，1960年代的數學家們確定了所謂的Kolmogorov複雜度，這是指量化一串數字的隨機性或模式。數字字符串的Kolmogorov複雜度定義為可以生成字符串的最短計算機程序的長度。對於某些字符串，例如121212121212121212121212121212，有一個簡短的程序可以生成它-交替為1和2。但是對於更複雜且看似隨機的數字字符串，例如37539017332840393452954329，可能不存在比字符串本身長度短的程序。
長期以來，這個問題引起了數學家和計算機科學家的關注，其中包括計算機科學與工程學名譽教授Juris Hartmanis。由於試圖生成該數字的計算機程序可能需要數百萬甚至數十億年的時間，因此1960年代的蘇聯研究人員以及1980年代的Hartmanis等人開發了時限性的Kolmogorov複雜度-最短的程序，可以在一定時間內輸出一串數字。
在論文中，Pass和博士生Liu Yanyi表示，如果計算有時間限制的Kolmogorov複雜度很困難，則存在單向函數。
儘管他們的發現是理論上的，但它對包括互聯網安全在內的密碼學都有潛在的影響。
“如果您能提出一種解決有時間限制的Kolmogorov複雜性問題的算法，那麼您可以破壞所有加密，所有加密方案，所有數字簽名，” Pass說。“但是，如果不存在解決該問題的有效算法，則可以獲得單向功能，因此可以獲得安全的加密和數字簽名等。”
該研究部分由國家科學基金會和空軍科學研究所資助，並且基於由國家情報局局長辦公室的情報高級研究項目活動資助的研究。
