密碼學是許多區塊鏈協議的核心。從傳統的工作量證明 (PoW) 到 L2 現代方法（如 ZK-rollups），許多高級加密方法爲區塊鏈運行時和協議提供了基礎。因此，關於任何區塊鏈架構的安全穩健性都存在一個無所不在的問題。天真地，我們假設在復雜攻擊中幸存下來的區塊鏈加密實現本質上是安全的，但這遠非經驗證明。有沒有更好的方法來驗證安全算法的魯棒性。答案似乎在一篇剛剛贏得美國國家安全局 (NSA) 的「最佳網絡安全研究論文競賽」的新論文中，這在密碼學研究界引起了很大的轟動。
這篇題爲「單向函數和 Kolmogorov 復雜性」的論文爲密碼學中的一個 500 周年問題提供了答案。手頭的問題與存在稱爲「單向函數」的數學結構有關，該結構可以證明 L2 區塊鏈中的零知識證明等方法是否是加密安全的。
現代密碼學的本質依賴於在數據上創建密碼，希望它們保持安全。但是，我們如何確保它們是安全的？這個問題的理論答案出現在 1970 年代，當時密碼學家提出了單向函數的概念，單向函數是易於計算但難以反轉的數學函數。爲了說明單向函數的工作原理，想想如果有人要求您將兩個大素數相乘，如 485144 和 999983。得到數字 485,135,752,552 作爲答案可能需要一些工作，但我們有一種方法可以做到這一點。現在讓我們來回答反問題，從數字开始，嘗試確定它的質因數。這是一項極其艱巨的任務。這是單向函數的本質。
(相关资料图)
圖源：Codeprg
L1 和 L2 區塊鏈中使用的密碼技術的基礎是以單向函數的存在爲前提的。如果給定問題存在單向函數，那么它的加密保護，如果沒有，它可能容易受到不同的攻擊。然而，到目前爲止，幾乎不可能證明單向函數的存在。在他們的論文中，康奈爾大學的研究人員發現了一個與計算機科學的一個晦澀領域相似的答案。
輸入 Kolmogorov 復雜性
康奈爾大學研究論文中提出的答案基本上表明，單向函數的存在與計算機科學的另一個基礎問題有關，即 Kolmogorov 復雜性 (KC)。KC 理論與數字串的復雜性有關。如果您看到兩個大數字66666666666666666666 和 123948109102912，您無法完全證明哪個比另一個「更隨機」，但直覺上您認爲第二個數字生成起來更復雜。這是蘇聯數學家 Andrey Kolmogorov 用來开始計算復雜性新理論的想法。本質上，KC 理論將數字字符串的復雜性定義爲產生該字符串作爲輸出的最短程序的長度。
回到我們的例子，KC 理論要復雜得多，但希望您掌握了核心思想。幾十年來，KC 理論已經成爲計算機科學許多領域的基礎，但在密碼學中卻沒有那么重要。直到康奈爾研究小組從帽子裏拿出一只兔子，並證明單向函數的存在與給定問題的 KC 相關。簡單來說，如果一個問題是 KC 復雜的，則存在單向函數，如果不存在，則很可能不存在。
