密碼學視角

2012 (註：根據內文判斷演講日期為 2014)

作者：Shafi Goldwasser

現在很高興為大家介紹 Shafi Goldwasser，她是 MIT 的 RSA 教授，同時也是 Weizmann 研究所的教員。好的，我的演講題目是「密碼學視角」(The Cryptographic Lens)。我很高興能在這裡，STOC 2014 發表這場演講，因為我第一次參加的電腦科學會議也是 STOC 會議，在 1982 年。所以那是我第一次參加的會議。地點在舊金山。這也是我第一次發表論文的會議，論文是關於機率加密，我們將其命名為「Probabilistic Encryption and How to Play Mental Poker, Keeping Secret All Partial Information」(機率加密與如何在不洩露任何部分資訊的情況下玩心理撲克)，我想這篇論文也在圖靈獎引用過。這也是我第一次發表演講。事實上，我和 Silvio 的約定是，因為他之前已經在 STOC 發表過論文，這次輪到我發表演講。作為交換，這次我讓他先講。我覺得這是一個錯誤。如果我早知道的話，也許我們會換個方式。總之，不是開玩笑，我非常感謝 Silvio 多年來的合作、友誼、啟發以及所有那些建議。只是他現在才給我，如果我早知道的話。好的。我特別喜歡那隻貓看著鏡子，看到獅子的圖像。你們可能不知道，但顯然 Silvio 的母親說，他小時候堅持讓他們叫他「獅子」好幾年。好的。所以我們現在是 2014 年，第一次會議是 1982 年。正如我們所知，理論電腦科學從 1970 年代至今，經歷了巨大的旅程。1982 年對我來說是一個重要的中間點。它發現了許多關於計算本質的基礎思想。我在這裡列出了一些我最喜歡的：非決定性、隨機性、同步、並行、容錯、互動、局部性。如果你回到 1982 年，我們今天視為理所當然的許多事情當時都是未知的。我們不知道線性規劃在 P 中，也不知道質數測試在多項式時間內完成等等。所有這些宏偉的定理都是在這些年裡被證明的。不僅僅是這些令人驚嘆的演算法進步和基礎概念，我們還對技術產生了許多影響。當我們剛開始時，理論是電腦科學的一個深奧領域。現在它已成為搜尋演算法和引擎等的骨幹。在科學領域也是如此，你經常聽到物理學家談論透過 Shor's algorithm 等對量子計算產生興趣。以至於人們創造了「計算視角」(computational lens) 這個詞，來描述如何透過計算的稜鏡來看待科學、工程、技術，並將電腦視為在生物學、物理學、宇宙等領域發生的抽象過程。但今天我要談論的是另一個視角，我稱之為「密碼學視角」(cryptographic lens)。所以我要告訴你們，透過這個密碼學視角，你們可以如何根據 Shafi 的觀點看待理論電腦科學。

密碼學的歷史與現代密碼學的興起

在我們開始這個故事之前，我發現歷史上一個有趣的現象是，這個領域的兩位重量級人物或重要人物，領域的創始人，是 Shannon 和 Turing，一位是資訊理論的發明者，一位是通用電腦的發明者。他們兩人也以在密碼學領域的工作而聞名。事實上，對於大眾來說，他們可能更認識 Turing 是破解 Enigma machine (德國密碼機) 的人，而不是通用 Turing machine 的發明者。有趣的是，Shannon 同時進行了兩篇論文的工作。一篇是《The Mathematical Theory of Communication》(通訊的數學理論)，他在其中引入了資訊理論。另一篇是《A Communication Theory of Secrecy Systems》(機密系統的通訊理論)，他在其中定義了完美隱私系統的需求，如何實現它，以及你所能做到的範圍限制。事實上，他本人證明這兩個結果是相互關聯的。它們彼此激發了動機，儘管其中一篇因為機密原因較晚發表。我這張幻燈片的主要重點不是因為我喜歡歷史（我了解很少），而是因為那兩個人在密碼學上的興趣是由戰時研究激發的。他們工作的動力，事實上，我想他們曾在戰爭期間在 Princeton 碰過面，是因為他們對如何擊敗敵人、如何贏得戰爭感興趣。這也是我們談論現代密碼學時與之不同的地方。

