四個假設論證「不可區分混淆」存在性，華人科學家觸摸「皇冠上的明珠」

  • 2020 年 11 月 25 日
  • AI

作者 | 蔣寶尚
編輯 | 青暮 
在密碼學中,一直存在一種黑科技般的概念：Indistinguishability Obfuscation。中文翻譯為不可區分混淆，簡稱為iO。 
iO是否存在一直是個迷，學者們為了論證它也打了非常多的「架」。這個概念（iO）又稱為Crypto-complete（密碼學完備）的，如果它真的存在，那麼就可以基於IO構建出幾乎所有的密碼學構造，包括但不限於公鑰加密、函數加密、數字水印…….
此概念自美國加州大學洛杉磯分校的Sahai教授及其合作者們提出之後，有人狂熱，有人鄙夷。有學者稱：「隨著時間的推移，相信它存在的狂熱分子越來越少了。」
iO的出現最初是為了保護軟體不被破解。其基本思想是：將程式轉換為一種稱為多線性拼圖的遊戲（multilinear jigsaw puzzle），從而將混淆技術的安全性轉化為一類與格（lattice）有關的數學難題。
換句話說，其利用的原理是：如果你使用兩個同等的程式 A 和 B（如把相同值輸入到 A 或 B 里去產生相同的輸入）計算得到 O(A)=P 和 O(B)=P，則在無法進入程式 A 或 B 的情況下，則在計算上分辨 P 來自於 A 還是 B 是不可行的。
可以看出，這個問題在理論上很容易定義，但是符合人們期望的混淆技術在理論上是否存在還是一個很困難的問題。
8月18日，來自華盛頓大學和加利福尼亞大學的三位研究者發表了一篇名為「Indistinguishability Obfuscation from Well-Founded Assumptions」的文章，在文章中作者用「標準」的安全假設構建了IO。這三位作者中，Huijia Lin本業畢業於浙江大學，2011年在康奈爾大學獲得博士學位，目前是華盛頓大學的副教授。
具體而言，他們證明了四個假設：
1.關於素數階為p=O(2^λ)的非對稱雙線性群的SXDH假設，
2.在Zp上的LWE假設，次指數模數雜訊（subexponential modulus-to-noise ratio）比為2^(ke)。
3.在Zp上的LPN假設，且具有多項式的LPN樣本和錯誤率1/L^δ。
4.Boolean PRG在NC^0中的存在性。
有了上述四個假設，那麼IO對於所有的多項式邏輯線路（polynomialsize circuits）都是存在的。
此篇論文的作者之一在接受採訪中表示，新的研究結果應該會讓IO懷疑論者安靜下來。「現在，人們將不再懷疑IO的存在。」

1

IO：皇冠上的明珠

幾十年來。電腦科學家一直在思考，是否存在一種方法，能夠安全的、全方位的混淆電腦程式呢？為了不讓使用電腦程式的用戶弄清楚程式原理（反編譯），科學家們做了很多努力。
康奈爾大學Rafael Pass 稱這個問題為「密碼學皇冠上的明珠」，「一旦找到通用的方法，你就會得到一切」。
而當前程式混淆有兩種方式，第一種是全文替換關鍵詞，把整段程式碼中所有的「命名」全部替換成數字（例如b4452)；第二種是直接輸出編譯過後的程式碼（可執行文件），這樣別人就沒法直接打開這個文件看到原本的程式碼了。
這兩種方式的目的都是在導出程式的時候，把標註性的符號（symbols）摘除掉。從而達到不暴露原本源碼資訊的效果。
但比較可惜的是，當今常用的這兩種方法，其實並不能作為真正意義上的混淆。
文章鏈接：//zhuanlan.zhihu.com/p/270364254?utm_source=qq
知乎網友@Steven Yue一篇介紹介紹IO的時候，指出：」在密碼學的定義上是非常脆弱的。這就像是上世紀二戰的時候，我們通過各種各樣的暗號以及暗碼來加密通訊的電報，然後在另一頭通過某一本小說或者報紙來解讀出原文一樣。整個系統的目的就在我們使用各種亂碼一樣的名字，錯綜複雜的邏輯結構（比如循環展開），以及不同的表述方式（把C變成彙編），儘可能使得看到我們最終混淆輸出的人無法從輸出中有效的提取和源程式碼有關的資訊來。」

          
比如說上述的C混淆程式碼，雖然說看似一團亂碼，我們作為人類難以去理解這串程式碼到底在做什麼。但是如果我們一旦把這樣的程式碼放入編譯器中，去分析整個程式語言的語法結構，把每一行的指令做的事情都歸納出來的話，那麼就能看出些端倪來了。
一開始，科學家們採用虛擬黑盒混淆（Virtual Black Box Obfuscation），這個機制可以簡單理解為輸入和輸出之間有一個摸不透的黑盒，此黑盒保護輸出無法反推輸入。但隨後在2001年的時候被證明通用的黑盒混淆是絕對不可能的。
此後，這一方向就分為了兩派，一派是繼續研究黑盒混淆，另一派則是研究則研究Indistinguishability Obfuscation。

