近乎完美的電腦安全系統可能即將降臨

    加入我們永遠收到最新的消息

Quanta Magazine

這個方法稱為「不可區分的混淆(indistinguishability obfuscation)」或「IO」。作者將它吹捧為加密的「中央樞紐」:重建像是公鑰或選擇性安全簽名等熟悉的編碼方法。論文中主要用數學式來解釋IO。

這個研究讓很多人產生興趣,但在公布這個研究之後的兩年內,電腦科學研究人員在IO實作上遇到了很多挑戰與阻礙。其中一項是IO相當緩慢。混淆一個程式的延遲時間不是以分鐘或小時來計算,而是用一輩子來計算。此外,這個方法並不如預期像數學式保全那樣安全。

但過去幾個月,有許多研究論文都提供了從2013年公布以來最重要的進展。一些研究人員認為我們再十年就可以做出一個工作系統,或是更早。加州大學洛杉磯分校計算機科學家,也是這兩篇論文的共同作者Amit Sahai說:「現在看起來已經沒有任何比較大的限制了。IO非常強大,而且幾乎可以做任何我們想得到的工作。」研究人員相信如果IO可以採用簡單的數學重建,即使是量子電腦也無法突破IO。

一整座山的小小步伐

加密

不可區分的混淆一開始是用兩個不同計算程式(例如等義方程式f(x) = x(a + b) 與 f(x) = ax + bx )得到完全相同的結果。對於任何三組輸入(a、b、x,)每個程式都得到與另一個程式相同的結果,只有中間過程不同。如果給IO兩個相同的程式,編碼出來的結果會讓使用者不管怎麼看都無法分辨出哪個是哪個。

2013年的論文讓很多人相信IO有那個能力可以明顯擴大加密的範圍,但研究中並沒有提到如何實作。研究人員遇到兩個主要的挑戰:第一個是要提升程序速度,第二個是要保證IO的安全性。

IO現在仍然是不實際的。任何加密方法或多或少都會讓計算程序變慢。IO的情況則是,如山一樣高的方程式需要用不可區分處理,會大大拖慢速度。

積極參與IO研究的麻省理工學院密碼學家Vinod Vaikuntanathan說:「要讓一個程式混淆跟執行能需要上百年。當你發現數字這麼誇張的時候,你就不會再關心確切的數字。」

一般計電腦科學家用來加速執行時間的方法是減少大程式的混淆讓更小連結的程式混淆。科學家要採用這個方式模糊化一個程式需要兩個步驟。改善任一步驟都可以讓整個計算過程更有效率。

第一個步驟比較困難。現在用的IO方法一開始會從稱為「靴式載入bootstrapping」的程式開始(夠小可以進行混淆)。這個程式與大的「目標target」程式互動。靴式載入程式如同安全性泡泡般包圍著目標程式的輸入與輸出進行工作:將所有輸入與輸出做混淆處理,有效地進行整個目標程式的混淆處理。

但是,即使是針對小靴式載入程式,也都還沒有人想出要如何更有效地做混淆處理。她說:「就像是要找『盔甲的縫隙』一樣,靴式載入程式這部分真的讓我們卡住了。」

研究人員在第二個步驟有比較多的進展。一旦靴式載入程式就定位之後,接下來的挑戰是混淆處理更長更多樣化的計算。在俄勒岡州波特蘭舉辦的年度計算機理論座談會(STOC)上,有三個研究小組示範了如何從用混淆處理單一電路(研究人員已經知道理論上要如何進行),進到混淆處理普通計算機(或說是電腦理論科學家眼中的圖靈機)。

這是個大躍進。為了要混淆處理單一電路,研究人員需要提前知道輸入的大小以及計算的每個步驟。相較之下,電腦可以讀取任意長度的輸入,將更多的計算看成是更多資料的輸入。在STOC裡介紹了如何用稱為打洞程式編寫(punctured programming)的技術將較長、不停輸入的計算當做是一連串的離散、相連、電路尺寸的步驟進行混淆處理。

某一篇在STOC發表的論文之共同作者,哥倫比亞大學電腦科學家Allison Bishop說:「主要的技術成果是將IO應用到電路上,將計算區域化再將所有的東西綁在一起,讓你可以保護整體的計算過程。」

AllisonBishop

Allison Bishop

透過數學驗證的安全性

讓IO更有效率可以解決實作上的問題。建立高安全性則可以解決根本的問題。