當我們思考現代密碼學時，我們不只是思考對抗某些壞人、一個敵人、一場戰時努力。實際上，它產生於數位電腦正成為現實的時期，以及人們試圖思考如何利用這一切進步來促進經濟增長的時候。事實上，現代密碼學既關注計算的正確性也關注其隱私性。因此，許多結果討論正確性，許多結果討論隱私，並且不只用於保護通過敵方陣線的某些通訊。

現代密碼學的能力與核心概念

這次演講我想談三個重點。其中一個是，現代密碼學實現了許多在我看來非常迷人的能力，這些能力在本質上似乎是矛盾的。第二個是，它一直是許多概念和技術的催化劑，這些概念和技術導致了理論電腦科學領域一系列真正的飛躍，我認為是真正的思想新範式。最後，我認為它不僅實現了所有這些矛盾、優美的密碼學能力，並促進了廣泛理論的進步，而且它實際上還有一個美好的未來。因為今天我們擁有所有這些大量的數據、巨大的連通性，並且有一個非常迫切的問題：現在怎麼辦？所有這些都公開了。所有這些神奇的能力都存在。我們還能否保留一些基本權利？我讀過 Judge Brandeis 大約在 1890 年的一篇文章，他說我們有「獨處的基本權利」。我認為這是一句很棒的引言。在這個時代，我們在某種意義上還能否「獨處」？我認為密碼學，以及其中一些我將向你們介紹的工具，確實是我們在某種程度上能夠「獨處」的最佳機會。

好的，讓我從這些密碼學實現的催化性、矛盾性能力開始。這是一個列表。顯然我不會談論所有這些，但我只是簡要提及它們。我認為許多人了解其中很多事情，主要是因為密碼學非常迷人。你知道，這非常酷，而且我想你們很多人甚至在小學時就嘗試過創造密碼和破解密碼等。所以這是一系列這類能力。

我會放在這裡的第一個是，人們可以在從未見面的情況下交換秘密資訊，我們稱之為「公開金鑰密碼學」(public cryptography)。這是一個驚人的概念，如果你仔細想想的話。你們都認為這是理所當然的，但從一開始，這似乎是不可能的。第二個是，位於世界各地遙遠地方的兩個人有可能「同時簽署合約」(sign a contract simultaneously)。顯然，他們如何能同時做到？資訊應該從一方傳到另一方再傳回來，但不知何故，我們可以使用密碼學手段來模擬這種同時性。第三個是，我們可以從非常少的隨機性開始，「確定性地生成非常非常長的字串」(generate very, very long strings deterministically)，這些字串在所有實際應用中都像隨機字串一樣好。接下來是，我們可以在不揭示證明內容的情況下「證明定理」(prove theorems without revealing the proof)，Silvio 提到的「零知識證明」(zero knowledge proof)，我會更多地談論它。我們可以在世界各地「玩數位遊戲」(play games, digital games) 而無需紙牌、無需裁判，並且當有人被宣布為贏家時能夠彼此信任。這也是因為密碼學的思想。我們可以從資料庫中「檢索資訊」(retrieve information from databases)，而資料庫不知道我們實際在尋找什麼資訊。現在我們可以做到在「加密資料上進行計算」(compute on encrypted data)，並且越來越多。

這看起來像是一個待辦事項列表。你可以為其中每一個項目開一門課程。所有這些發明有什麼共同點？統一的主題是，存在一個「敵人」(enemy)。所以存在一個「對手」(adversary)，它是問題定義的一個組成部分。我總是喜歡說，即使在演算法導論課程中，他們也談論對手，因為他們說演算法在一定的時間內運行，他們證明這一點的方法是說存在一個由對手選擇的輸入，它是最糟糕的輸入，即使對於那個輸入，演算法也運行得很快。但這裡不同，因為我們不是在談論分析，而是真正談論問題的定義。如果沒有對手，就不會有問題。換句話說，如果兩個人通訊而世界上沒有對手，他們為什麼要加密？只有在有人試圖竊聽時才有意義。如果有證明，我為什麼要給你看證明？我為什麼要寫證明？沒有人懷疑它。為什麼我們不直接稱之為一個主張？當你談論隨機性時，是相對於誰的隨機性？所以對手是問題定義的一個組成部分，因此，他實際上也會決定一個解決方案的品質。所以我們會說一個解決方案是好的還是壞的。