2

研究歷程

2013年Sahai聯合其他五位學者發布文章「Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits」，提出IO協議，其基本思想正如前面提到的「把一個程式轉換為一種稱為多線性拼圖的遊戲（multilinear jigsaw puzzle），從而將混淆技術的安全性轉化為一類與格（lattice）有關的數學難題。」
這一混淆技術從概念上來看，具備了黑箱混淆器的大多數特性。當時也被稱為一種突破，並引發了數十篇後續論文。但在提出的幾年內，已遭受了領域內一大批專家（包括提出者）的第一輪攻擊。
後來有研究者證明：在混淆過程，使用多線性映射是不安全的。這時候IO是否存在的質疑聲又甚囂塵上。
2016年，在本科畢業於浙江大學，現在是華盛頓大學副教授的Huijia Lin，開始研究有可能減少對多線性配對（Multilinear maps）的需求，從而繞過IO機制的弱點。
確實，多線性配對存在致命的缺點。多線性配對本質上只是用多項式計算的一種方式。它由數字和變數之間的和與乘積組成，如3xy+2yz^2。這些映射需要一個類似多項式計算器的東西，連接到一個包含變數值的「秘密儲物櫃系統」。用戶在機器上輸入一個機器接受的多項式時，可以查看最後一個儲物櫃。從而找出隱藏的值是否使多項式的值為0。因此，打開最後一個「儲物櫃」的過程中，透露了本應隱藏的計算資訊。
接下來幾年中，她發現，減少使用多線性配對確是可行！緊接著，她把多線性配對的維度（層數）降到了5層。同在2017年的時候，她與Tessaro在中成功的把這一要求降到了3層。這也就是說，只要我們擁有一個三線性配對（Trilinear Map）的構造，就可以IO。
但是，這時候又有學者質疑：從論文上看，這似乎是一個巨大的進步，但是從安全的角度來看，3次好像還是差點意思。
於是，Huijia Lin 與 Jain以及Sahai聯手探索2次多線匹配的方法。但是研究過程似乎陷入了沉默之中，久久找不到方向。
後來另一位研究區塊鏈的學者Christian Matt提出了一種折中的方法，由於IO似乎需要3次，但電腦科學家只有2次，是否有一種介於兩者之間的東西？2.5次？
後來Huijia Lin也考慮到，這些只用2.5次的「混合儲物櫃」系統可以安全地建造。.基於這種並不需要強大的多線性配對思想，Huijia Lin和她的團隊發明了一種新型的偽隨機性生成器。此隨機生成器可以將一串隨機比特擴展成更長的字元串，其隨機性足以愚弄電腦。
以上就是Jain、Lin和Sahai在他們的新論文中想出的方法。另外，論文中的方案依賴於四個數學假設，這些假設在其他密碼學環境中已經有了廣泛應用。即使是研究最少的假設—LWE假設（learning parity with noise），在20世紀50年代就有了相關研究。
但是，雖然證明了iO存在性，但仍然有一樣東西能夠破壞所有的美好：量子電腦。如果量子電腦建成了，那麼四個假設就很容易受到量子攻擊，IO的理論就會受到威脅。
另外，有三篇獨立的論文也提供了一條不同的通往IO的潛在途徑，即使面對量子攻擊也可能是安全的。研究人員稱：「此版本的IO依賴於不那麼確定的安全假設」。

參考資料：
//www.quantamagazine.org/computer-scientists-achieve-crown-jewel-of-cryptography-20201110/

點擊閱讀原文，直達ICLR小組！

VirMach 便宜 VPS

QNews

QNews