當Sahai與德州大學奧斯汀分校電腦科學家Brent Waters在2013年敘述如何使用IO的時候,這個混淆處理被相信可以用來保護程序裡的機密。它們一開始的工作有點像是打一個看起來很複雜的結(看起來很難復原),但如果沒有更加了解這個結的結構,無法確定會不會其實有個簡單的方法可以解開。

Portrait of Dr. Brent Waters in the Department of Computer Sciences, College of Natural Sciences for a feature story on cybersecurity.

Brent Waters

Vaikuntanathan說:「那時候只有一個架構,連要怎麼去探討它的安全性都還不清楚。」

後來情形有改善了。任何以數學作為基礎的優良加密方式會定義好入侵者要進行突破時需要處理的問題。例如RSA編碼,是用兩個主要的大數字產生出結果。要讀取你的郵件,入侵者必須回推出相乘出這個結果的兩個數字:以目前電腦的能力限制,這個工作是不可能做到的。

一個加密方式的基礎數學式需要有困難度,也需要簡單、可以久經考驗並且容易理解,讓密碼專家可以有信心這問體看起來就是有那麼難。

Sahai說:「根據既有經驗,這個方法必須是一個我們可以了解的數學問題,否則可能會被突破。」

在2013年沒有一個安全性系統是採用IO實作。一年之後的2014年4月,Waters、Bishop以及(紐約州約克鎮高地IBM研究院湯瑪士.J.華生研究中心科學家)Graig Gentry共同發表了兩篇論文炒熱了IO,論文提到一些簡單方法(利用一種稱為多線性圖的數學元素)。(Sahai是其中一篇的共同作者。)Bishop說:「我們認為攻擊者如果以任何方式突破『IO』,他必定正在開其中一個問題。」

多線性圖僅在2013年被介紹過應用在加密。專家們還沒有時間去嚴格確認它的可靠性。Waters說:「現在,如果這些多線性圖座標被破解,並不會帶來太大驚訝。」

如今,電腦科學家都試著要想出如何用一個更容易懂的數學障礙取代多線性圖。最有希望的似乎是「學習錯誤(learning with errors,LWE)」,一個需要機器學習的問題。LWE與多線性圖有共同的數學祖先「晶格密碼學(lattice-based cryptography)」,所以看起來有機會取代多線性圖。然而,還沒有人想出要如何產生大躍進。

Vaikuntanathan說:「就好像看著對岸的懸崖,看起來很近,好像可以跳過去一樣,但事實上不是只有這個問題。」

安全性的急迫性

Cryptography

儘管IO面臨挑戰,專家們還是相信以IO為基礎的安全性方法即將出現。Sahai指出加密延遲時間在理想與實作之間的差距高達30年。從這兩年的進度來看,他認為IO可以比那個時間差距更早準備好,他說:「我們希望能縮短到10到15年。」

IO安全性的主要里程碑是簡單的數學基礎。這個領域中最傑出的人物認為目前情況正在加速IO的進展。Bishop說她「不反對」高安全性的簡單組合方式會在10年內發展出來的說法。Vaikuntanathan說得更強勢「我甚至認為只要再過幾年。」

這些樂觀的態度要歸功於這兩年投入IO研究的資源。Sahai現在是加州大學洛杉磯分校加密功能中心的董事。該中心致力於混淆研究,創立於2014年,美國國家科學基金會捐贈五百萬贊助,由Waters與Bishop共同擔任首席研究員。此外,去年秋天,美國國防部高級研究計畫局(DARPA)宣布成立SafeWare,進行一項支持「用數學驗證安全屬性之高效率且廣泛應用的混淆方法」的研究計畫。

這麼急著發展IO,表示出IO的能力,也顯示出加密學固有的貓抓老鼠遊戲。當研究人員正在發展新的安全性策略的同時,另一群人也努力進行量子電腦的工作,如果他們達到目的,他們的計算速度將會讓幾乎所有的加密方式變無效,(也許)除了IO。

量子安全加密是個棘手的問題,還沒有哪一個方法在量子基礎的計算法下被證明是完全安全的。

原始報導由Quanta雜誌同意轉載,Quanta雜誌是由西蒙斯基金會獨立編輯出版,基金會的主要工作是藉由報導數學、物理及生命科學相關的發展與趨勢,來增加大眾對科學的了解。
加入好友
來源: Wired