核心概念：計算不可區分性與模擬範式

在任何在多項式時間內運行的應用中。所以你可以選擇給誰安慰劑，給誰藥。任何你能想到的應用都在多項式時間內運行。如果你無法區分，那就意味著這個應用在偽隨機序列上的表現，與在真正的隨機序列上的表現一樣好。所以這顯然是正確的定義。此外，可以證明，如果單向函數 (one-way functions) 存在，你就可以構造出偽隨機數生成器和偽隨機函數。好的。接下來，再一個例子。這個例子非常及時。現在密碼學領域有很多關於「程式碼混淆」(obfuscation) 的研究。我不知道你們有沒有聽說過。如果你參加了上一次會議，肯定聽說過。程式碼混淆是什麼意思？通常我們認為程式碼混淆就是一個程式，我們想把它弄亂。這樣我們就有一個新的程式，你不知道如何進行逆向工程。那麼你如何形式化地定義這一點呢？一種可能的定義方法，就是使用「計算不可區分性」(computational indistinguishability)，你可以觀察混淆一個程式的所有方式，然後觀察混淆第二個程式的所有方式。你需要要求，如果這兩個程式實際具有相同的輸入-輸出關係，儘管它們一開始是不同的程式，你仍然無法區分你得到的是第一個程式的混淆版本還是第二個程式的混淆版本。這是一個定義。事實證明，在某些假設或某些計算問題下，你可以構造出滿足這個定義的程式。而且這似乎是一個非常強的定義，它使你能從程式碼混淆中獲得你想要的許多應用。好的，這是第一個公理的部分。我們還做什麼？好的，我們有了計算不可區分性。我們可以將它應用於這些不同的問題。但是這個對手，你知道，有時候他並不是躲在帷幕後面按按鈕、觀察樣本。有時候對手是系統的一部分。所以他可能是系統的參與者之一。他不是坐在外面。我們如何談論在這樣的對手存在下的安全？所以這時候我們說的是，作為一個局內人（比如在這場對話中）的視角，將給予他「零知識」(zero knowledge)。我們如何定義這一點？我們說，如果他基本上可以在家裡自己模擬這場對話。這就是所謂的「模擬範式」(simulation paradigm)。它本質上是說，如果他可以在家裡自己模擬，他完全可以待在家裡。參與協議並不能讓他獲得任何好處。所以協議不會引入任何漏洞。當然，他可能會獲得一些好處。也許他在 Amazon 上買東西。問題是，他現在破壞系統的能力不會比他在家裡用自己的模擬電腦工作時更強。同樣，如果你能證明一個協議具有這種強度，那麼你就能證明你可以組合這類協議以及許多其他事情。好的，所以這兩種思維方式是我們的兩種基石：計算不可區分性和模擬。它們使我們能夠在密碼學中證明許多定理。

密碼學作為理論電腦科學的催化劑

現在讓我們轉到我之前提到的那些催化性發展，我認為密碼學在理論電腦科學領域中扮演了非常重要的角色。我這裡將分成幾欄，但讓我們從最為人所知的開始，也就是 Silvio 也提到的關於「證明」(proofs) 的討論，我會在這次演講中更多地談論它。正如我們所知，「零知識證明」(zero-knowledge proof)，在某種意義上，暫且不談零知識，它們引入了「機率可驗證證明」(probabilistically checkable proofs) 的概念，這演變成了許多其他的機率系統，並導致了許多關於「近似難度」(hardness of approximation) 的有趣且不同尋常和令人驚訝的結果。我將其列在第一位，既因為它廣為人知，也因為我想談談這個發展對今天，對我們如何將計算委託給雲端的影響。

