iO（Indistinguishability Obfuscation，不可區分混淆）是密碼學中黑科技一樣的存在，但很多人認為它并不存在。最近，一些研究人員提出了新的 iO 協議。

　　2018 年，加州大學洛杉磯分校博士生 Aayush Jain 前往日本演講，介紹他和同事正在開發的一款強大的加密工具。在他陳述團隊在 iO 方面的努力時，有觀眾提問：「我認為 iO 不存在。」

　　當時，這種看法較為普遍。如果 iO 確實存在，它不僅可以隱藏數據集合，還可以隱藏計算機程序的內部工作機制，創造出強大的加密工具。哈佛大學計算機科學教授 Boaz Barak 表示，這是「掌控一切的密碼學原語」，而這種力量的強大讓人們懷疑 iO 是否真的存在。

　　2013 年，計算機科學家 Sanjam Garg、Amit Sahai 等人首次提出 iO 的候選版本，后來其他研究者找出了對其安全性進行攻擊的方法。「誰將贏得勝利， the makers or the breakers？」

　　加州大學伯克利分校西蒙斯計算理論研究所負責人 Shafi Goldwasser 表示：「當時很多人對此很狂熱，他們相信 iO 的存在，并堅持研究。但后來這些人越來越少了。」

　　而近期，Aayush Jain 與華盛頓大學副教授 Huijia Lin、Jain 的導師 Amit Sahai 合作的一項研究為 maker 站臺。這篇于 8 月 18 日線上發布的論文首次展示了，如何僅使用「標準」安全假設來構建 iO。

　　論文鏈接：https://eprint.iacr.org/2020/1003.pdf

　　加州大學伯克利分校博士生、論文一作 Aayush Jain

　　所有的加密協議都依賴于一些假設，譬如著名的 RSA 算法基于一條被普遍認同的觀點：標準計算機無法對兩個大素數的乘積進行因式分解。加密協議的安全性和其假設有關，之前的 iO 基于未經測試、最終被證明不可靠的假設。而最新的協議依賴于經過廣泛使用和研究的安全假設。

　　盡管這一協議距離現實部署還很遙遠，但它從理論角度提供了一種即時構建多個加密工具的方式，而這在之前是不可能的。例如，它允許創建「可否認」加密和「函數」加密。

　　以色列理工學院教授 Yuval Ishai 表示：「現在應該不會有人懷疑 iO 的存在了。」

　　iO：密碼學「皇冠上的明珠」

　　數十年來，計算機科學家一直在思考是否存在安全、全面的方式來實現計算機程序混淆，使人們能夠在不了解其內部秘密的情況下使用它們。程序混淆可以支持大量實際應用，如使用混淆程序在銀行或電子郵件賬戶中向他人委派任務，而無需擔心別人濫用該程序或讀取你的賬戶密碼。

　　但截至目前，所有構建現實混淆器的嘗試都失敗了。2001 年，理論層面也出現了壞消息：最強大的混淆形式「黑盒混淆」是難以實現的。（黑盒混淆即攻擊者無法了解程序內部，只能看到程序的使用及其輸出。）Boaz Barak、Amit Sahai 以及其他五位研究者證明，一些程序自己揭示了內部秘密，它們無法實現完全混淆。

　　不過，這些程序是專門創建來抵抗混淆的，與現實程序沒有太多相似之處。因此，計算機科學家希望存在另外一些混淆，它足夠弱因此是可行的，又足夠強能夠隱藏人們真正關心的秘密。證明黑盒混淆不可能實現的研究者在論文中提出了一個可能的替代方案：iO。

　　乍一看，iO 并不是特別有用的概念。它不要求隱藏程序的秘密，只要求程序足夠混淆，比如你有兩個可執行相同任務的不同程序，你無法區分哪個是混淆版本，哪個是原版。

　　Aayush Jain 導師、UCLA 教授 Amit Sahai，也是 iO 候選版本的提出者之一。

　　但是，iO 實際上要強大得多。例如，假設你有一個程序，可以執行一些與銀行賬戶相關的任務，但是它包含未加密密碼，因此易受攻擊。但是，只要有一個執行同樣任務但能夠隱藏密碼的程序，不可區分混淆器就可以成功地 mask 密碼。

　　近年來，計算機科學家證明 iO 可以作為幾乎所有加密協議的基礎（除了黑盒混淆），包括經典的加密任務（如公鑰加密）和新興任務（如全同態加密）。它還涵蓋無人知道如何構建的加密協議，如可否認加密和函數加密。

