有沒有牢不可破的代碼？
這個問題幾千年來一直是密碼學的中心問題，並且是保護網際網路上私人信息的努力的核心。在一份新論文中，康奈爾大學的研究人員發現了一個問題，該問題是所有加密是否都可以破解的關鍵，以及與旨在定義和測量隨機性的數學概念的驚人聯繫。
康奈爾大學計算機科學教授拉斐爾·帕斯（Rafael Pass）說：「我們的結果不僅表明密碼學具有一個自然的&39;問題，而且還表明了數學和計算機科學這兩個非常獨立的領域之間的緊密聯繫-密碼學和算法資訊理論。」科技
Pass是「單向函數和Kolmogorov複雜性」的合著者，該論文將在11月16日至19日在北卡羅來納州達勒姆舉行的IEEE計算機科學基礎研討會上發表。
他說：「結果是，1960年代在蘇聯引入的自然計算問題表徵了基本密碼學的可行性，例如，私鑰加密，數字籤名和身份驗證。」
幾千年來，密碼學被認為是一個周期：有人發明了密碼，直到有人最終破解密碼，然後密碼失效，密碼才有效。在1970年代，尋求更好密碼學理論的研究人員引入了單向功能的概念—單向功能很容易完成，而另一個方向則不可能。
例如，點燃火柴很容易，但是如果不重新排列原子就不可能將燃燒的火柴恢復到熄滅狀態，這是一項極為艱巨的任務。
「想法是，如果我們有這樣的單向功能，也許這是理解密碼學的一個很好的起點，」 Pass說。「對消息進行加密非常容易。而且，如果您擁有密鑰，也可以對其進行解密。但是，不知道密鑰的人應該做的事情與恢復點燃的火柴相同。」
但是研究人員無法證明單向函數的存在。最知名的候選者（也是網際網路上最常用的加密方案的基礎）依賴於整數分解。將兩個隨機質數（例如23和47）相乘很容易，但是如果僅給定乘積1,081，則很難找到這兩個因子。
Pass說，儘管研究人員可能尚未找到正確的算法，但人們認為沒有有效的分解因子算法可用於大量數據。
「我們要解決的中心問題是：它是否存在？是否存在一些自然現象來表徵單向功能的存在？」 他說。「如果這樣做，那就是所有問題的源頭，如果您有解決該問題的方法，則可以打破所有聲稱的單向功能。而且，如果您不知道如何解決該問題，那麼您實際上可以安全密碼術。」