另一個發展是「偽隨機性」(pseudorandomness)。偽隨機數生成器和函數也是早期的密碼學目標，因為我們想生成大量的隨機性，以便在我們的隨機化密碼學演算法中使用。結果發現，硬度 (hardness) 和隨機性 (randomness) 之間存在著有趣的對偶關係，並且可以做到。但它們有著非常令人驚訝的應用。第一個應用可能不令人驚訝，那就是如果你有一個偽隨機數生成器，為什麼不用它來「去隨機化」(derandomize) 複雜度類別？這似乎說得通。也許不那麼說得通的是它效果如此之好，但邏輯上它是說得通的。但後來也證明了，如何利用偽隨機函數來形式化一些我們可以證明是「不可學習」(not learnable) 的概念。所以它為我們提供了一些在某些概念類別中學習不可能的例子。這也是 Rasbov 和 Rudish 在使用「自然證明」(natural proofs) 進行下界證明時，一些不可能性的背後原因。

繼續。接下來這個，我認為是我最喜歡的之一，因為它是一種不同尋常的發展。密碼學中我們想要的東西不僅僅是單向函數，我們還有一個概念，就是我們想要某樣東西非常困難。所以我們想找到這些「核心位」(hard core bits)，本質上是不可能猜對的機率高於 50-50 的東西。關於一般函數核心位的第一個結果是由 Goldreich 和 Levin 提出的。他們有一個非常有趣的證明，結果這個證明雖然是為密碼學目標而設定的，但它展示了如何為 Hadamard 碼 (一種著名的錯誤糾正碼) 提出一種多項式時間「列表解碼」(list decoding) 演算法。這是一個令人難以置信的發展的開端，「列表解碼」幾乎變得比例外更普遍。這在資訊理論和錯誤糾正碼領域是一個懸而未決的問題，突然之間，Reed-Solomon 碼有了 Madhu 的著名工作，還有長長的列表。直到今天，我們實際上擁有符合列表解碼界限的顯式碼。這是 Goswami 和合著者的工作，我總記不住名字，抱歉。但無論如何，這確實是一個令人難以置信的驚人發展。從一個證明技巧（它表明反轉一個函數等價於預測單個位）到這種列表解碼的進展。

下一個。下一個是這樣的。Oblivious transfer (不經意傳輸) 是一種非常奇怪的機制，是 Michael Rabin 在訪問 Berkeley 的一個夏天發明的，他想要一個以下的遊戲，這對密碼學家來說似乎是很自然的事情，但我必須承認原因並不清楚。Oblivious transfer 的想法是，有兩方，一方想向另一方傳送資訊，但不是直接傳送，他想在不知道自己是否傳送了的情況下傳送資訊。好的，所以我「不經意地傳輸」它。有時候我傳輸，有時候我不傳輸。這似乎價值可疑，但事實證明它實際上非常基礎。而且 Oblivious transfer 的想法本身轉變為一種稱為「私有資訊檢索」(private information retrieval) 的東西，其想法是你可以有一個資料庫，你可以在資料庫中搜尋（比如說）關鍵字，而資料庫並不會知道你在尋找哪個關鍵字。好的，當然我不能給你歸約，但兩者之間有直接聯繫。而這又導致了 Shafi 認為的許多其他研究，關於「局部可解碼碼」(locally decodable codes)。這些是錯誤糾正碼，你可以不看整個損壞的碼字，只需要看本地少數幾個位置，就能恢復原始資訊字在本地的位置，這具有令人難以置信的重要性，也具有實際意義，而且現在，我們再次有了亞線性解碼的線性率碼。

