構建無法破解的密碼，是眾多密碼學科學家的目標。

圖片來源：Kiel Mutschelknaus for Quanta Magazine一種被稱為不可區分混淆的加密方式因為太過完美，多年來被認為無法實現。不過最近，三名研究者首次證明不可區分混淆是可行的，這或許是通往完美密碼的重要一步。2018年，加州大學洛杉磯分校的研究生Ayush Jain前往日本，就他和同事正在開發的強大加密演算法進行交流。當他講述團隊正在嘗試實現不可區分混淆（indistinguishability obfuscation，簡稱iO）時，一位觀眾困惑地舉起了手。“可我一直以為iO不存在？”他說。當時，這樣的懷疑是普遍存在的。不可區分混淆如果可以被構建，不僅能隱藏資料集，還能隱藏程式本身，從而構建一種可以實現幾乎所有其他加密協議的加密演算法。但對很多計算機科學家來說，強大到如此地步讓iO看起來難以實現。計算機科學家從2013年開始提出iO的候選版本。但是他們很快被潑了一盆冷水，其他研究者發現了破解它安全性的方法。現在，Jain與華盛頓大學的林惠嘉（Huijia Lin，音譯），以及Jain在加州大學洛杉磯分校的導師阿米特·沙海（Amit Sahai）一起證明了這種方法的可行性。在8月18日在網上公開的論文裡，這三名研究者首次展示瞭如何僅用“標準的”安全假設來構建不可區分混淆。

從左至右依次為Jain、沙海和林惠嘉所有的加密協議都基於某些假設，比如著名的RSA演算法，基於人們普遍認為的觀點——標準計算機不能快速對大數進行質因數分解。加密協議的安全性和前提假設是繫結的，而iO的前提假設建立在未經檢驗並且不牢固的基礎上。相比之下，新的加密協議建立在經過廣泛檢驗的假設基礎之上。雖然協議還遠未能實用，但從理論上講，透過它可以立即構建一系列以前遙不可及的加密方式。例如，它支援建立可否認加密（deniable encryption），這種加密方式可以讓你向攻擊者傳送和真實郵件完全不同的訊息；以及函式加密（functional encryption），這種加密可以讓你向用戶提供不同級別的訪問許可權，從而用資料進行計算。以色列理工學院的尤瓦爾·伊沙伊（Yuval Ishai）說：“現在不會有人懷疑不可區分混淆的存在了，這似乎是個不錯的結局。”皇冠上的寶石几十年來，計算機科學家一直都想知道是否存在安全，包羅永珍的方法來混淆計算機程式，讓人們使用的同時無法破解。要想知道不可區分混淆是什麼，我們不妨先來看一看混淆是什麼。例如，對於程式設計師來說，最寶貴的自然是程式碼，一旦原始碼被別人看到了，那麼基本上花的心血和智慧財產權都被人一覽無餘。為了保護程式碼，可以在匯出程式之前採取一些手段來混淆程式，現在一般有兩種程式混淆方法，即程式碼混淆（Code Obfuscation）和程式碼編譯（Compilation）。程式碼混淆是為了防止程式程式碼本身給外人提供太多資訊，同時使程式的執行效率更高。在匯出程式時，會將所有標註性的符號（symbols）摘除掉。比較簡單的方法是直接全文替代關鍵詞，例如將全文的ui_controller替代為a0123456，這樣程式的符號就無法暴露程式運轉內容了。程式碼編譯更簡單，直接輸出編譯後的程式碼，將人們可以看懂的原始碼轉換成電腦看得懂的機器碼。這個過程，就相當於把上面提到的符號全部抹除了，他人看到我們釋出的可執行檔案中的機器碼時，自然看不懂其中發生了什麼。但對人的混淆並不是嚴格意義上的混淆，這樣的混淆在密碼學的定義上是非常脆弱的。在電腦程式的分析下，“混淆”後的程式會變得一覽無餘，一下就能看出程式在幹什麼。真正意義上的混淆被稱作虛擬黑盒（Virtual Black Box Obfuscation，VBB）。將一個程式C嵌入一個黑盒中，我們可以在黑盒的一端輸入x，另一頭會輸出C(x)。因為整個程式都藏在黑盒中，我們完全無法得知任何C的構造資訊。唯一可以做的，就是提供輸入x，觀察另一頭的輸出C(x)。我們稱這樣的黑盒為VBB混淆器O，對於經過O混淆的程式C，我們稱其為O(C)。O(C)的輸出C(x)並不會暴露任何關於C的任何資訊。如果實現虛擬黑盒，使用者可以使用程式卻無法理解程式本身，那麼就能讓開發的程式永遠不被破解，或是用很簡單地實現公鑰加密。密碼學中幾乎所有比較高階的構造都可以非常簡單地用虛擬黑盒實現。但虛擬黑盒的概念提出不久後，人們很快就被潑了一盆冷水。2001年，七位大牛聯手對混淆這一概念做了系統性的研究，並且發表了一篇文章：On the (Im)possibility of Obfuscating Programs。在文章中，他們提出了一種特殊構造的程式，並證明其無法被混淆。而這等於是在說：通用的VBB混淆是絕對不可能的。不過，同樣是在這篇論文中，一種混淆的新型定義被提出來了——如果一對程式C1和C2具有相同的功能性，能否透過一種新的混淆演算法，使第三方無法區分兩個程式的混淆結果呢？對於這樣的混淆，我們稱之為不可區分混淆（iO）。雖然VBB不可能實現，但是透過iO，我們仍然可以非常完美地混淆一個程式。假如我們有一個程式P，我們可以用五花八門的辦法和技巧來混淆程式，得到一個最強混淆功能卻相同的P*。同時，如果我們擁有iO，那麼完全不需要很多費勁的混淆操作，可以直接得到相同的結果，因為我們無法區分混淆後的iO(P)和iO(P*)。僅僅是給P套了一層iO，得到的結果和最強混淆過後P*的iO是一樣的。

