密碼學是許多區塊鏈協議的核心。從傳統的工作證明(PoW)到L2現代方法(如zk -rollup)，許多高級加密方法提供了區塊鏈運行和協議的基礎。因此，任何區塊鏈體系結構的安全穩定性都是一個普遍存在的問題。我們天真地認為，區塊鏈加密的實現在經受了複雜攻擊後本質上是安全的，但這並不是經驗證明。是否有更好的方法來驗證安全算法的穩定性。答案似乎出現在一篇剛剛贏得美國國家安全局(NSA)“最佳網絡安全研究論文競賽”的新論文中，這在密碼學研究界引起了很大的爭議。

這篇題為“論單向函數和Kolmogorov複雜性”的論文為密碼學五百年來的一個問題提供了答案。當前的問題與一個稱為“單向函數”的數學構造的存在有關，該構造可以證明L2區塊鏈中的零知識證明等方法是否具有密碼保護。

論文地址：https://arxiv.org/abs/2009.11514

現代密碼學的本質是在數據上創建密碼，並希望它們保持安全。然而，我們如何確保它們是安全的呢？這個問題的理論答案出現在20世紀70年代，當時密碼學家提出了單向函數的概念，單向函數是一種數學函數，很容易計算，但很難反轉。說明下單向函數是如何工作的，假設有人讓你將兩個大素數(如485144和999983)相乘。得到485,135,752,552的答案可能需要一些工作，但我們有一個方法可以做到這一點。現在我們來做一個反題，從這個數開始試著確定它的質因數。這是一個極其困難的任務。這就是單向函數的本質。

L1和L2區塊鏈中使用的加密技術的基礎是以單向函數的存在為前提的。如果對於給定的問題存在單向函數，那麼它的密碼保護是安全的，如果沒有，它很可能容易受到不同的攻擊。然而，到目前為止，幾乎不可能證明單向函數的存在。

Kolmogorov的複雜度

在康奈爾大學的研究論文中提出的答案本質上是，單向函數的存在與計算機科學中另一個被稱為Kolmogorov複雜度(KC)的基本問題有關。 KC理論與數字串的複雜性有關。如果你面對兩個較大的數字，6666666666666666666666666666和123948109102912，你不能很好地證明哪個比另一個“更隨機”，但直覺上你會認為第二個數字生成起來更複雜。蘇聯數學家安德雷·柯爾莫戈羅夫用這個想法開創了計算複雜性的新理論。本質上，KC 理論將數字字符串的複雜度定義為產生該字符串作為輸出的最短程序的長度。回到我們的例子，生成第二個數字所需的程序從根本上來說比僅僅打印一個6序列要復雜得多。

KC理論比較複雜，但希望你們已經掌握了核心思想。幾十年來，KC理論已經成為許多計算機科學領域的基礎，但在密碼學中並沒有那麼重要。直到康奈爾大學的研究小組證明單向函數的存在與給定問題的KC有關。簡單地說，如果一個問題是KC複雜的，那麼存在一個單向函數，如果不存在，很可能它就是不存在。

這個簡單的陳述可能會成為現代密碼學中最具革命性的發現之一。

這對區塊鏈世界意味著什麼?

康奈爾大學的論文提供了一種經驗方法來評估L1和L2區塊鏈中使用的加密技術的穩定性。考慮到基於加密技術（例如安全多方計算或零知識證明）的在L2 運行時的出現，這一點變得尤其重要。判斷一個算法是否KC复形比判斷是否存在單向函數簡單得多。當然，這個問題遠遠超出了區塊鏈生態系統的範圍，但如果我們談論的是構建一個新的金融系統的軌道，密碼穩定性是一種基本能力。

Source：https://medium.com/intotheblock/the-paper-that-can-change-the-foundations-of-all-blockchain-cryptography-6df9f077e9d3