最後，我的最後一條線索（雖然不是最後一個發展）是關於「技術」(techniques)。到目前為止，我們討論了結果、模型、以及引發其他問題的問題。技術呢？密碼學的核心是我們要為對手設置一些「困難的問題」。這些困難的問題，僅僅在最壞情況下難是不夠的，因為密碼學發生在現實世界中。我們需要「平均情況下困難」(average case hard) 的問題。所以我們需要將最壞情況歸約到平均情況問題的技術，這就是我們開發了「隨機自歸約」(random self-reducibility) 技術等等。現在，這些技術意味著如果你能將一個問題從最壞情況歸約到平均情況，那就意味著本質上沒有最壞情況。所有東西在平均情況下都困難。但它也意味著如果這個問題是容易的，那麼它 everywhere 都容易。你有辦法將一個實例映射到另一個。事實上，透過程式檢查 (program checking) 等工作，下一個想法是這種映射如何以局部的方式完成。所以你想檢查一個全局屬性，你通過將全局屬性轉換為檢查平均局部屬性來做到這一點，這在某種意義上是「屬性測試」(property testing) 的基本技術。我們想在不閱讀所有內容的情況下進行測試。我們想通過進行一些局部隨機測試來測試，因此也許能夠在亞線性時間而不是線性時間甚至更少的時間內工作。所以我這裡就不說嘗試破解 RSA 對因數分解和量子因數分解的改進等影響了。那些是顯而易見的。我試圖提供一些不太明顯的東西，並希望說服你。

零知識證明與其催化作用

他很天真，但沒那麼天真。所以他做的是，他隨機選擇是要看第一個方程的解還是第二個方程的解。重點在於，如果她無法解決其中一個解，他至少有 50-50 的機會會要求她提供那個解，然後他就會發現她的錯誤。所以事實上，我們最終得到的是什麼？如果兩個方程都有解，她總是能夠滿足他的問題。如果兩個方程都沒有解，他最好的情況就是 50-50。如果我們一遍又一遍地重複這個過程，每次都提出新的方程，如果原始方程沒有解，她能夠滿足他的機會將會非常小。太棒了。這只是一個例子。但事實是，所有零知識證明在某種意義上都是這樣工作的。到目前為止，我還沒有談論零知識，但那些有趣、即使沒有零知識、利用互動的證明，都是這樣工作的。你拿著證明，以某種方式將它變成另一個被分成若干部分的證明，這樣如果所有部分都為真，那麼原始證明就存在，然後你只展示其中一部分，由驗證者隨機選擇哪一部分。太好了。

為什麼我口語上將其稱為「零知識」(zero-knowledge)？因為他從未看到兩個方程，因此他永遠無法推導出原始解。事實上，他看到的幾乎都是垃圾。這產生了 Silvio 正在談論的「互動證明」(interactive proofs) 的概念，我知道人們了解這一點，但這是我的圖靈演講。更一般地說，我們有一個證明者 (prover) 和一個驗證者 (verifier)，他們有一個主張，他們將使用互動來來回回，以及隨機性，這樣最終，如果證明是正確的，如果定理是正確的，驗證者將接受。如果定理是不正確的，驗證者將拒絕，具有極高的機率。存在很小的機會，有人說服你相信一個不正確的定理，而那些高中時寫的幾何證明，從來沒有這樣的機會。至少我們是這麼認為的。但無論如何，形式上來說，我們一開始就允許這種機會。而且，它是零知識的。

我關於這一點的重點是，零知識證明對密碼學等產生了非常大的影響，但我想更多地將其視為一種「催化劑」(catalyst)。催化什麼？這確實是我們第一次將「正確性」(correctness)（定理的正確性）與「知識」(knowledge)（證明的知識）分開。我們將必須看到證明才能驗證其正確性這件事分開了。一旦我們完成了這個分離，並且它不再是必要的，我們現在願意了，我們不會稱之為「證明」，我們會稱之為「互動證明」，但我們願意接受這類機制，也許你不必看證明就能驗證正確性，我們可以開始提出關於「證明是什麼」的新問題。例如，我們可以討論，這是否是唯一的證明系統？這種證明能否證明比你在書中寫出來的更強的定理或更難的定理？這種方式證明是否能更有效率？你可以問很多很多問題。事實上，這些正是過去 25 年（加上，我想是 35 年了，我不知道我第一次發表演講是什麼時候，25 年？86 年？算術真差）被問和被回答的問題。