圖片來源：知乎使用者@Steven Yue這樣一來，如果我們想充分混淆一個程式P，使其構造不被別人發現，只需要輸出iO(P)就行了。有了強大的不可區分混淆，我們就能完美加密已有的程式，使其永遠不會被破解。同時，由於iO密碼學完備（Crypto-Complete）的特性，我們可以輕易借其實現一系列強大的密碼學構造。更少即是更多2013年，沙海和五位合著者提出了一個iO協議，將程式拆成幾部分，類似拼圖，然後他們使用多線性配對來找出這些拼圖。單個碎片看上去毫無意義，但如果將碎片正確地組合到一起，程式就能正常工作。多線性配對本質上是用多項式計算的密碼學方法——由不同變數和數字之積的加和組成的數學表示式，如3xy+2yz²。Jain表示，這些配對有點類似於一個連線著多項式計算器的密碼保險櫃。使用者輸入數字，看向最後一位，看保險櫃中隱藏的數值能否讓整個多項式歸零。為了保證計劃的安全，使用者不能獲知整個過程中任何引數。但是在所有可能的多線性配對候選中，開啟保險櫃的過程，都透露了計算過程中應該隱藏的資訊。由於多線性配對機制全都有安全性問題，林惠嘉開始探索能否透過約束多線性配對的層數來實現iO。（這樣更容易實現安全性）四年前，她想出瞭如何用30層多線性配對構建iO。接下來幾年裡，她、沙海和其他研究者逐漸想出瞭如何只用3層多線性配對來實現iO。表面上看，這是一個巨大的進步。但有一個問題——從安全的角度來看，3層多項式配對和其他任意層一樣不穩固。研究人員們只知道2層及以下的多線性配對是安全的。林惠嘉與Jain和沙海聯手，試圖找出如何用2層多線性配對應設構建iO。但是，“我們被困住了很久很久。“林惠嘉這樣說。最終，他們與加州大學聖巴巴拉分校的普拉漢漢·安納思（Prabhanjan Ananth），區塊鏈專案Concordium的克里斯蒂安·馬特（Christian Matt）一起，想出了一個折中方案：既然iO需要三層，但計算機科學家為了安全需要二層，中間是否存在2.5層呢？研究人員設想了一個系統，其中保險櫃上有窗，使用者可以看到部分密碼的值。這讓整個機制不需要隱藏太多資訊。為了平衡多線性匹配的能力和二層的安全性，這個機制允許計算高於二階的多項式，但有一個限制——多項式被隱藏的變數必須不能超過二階。林惠嘉說：“我們試圖不去隱藏那麼多。”

圖片來源：quanta magazine但是從不太強的多項式配對到iO，團隊還缺少最後一塊拼圖——一種新型的偽隨性數生成器，它能將一串隨機的資料轉換成擴充套件成更長，更隨機的一串。而這正是Jain，林惠嘉和沙海在新論文中想出來的。結果是，iO協議最終避免了多項式配對的安全性漏洞。“他們的結果看起來幾乎是完美的。”康奈爾大學的拉斐爾·帕斯（Rafael Pass）說。該方案的安全性基於四個數學假設，這些假設已經被廣泛的應用於其他加密方式中。即使是被研究最少的假設——“Learning Parity with Noise“假設——也和20世紀50年代以來一直被研究的問題有關。很可能只有一種東西能打破新的方案——量子計算機，如果我們能造出真正的量子計算機的話。四個假設中的一個容易受到量子攻擊，但過去的幾個月裡，帕斯和其他研究者分別獨立地在論文中得到同一個結果，這一結果提供了一條不同的潛在路徑，讓iO在量子攻擊下也能確保安全。研究人員表示，相較於Jain，林惠嘉和沙海的版本，這些新版本的iO基於不太成熟的安全假設。哈佛大學的博阿茲·巴拉克（Boaz Barak）說：“但它是有可能的。這兩種嘗試可能在接下來的幾年融合，創造一種基於標準安全假設上，能抵禦量子攻擊的新版iO。伊沙伊預測，Jain，林惠嘉和沙海的創造可能吸引新的研究者進入該領域，讓該方案更加實用並作出一些新的嘗試。他說：“一旦你知道某件事原則上是可能的，就會讓這個領域的研究者在工作時心理上好受得多。”在協議（或者是其變體）可用於實際應用之前，計算機科學家還有許多工作要做。但研究人員表示這是意料之中的。帕斯說：“密碼學中有很多概念，當它們第一次出來的時候，人們會說：‘這只是純理論，（它）與實踐無關。’然後10年20年後，Google開始實施這些計劃。”巴拉克說，從理論突破到實際可用的協議還有很長一條路要走。“但是你可以想象。或許50年後密碼學教科書上會說，‘好吧，這裡有一個很簡單的iO構造，我們能從中得到其他所有加密方式。’”他說。原文連結：https://www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/部分內容經授權轉載自知乎使用者@Steven Yuehttps://zhuanlan.zhihu.com/p/270364254