　　康奈爾大學教授 Rafael Pass 表示：「這是皇冠上的明珠。一旦實現，我們可以獲得一切。」

　　2013 年，Sanjam Garg、Amit Sahai 等人提出 iO 候選版本，將一個程序分割成多個「拼圖塊」，然后使用多重線性映射混淆單個「拼圖塊」。把所有拼圖塊拼在一起后，所有混淆互相抵消，程序運轉如常，但是每個單獨的「拼圖塊」看起來是無意義的。當時，這一研究結果被視為一大突破，并引發了后續大量相關論文。然而幾年后，其他研究者發現多重線性映射并不安全。之后又出現了其他 iO 候選版本，但也都被攻破。

　　當時，很多人擔心 iO 可能只是個無法實現的奇跡。

　　少即是多

　　2016 年，Huijia Lin 開始研究能否通過簡單地減少多項式計算，來解決多重線性映射的缺陷。多重線性映射本質上是多項式計算的加密方式。Jain 表示：「這些映射類似于多項式計算器，并與包含變量值的 secret locker 相連接。」機器接受用戶輸入的多項式，用戶可以查看最終 locker，以了解隱藏值能否使多項式的值為 0。

　　為了確保該方案的安全性，用戶不應了解有關其他 locker 的信息或者過程中生成的任何數字。Sahai 表示：「我們希望這是真的，」但是，在研究人員提出的所有候選多重線性映射中，打開最終 locker 的過程中總是泄露出本該隱藏的計算信息。

　　華盛頓大學副教授、該研究第二作者 Huijia Lin。

　　研究人員提出的的多重線性映射均存在安全漏洞，Lin 想知道是否有一種方法，不必計算那么多不同種類的多項式也能構建 iO（因此更容易被安全地構建）。

　　四年前，Lin 發現了僅使用某些類型的多重線性映射構建 iO 的方法，這些映射計算「階數（degree）」為 30 或者更小的多項式（這意味著每個項是最多 30 個變量的乘積）。接下來的幾年中，Lin、Sahai 和其他研究者致力于如何將階數降得更低。直到能夠使用三階多重線性映射構建 iO。

　　理論上，這似乎是一個巨大的進步。但它仍存在一個問題：從安全的角度講，三階實際上與任意階多項式處理機器一樣差。

　　研究者了解如何安全構建的唯一多重線性映射是二階或者更低階的多項式處理機器。Lin 與 Jain、Sahai 一道，試圖找出用二階多重線性映射構建 iO 的方法，他們在這個問題上掙扎了很久。

　　盡管探究過程充滿艱辛，但最終他們提出了一種新的想法：由于 iO 需要三階映射，而計算機科學家只能安全構建二階映射，那么二者是否存在折中方案？比如 2.5 階映射？

　　研究者設想了一個系統，其中某些 locker 具備清晰的窗口，因此用戶能夠查看其中包含的值。這使得機器不需要保護太多的隱藏信息。為了在高階多重線性映射的能力與二階映射的安全性之間取得平衡，機器可以使用高于二階的多項式進行計算，但是有一個限制：隱藏變量的多項式必須為二階。研究者稱他們試圖不隱藏太多信息，并證明能夠安全構建這類混合 locker 系統。

　　要將這些功效較弱的多重線性映射轉換為 iO，還需要最后一個要素：一種新型的偽隨機數生成器。它可以將一串隨機位擴展為更長的字符串，并且仍具有隨機性。

　　該研究的最終成果是能夠避免多重線性映射安全弱點的 iO 協議。

　　該方案的安全性基于在在其他加密環境中被廣泛使用的四個數學假設，這些假設歷史悠久，研究時間最短的假設相關問題都可以追溯到 20 世紀 50 年代。

　　只可能有一種情況會打破該研究提出的新 iO 協議，那就是全功率量子計算機。四個假設之一易受量子攻擊，但最近的一些研究已經提供了通往 iO 的另一種潛在途徑，保證它即使受到量子攻擊也是安全的，不過它所依賴的假設沒有那么堅固。有研究者表示，在未來的研究中可以將兩種方法結合起來，創造出既基于標準安全假設又能抵擋量子攻擊的 iO 版本。

　　這可能會吸引新的研究人員加入。當理論上存在可行性時，那么就會有更多人愿意加入研究團隊。毫無疑問，在該協議（或其變體）用于實際應用之前，計算機科學領域仍然有很多事要做。