我們可以問什麼樣的問題？一個問題，正如 Silvio 所說，我們可以問「什麼是可以互動證明的」(what's interactively provable)。你知道，經典證明可以處理 NP，我們可以處理 co-NP 嗎？也就是說，我們可以證明那個方程沒有解嗎？我們可以計算方程有多少個解嗎？等等。Fortnow、Carl of Lund 和 Nissan 以及 Shamir 的驚人結果表明，你可以通過互動和隨機性證明更多東西。事實上，你不僅可以證明方程存在解，還可以證明有零個解、有多少個解，事實上，任何你可以在多項式空間中進行的計算，你都可以說服一個只有多項式時間能力的人相信它。太棒了，令人驚嘆，而且使用了所有這些精妙的技術。

但我們還不滿足。我們問，你知道嗎？太有趣了。那麼還有另一種方式來定義機率證明，定義證明呢？也許互動和隨機性並不是唯一的東西。我們還能做什麼？我們該如何定義它？所以接下來的一步就是我稱之為「第二個證明者的到來」(the arrival of the second prover)，這有點像基督教的說法，我明白。但無論如何，我對此也不是很了解。這是與 Ben-Or、Kilian 和 Avi 合作完成的，我們說了以下的話。你知道嗎？為什麼不加一個證明者呢？首先，這似乎是一個輕率的想法，因為第一個證明者，我們說過我們不介意，她想花多少時間都可以。為什麼另一個證明者會有用呢？因為我們要做的就是把這兩個證明者分開。所以驗證者會向一個證明者提問並互動，向第二個證明者提問並互動，但他們不會看到他提的問題... 第一個人，第一個女孩，不會看到驗證者問另一個證明者什麼。我對誰是誰有點性別模糊，但無論如何，他們是證明者。

你為什麼認為這會很有力？因為想法是，通過向他們提問，然後根據你收到的答案，可能向另一個人提問，如果他們沒有知道證明，你可能會發現他們的不一致之處。所以我們想說的是，如果存在證明，他們對於定理總是會保持一致。如果定理沒有證明，我們將能夠發現他們的不一致之處。這就是我們想讓其為真的。同樣，我們喜歡講述的這個故事通常是，這就像兩個罪犯準備了不在場證明，但如果他們真的犯了罪，他們的不在場證明就不會完全嚴密。通過向他們提出他們無法預測的正確的刁鑽問題，我們將能夠抓住他們，證明他們的不在場證明是假的，或者證明證明的正確性是假的。事實上，回到密碼學作為催化劑這一點上，當我們詢問第二個證明者時，我們真的不知道這個第二個證明者會如此有用。我們覺得它有用是為了獲得更多密碼學。哪種更多密碼學？Silvio 暗示 GMW 具有 NP 和零知識。這實際上是在單向函數的假設下。我們想說的是，讓我們有一個無條件的結果。事實上，有了這兩個證明者，你可以以某種方式和其中一個交談，和另一個交談，互相檢查，並且他們可以在無條件零知識的情況下說服你關於定理的正確性。

然而，我們完全沒有準備好，這個第二個證明者似乎是一個改變遊戲規則的因素，正如 Babai, Fortnow, 和 Lund 在 FKLN 結果之後不久所展示的。他們展示了，實際上，這兩個證明者，他們事實上可以讓驗證者相信比 P-SPACE 更難的陳述。他們可以證明非決定性指數時間語言。所以他們可以證明這類問題。現在這確實是與 NP 相比的指數級差距。所以經典上，在教科書中，你可以做到 NP。有了這兩個被鎖在不同房間裡的證明者，你可以做到非決定性指數時間。這甚至使用了更多想法。這裡有一個非常重要的概念，來自 Blum, Rubinfeld, 和 Luby 在檢查方面的工作——「線性測試」(linearity testing)。

所以我們在這裡。我們有了這兩個證明者。而且他們非常強大。所以我們非常興奮。然而，你意識到我們有點脫離現實了。所以我們正在談論 #P, P-SPACE, 非決定性指數時間。我們說，你知道，外面有這樣一個證明者。他可以做所有這些陳述，說服...可憐的驗證者只需要多項式時間的能力。然而，這種想法是錯誤的。因為真正應該出現在你腦海中的是，好的，如果我們通過擁有這兩個證明者可以實現這樣的飛躍，那麼經典問題呢？所以也許這意味著我們可以將這個結果「縮小規模」(scale down)，甚至以不同的方式證明經典問題，也許以快得多的方式。既然驗證者可以用多項式時間驗證如此困難的陳述，也許他可以用更少的資源驗證更簡單的陳述。所以這事實上是下一個問題。事實上，這是真的。所以，你知道，最初的兩篇論文，這是 Fortnow, Levin, 和 Segedy 的工作。然後這是與 Feige, Lovasz, Safra, 和 Segedy 的合作。我們只是希望縮小規模，好的，也許證明可以更短，多項式對數大小 (polylogarithmic in size)。但結果證明，你事實上可以用只需要讀取常數個位元的證明來驗證 NP 陳述。所以這令人難以置信，但這是真的。正如人們所知，這引發了許多關於近似問題難度的深刻見解，本質上是通過觀察通訊圖，但我不打算深入探討。我確實想給你一個想法，為什麼。

雲端運算的挑戰與密碼學的希望

輸出並接收輸出。因此，這具有巨大的潛力，人們一直在談論這種知識的全球化，而我們在節省本地儲存和計算方面的能力確實令人印象深刻，更不用說我們如何聚合所有這些資訊了。這可以幫助我們進行醫學研究、能源使用、交通改道等。你知道，很難總結通過了解如此多資訊所能實現的所有美好事物。然而，這種知識的全球化也存在巨大的風險。一些風險是我們失去控制。所以以前計算是在家裡完成的，現在是在其他地方進行。我怎麼知道計算是否正確完成？我們失去了隱私。我們失去了獨處的權利。我們失去了公平。他們對我了解這麼多。現在他們可能會對我進行分析。他們可能會向我收取更高的費用。他們可能不接受我進入研究生院等等。所以問題是，我們作為一個社會能否基本上向前發展？我的意思是，我們是否還能做到所有那些可以完成的美好事情，而不同時放棄我們希望擁有的所有這些個人控制？

我認為密碼學的魔力為我們提供了一種希望。就像我展示的，驗證不代表你必須看到證明。類似地，計算也不一定意味著你必須看到數據。事實上，自 80 年代以來，特別是過去五、六年，已經開發出了一系列技術，其中一些非常精彩，我將在我剩餘的時間裡討論，它們正是做到這一點的。它們討論瞭如何在不實際看到數據的情況下在數據上進行計算。因此，如果我們思考所有這些進步，它本質上是在你不想放棄的數據上進行計算，這是成功的關鍵。

讓我非常快速地瀏覽一下人們目前在雲端運算中使用密碼學工作的問題，正是以這種我充滿希望的方式。首先是關於「正確性」(correctness) 的問題。這很明顯。我只是將我的數據發送到雲端，雲端正在計算並將結果返回給我。但是我為什麼要信任雲端？誰說它返回的結果是應該返回的？這很棒，因為我們已經討論證明快兩個小時了，相信但要驗證，對吧？與其信任雲端，我們寧願告訴雲端，聽著，為什麼你不計算然後證明結果？當然，不是任何證明都可以。如果雲端告訴我他們所有的想法，他們早上怎麼起床，怎麼處理了所有東西，我將不得不花費和雲端計算一樣多的時間。重點是，我比它弱得多。所以我想要那種驗證起來非常有效率的證明。而這正是我們一直在談論的。所以我們為什麼不使用互動證明呢？證明會是什麼？互動證明，雲端會說，嘿，我實際上為這個 F 運行了一個程式，這就是結果，我在我聲稱的步驟中完成了這個。拿去吧。事實上，我們說過，例如 IP 等於 PSPACE。所以這看起來我們已經完成了，因為這是一個非常複雜的計算，而你可以在多項式時間內驗證它。問題在於，這些最初的結果真正關心的是複雜性理論。他們不關心特定的計算。他們通過完全問題來實現。所以如果你看這些結果，雲端為了完成證明所要做的工作將會超過多項式時間。所以你真正想要的，或者說現代的挑戰是，你要確保雲端在給你證明時，它不需要付出太多額外的努力來得到那個證明。所以我們既希望驗證者超級有效率，也希望雲端不要損失太多時間。所以這是一個極其活躍的研究領域。這裡只是一堆結果。它們似乎改變了每一個模型。然後我們討論證明者必須花多少時間，以及驗證者必須花多少時間。結果會根據你是想要一個對計算能力沒有任何假設的互動證明，還是像 Silvio 談到的那種計算可靠證明 (computationally sound proof) 而改變。而且這裡有令人難以置信的進展。這次會議上有一篇論文。我不知道為什麼我說 13 年。也許是因為它在 13 年已知但在 14 年才發表。所以這將是明天 Kalaros 和 Brothlum 的論文，他們展示了如何實際上將任何時間 T 的計算，在證明者必須做的工作之上，僅僅用幾乎線性的時間開銷來完成。現在，這些結果的好處是，它們再次具有這種催化性。儘管人們的目標是一個與委託計算有關的問題，一個受密碼學啟發的問題，但在這個過程中，卻展示了一些複雜性理論的結果。其次，實際上，這些不再只是象牙塔式的研究，而是人們正在努力將理論轉化為實踐。所以他們將許多這些技術應用於實際程式。他們正在編寫編譯器，設計硬體來實際獲取真實程式並快速附加證明。你為什麼在笑？沒事，好吧。這裡也有一些應用於大數據。

第二個挑戰是什麼？第二個挑戰，正如我所說，好的，所以雲端可以證明他們按照要求進行了計算。但我的「隱私」(privacy) 呢？我真的想把我的所有數據都交給雲端嗎？你會說，當然不想。這是我的所有個人信息。我擔心隱私問題。所以我要將我放在雲端的所有數據加密。但是一旦我加密了，雲端如何在上面進行計算？因為現在它是加密的。所以問題當然是，你如何既加密它，獲得隱私，又獲得實用性？這實際上是一個很棒的問題，過去幾年在這個問題上取得了令人驚嘆的突破性進展，關於如何在加密數據上進行計算。如何提出新的加密形式。我們不只是隱藏資訊，而是你可以在它們上面進行計算。所以有一些巧妙的方法，除了隱私之外，還允許計算。最著名的是 Gentry 在 2009 年提出的「全同態加密」(fully homomorphic encryption)，他展示了一種加密方案，事實上，你可以在加密領域評估任意函數。所以有加密的資訊。它返回的結果是該資訊上的加密計算。現在，當這項技術剛開始時，它非常慢。它使用了我們不熟悉的假設。這個領域取得了令人難以置信的快速進展。目前，據我所知，最好的假設與基於格的非同態密碼學方案的最佳假設一樣好。所以我們已經設法將所需的假設降低到實際密碼學所需的假設，而無需同態屬性。而且在這裡，也投入了大量的資金來將理論轉化為實踐。

第三個挑戰。好的，現在，太棒了，我們可以將數據加密在雲端。我們可以得到證明，證明一切都是正確的。我們可以將雲端用作計算引擎。但還有什麼呢？我們還想要什麼？好吧，你知道，實際上，我們並不一定總是想帶著加密的數據返回給客戶端，然後說，嘿，這是你的數據，你可以解密它。我們想讓它做得更多。我們想在雲端聚合資訊並能夠在上面進行計算。這實際上是第三個挑戰，也就是，我們能否在雲端只對數據進行加密，並允許伺服器從這些加密數據中提取部分資訊，僅此而已？所以我們希望伺服器知道一些事情。並不是我們不希望它知道任何事情，比如為了醫學研究、交通資訊等。我們能做到嗎？答案是可以的。但在我給你們肯定答案之前，我想給你們看兩個在我看來很棒的應用。

這裡有一個應用：假設你有一家醫院，有很多病歷，它們都被加密了，醫院不允許將這些病歷透露給製藥公司（比如說），因為病人沒有授權。但製藥公司想運行一個檢查基因存在的演算法。他們並不在乎查看醫療數據。這可以做到嗎？所以這裡你想要的是能夠獲取這些數據，僅檢查是否存在某個基因，除此之外什麼都不做。好的，你怎麼做呢？你可以索要金鑰。但如果我給你金鑰，那你就知道一切了。所以我們希望在不了解一切的情況下做到這一點，只知道某個基因是否存在。