公鑰密碼學的複雜性

原文：https://eprint.iacr.org/2017/365.pdf

作者：Boaz Barak

譯者：Kurt Pan

2017年4月27日

我們回顧了公開密鑰密碼學的計算基礎，並探討了作為公開密鑰加密方案基礎所採用的計算假設，以及我們對這些假設真實性所擁有的各種證據。

引言

讓我們回到1977年。第一部（或者根據你所計算的順序是第四部）《星際大戰》電影上映，ABBA錄製了《Dancing Queen》，而在八月，Martin Gardner在《科學美國人》專欄中描述了RSA密碼系統，其安全性依賴於整數分解的難度。這是在Diffie、Hellman和Merkle於1976年發明公開密鑰密碼學及基於離散對數的Diffie-Hellman密鑰交換協定之後不久的事。

現在來設想一個不同的歷史情境。假設在那年十二月，一位名叫Dieter Chor的數學家發現了一種能夠高效計算離散對數及分解整數的演算法。可以想像，在這種情況下，科學界會達成共識，認為公開密鑰密碼學這一概念本質上是不可能的，反正它聽起來就“好得令人難以置信”。在接下來的數年中，人們偶爾會提出各種公開密鑰加密的其他建構方式，但由於過去的教訓，科學與技術界將對採用這些方式保持謹慎，並認為這些建構在證明其安全性之前是不可靠的。

這個假想歷史當然與我們的現實大相逕庭，現今公開密鑰密碼學是一個廣受研究與實際應用的概念。但基礎的科學事實是否真的有所不同呢？目前我們並無強有力的證據證明整數分解與離散對數問題實際上是困難的。事實上，Peter Shor提出了一種能夠在所謂的「量子電腦」上以多項式時間運行的演算法來解決這些問題。儘管一些研究者（包括Oded Goldreich等）對實際物理上實現這一模型表示深刻懷疑，但美國國家安全局已對此可能性表達了足夠的關切，並警告政府與產業界應在不久的將來逐步放棄這些密碼系統。無論如何，考慮到這些問題強大且尚未完全理解的數學結構以及存在極為非平凡的次指數演算法，我們沒有充分理由假設不存在一種經典（即非量子）演算法來解決這些問題。

在本教程中，我想探討在離散對數與整數分解問題上取得突破的這一假設性（或許並非那麼假設性）的情境對密碼學理論所產生的影響，並以此作為進一步探討本領域中困難假設角色的起點。我將討論的不僅僅是數學方面，還有這一問題的社會與哲學層面。這類考慮在任何科學領域中都扮演著重要角色，但在我們需要決定應該信賴哪些未被證明的假設時，尤其如此。這並非一篇標準的教程或報告，因為它更多關注於問題而非答案，而我對這些問題的許多看法也相當主觀。不過，我確實認為，對於有意於研究密碼學基礎的人士，無論是學生還是其他人，思考這類問題並形成自己對如何正確處理這些問題的見解都是十分合適的。

致謝。 本報告是為了慶祝Oded Goldreich 60歲生日而撰寫。我第一次接觸到密碼學基礎之美即是通過Oded，儘管我們在某些具體問題上可能並不總是一致，但他的教導、著作以及我們之間的討論對我在此議題上的看法產生了深遠影響。Oded撰寫了許多值得一讀的文章，探討了與本報告相關的議題，例如科學中的主觀性與品味、密碼學中的計算假設，以及純科學與應用科學（或「理論」與「工具性」）之間的區分。我也要感謝Benny Applebaum、Nir Bitansky以及Shai Halevi對本報告早期版本所提出的極具洞見的意見，這些意見大大改善了報告的呈現。

公開密鑰密碼學的獨特之處

也許在本文中，第一個未經充分證明的主觀判斷便是我特別懷疑整數分解與離散對數問題，以及其他「公開密鑰型」假設。畢竟，既然我們尚未能證明 ，實際上所有密碼學基本構件都建立在未被證明的假設之上，無論是分解的難度、離散對數的難度，還是破解 AES 密碼的難度。正因如此，許多密碼學理論研究並不直接針對某個具體的困難問題，而是構建起一個將不同基本構件相互歸約的網絡。基於歸約的安全性取得了顯著成功，正是因為它能夠將眾多密碼學構造的安全性歸約到少數幾個簡單明了且廣受研究的假設之上。這一發展使密碼學從一種依賴於「安全性靠隱蔽」的煉金術式活動轉變為一門在明確陳述的假設下獲得明確安全屬性的科學，並且常被認為是安全應用中最堅實的基石。

鑑於上述情況，理論密碼學家的典型工作可以被視為從一個較舊（通常較簡單或較易構造）的基本構件出發，構造出一個新的（通常更精妙或滿足更嚴格安全性要求）的密碼學原語。這些原語的最底層可能有多個基於各種困難假設的候選構造，而密碼分析算法的任何新進展，都意味著我們少了一個候選。

上述直覺在對稱密碼學中大致成立。在過去三十年間，密碼學家們構築了一個強大的歸約網絡，展示了從單向函數這一原語中構造出眾多物件的可能性。事實上，我們確實有許多單向函數的候選構造，不僅包括基於整數分解與離散對數的構造，還有基於簡單組合問題（例如植入最大團、隨機 SAT、Goldreich 基於擴張圖的候選構造）以及許多在實際中廣泛使用、經過大量密碼分析卻未發現重大攻擊的候選區塊密碼、串流密碼和雜湊函數。

然而，對於公鑰密碼學，情況則截然不同。實際上，公開密鑰系統主要分為兩大流派。第一類包括基於整數分解與離散對數問題的「代數」或「群論」構造，如 Diffie-Hellman（及其橢圓曲線變種）、RSA、Rabin、Goldwasser-Micali等方案；第二類則包括由 McEliece 首次提出的「幾何」或「編碼／格」系統（以及曾被破解的 Merkle-Hellman 背包方案）。這些系統因 Ajtai 的格論文而煥發新生，隨後又由 Ajtai-Dwork、Goldreich-Goldwasser-Halevi 以及 Hoffstein 等人的工作，提出了基於格的公鑰系統；後來，Regev 又提出了*帶錯誤學習假設(LWE)*，並展示了該假設與某些與格相關的困難假設之間的等價性。

現有的經典與量子演算法對基於代數／群論流派的方案安全性提出了質疑。畢竟，作為理論學家，我們關心的是那些不僅缺乏已知有效攻擊，而且確實不存在有效攻擊的方案。然而，目前幾乎沒有證據顯示這第一類方案能滿足這一要求。這便使我們只剩下基於格／編碼的系統。幸運的是，鑒於近期的進展，幾乎沒有哪一個群論流派的原語不能基於格構造；事實上，許多令人振奮的新原語，如全同態加密和不可區分混淆技術，也僅有基於格／編碼假設的已知構造。

如果因為這些經典與量子演算法，我們不願信任這些「代數」／「群論」密碼系統的安全性，那麼我們就會處於一個相當不舒服的境地：所有公開密鑰密碼學的結構僅建立在一個相當充分研究的基礎上，即格／編碼問題的難度。而且，人們不禁會懷疑，若在最底層每個基本構件本質上僅有單一實現，談論一個「抽象網絡」是否有些誤導。這使得弄清楚公開密鑰密碼學是否能夠建立在截然不同的假設之上顯得尤為重要。更廣泛地說，我們希望探討密碼學中的「假設景觀」，既包括具體假設，也涵蓋不同對象之間的相互關係。自現代密碼學誕生以來，這類問題一直吸引著眾多研究者，我們將在本教程中回顧一些已取得的發現以及仍存在的諸多未解之謎。

備註：我們提出這一問題的一種說法，是要了解公開密鑰密碼學所需的結構類型。單向函數可以被視為一種完全無結構的對象，既可以由任何平均難度的搜索或“植入”問題實現，也可以直接由具備偽隨機特性的函數推出。相較之下，至少目前，我們尚不知如何在不假設結構性問題困難性的前提下獲得公開密鑰加密，且我們也不知道如何將公開密鑰加密建立在對稱加密方案的基礎之上。這種固有性的程度正是本調查的主題；此外，我在另一篇調查中也有更多關於計算困難性中結構所扮演角色的討論。

組織架構

在本教程的剩餘部分，我們將探討對稱密碼學和公開密鑰密碼學的假設景觀。重點不在於最有效的方案，也不在於那些提供最複雜安全性屬性的方案，而僅僅是嘗試涵蓋一些基於各種計算困難假設的候選構造。此外，我們並不打算對這些方案進行完整的數學描述——在這些主題上已有許多優秀的調查報告和教材——而是側重於它們的質性特徵。

這裡所做的許多判斷，例如評估兩個未被證明等價的困難假設是否「相似」，本質上帶有主觀性。第六節或許是本調查中最具主觀性的一部分，我們在該節中試圖探討一個計算問題之所以困難的內在因素。

對稱密碼學

在討論公開密鑰密碼學之前，讓我們先來探討對稱密碼學，其在理論與實踐上呈現出更為清晰的假設景觀。對稱密碼學的基本理論對象是單向函數：

定義 1（單向函數）。如果存在一個多項式時間算法能將  映射至 ，並且對於任一概率多項式時間算法 、常數  以及足夠大的 ，則函數  為單向函數，滿足

我們用 OWF 來表示單向函數存在的猜想。

雖然單向函數的定義先驗上並未涉及任何秘密鑰匙，但大量研究證明（主要通過 Goldreich-Levin 定理所建立的偽隨機性聯繫），OWF 等價於多種密碼學原語的存在，包括：

• 偽隨機產生器

• 偽隨機函數與訊息認證碼

• 數位簽章

• 承諾方案

• 對 NP 中所有語言的零知識證明

因此，OWF 可被視為對稱密碼學的核心猜想。但這一猜想的正確性究竟有什麼證據呢？

候選單向函數構造

「自古以來，人類總是不斷地且往往殘酷地被提醒：許多事情做起來比其逆轉容易得多」——Leonid Levin

支持 OWF 猜想的主要證據在於我們擁有大量潛在安全的候選單向函數構造。的確，看似「甩一塊石頭都能打到一個單向函數」的意思是，一旦你將大量簡單的計算操作組合起來，除非這些操作滿足某些特殊屬性（例如線性性），否則你通常會得到一個難以逆轉的函數（實際上，有人已提出一些對這一直覺的形式化描述）。以下是一些候選單向函數構造的範例：

區塊密碼、串流密碼與雜湊函數

許多實際應用中的對稱密碼學原語，如區塊密碼、串流密碼和雜湊函數，相信分別滿足偽隨機置換、偽隨機生成器與抗碰撞雜湊函數的安全定義。所有這些概念均蘊含了單向函數的存在，因此這些原語均可作為候選的單向函數。這些構造（包括 DES、AES、SHA-x 等）通常以固定的有限輸入與密鑰大小來描述，但它們往往可以自然推廣。請注意，業界通常要求這些原語具有極高的安全性，任何比平凡的 （其中  為密鑰大小、區塊大小等）更快的攻擊都會被視為安全上的弱點。實際上，對於許多被認為較弱或「已破解」的構造，已知攻擊仍需指數級時間（雖然指數遠小於 ）。

平均情況組合問題：植入 SAT、植入最大團、帶噪聲奇偶學習（LPN）

一個 NP 問題的植入分布可以定義如下：

定義 2 (NP 關係與植入問題)。 一個關係  是 NP 關係，當且僅當存在一個多項式  使得對於每個 ，都有 ，且存在一個多項式時間演算法 ，在輸入  時當且僅當  輸出 1。一個概率多項式時間演算法  是  的採樣器，若對於每個 ， 都以概率 1 輸出一對滿足  的 。我們稱演算法  能解決對應於  的植入問題，若對於每個 ，以至少  的概率，當從  中取樣  時，有 。我們稱對應於  的植入問題是困難的，若不存在任何概率多項式時間演算法能解決它。

以下這個簡單引理表明困難的植入問題蘊含了 OWF 猜想：

引理 2.1。假設存在一個困難的植入問題 ，則存在一個單向函數。

證明： 接下來我們將證明一個困難的植入問題蘊含了一個弱單向函數，這裡我們定義弱單向函數為一個函數 ，使得對於每個概率多項式時間演算法  與足夠大的 ，

也就是說，我們僅要求敵手以超過 90% 的概率無法逆轉該函數，而非定義 1 所要求的不可忽略的概率。已知弱單向函數的存在蘊含了強單向函數的存在。令  為一個困難植入問題的生成器， 為其對應的關係。通過填充，我們可以在不失一般性的前提下假設，對於輸入 ， 所使用的硬幣數量為 ，其中  為某個整數且 。對於每個 ，我們定義 ，其中 ，且 ，而  表示  在輸入  及硬幣  下的輸出。

現在我們證明  為一個弱單向函數。實際上，假設存在一個概率多項式時間演算法  與某個足夠大的 ，使得弱單向函數定義被違反，並令 。這意味著

這特別意味著，如果我們令 ，則以至少  的概率， 將輸出一對 ，其中  且 （因為對於  的輸出，此條件以概率 1 發生）。因此，我們得到一個多項式時間演算法，可在長度為  的輸入上以至少  的概率解決該植入問題。

利用這一聯繫，有幾個自然的植入問題產生了候選單向函數。

植入最大團問題：眾所皆知，在一個隨機的 Erdős-Rényi 圖  中（其中每對頂點以概率  連邊），最大的團大小將為 。然而，貪婪算法僅能找到大小為  的團，而 Karp 在 1976 年提出問題：是否存在一個高效算法能找到大小為  的團。至今該問題仍未解決。在 1990 年代，Jerrum 與 Kucera 考慮了一個較簡單的變種，即是否可以在一個隨機圖中找到一個植入的團，其大小為 ，方法是隨機選取一個大小為  的集合並連接其中所有頂點。 越大，問題越容易，而目前尚未發現對於任何  的情況存在多項式時間算法。根據上述討論，若此問題對任何  都是困難的，則存在一個單向函數。Juels 與 Peinado 表明，對於 ，植入分布在統計接近與均勻分布。因此，只要 Karp 問題的答案是否定的，就存在一個困難的植入分布（從而存在一個單向函數）。

植入約束滿足問題：一個（二元）約束滿足問題是由一組函數  組成，這些函數將  映射至 ，且每個函數  僅依賴於輸入位中的常數個數。給定一個賦值 ， 的值定義為 。 的值即是所有賦值  中所能達到的最大值。

對於隨機約束滿足問題存在若干模型。一個簡單的模型如下：對於每個謂詞  以及數字 ，我們可以通過隨機且獨立地選取每個  使其等於  來選取 ，其中  為隨機且獨立的文字（即對於某個隨機選取的 ，等於  或 ）。利用標準的測度集中結果，可以證明以下命題：

引理 2.2。對於謂詞  以及每個 ，存在一個常數 （取決於  與 ），使得若  且  是從上述模型中隨機選取的，則以至少  的概率， 的值落在  之中，其中 。

存在幾個植入模型，其中給定 ，我們隨機抽樣一個實例  使得相對於 ， 的值明顯大於 。下面是一個模型：

定義 3。令  如上，令 ，且令  為  上的某個分布。生成約束滿足問題的  植入模型，透過對  重複以下步驟獲得：以概率 ，按照上述方式隨機抽樣一個約束 ；否則，從  中抽取一個字串 ，並根據條件（使得這些文字應用於  後得到 ）隨機抽取  作為文字，並令  為約束 。

類似於引理 2.2，如果  是從  模型中抽樣的，則以高概率相對於  的值至少為 ，其中 。若 ，則我們可以將植入問題定義為尋找一個賦值，其值至少為 。有研究者猜測，只要  為成對獨立分布，此植入問題便是困難的。這一猜想立即引出許多基於謂詞（如 -XOR、-SAT 等）的候選單向函數。

Friedgut 已證明，每個隨機約束滿足問題皆滿足一個閾值條件，即對於每個 ，當  增大時，存在一個值  使得隨機選取的  個約束組成的實例其值為 1 的概率接近於 1，而隨機選取的  個約束組成的實例其值為 1 的概率接近於 0。人們普遍認為， 的值為某個與問題相關的常數 （對於許多謂詞而言，人們已提出具體的猜測），但這尚未在完全一般情況下得到證明，尤其是  的情況仍然懸而未決。同時，人們亦認為，對於足夠大的 （可能甚至  就足夠），在隨機 -SAT 約束滿足問題中，當  非常接近（但低於）閾值時，尋找一個滿足（即值為 1）的賦值是困難的。利用類似於其他研究的推理（但使用了更為複雜的技術），Achlioptas 與 Coja-Oghlan 證明該猜想暗示了某一植入變種的困難性，從而又產生了另一個候選單向函數。

無監督學習與分佈式單向函數

無監督學習的應用提供了另一個候選單向函數。在這裡，我們可以將模型  描述為一個概率演算法，其在給定某些參數  後，從某個分佈  中抽樣。機器學習中研究的模型通常在正向計算上是高效的。挑戰在於，在給定來自  的  個獨立樣本  的情況下，解決恢復 （或其近似值）的推理問題。

考慮足夠大的  使得參數是統計可識別的。為簡單起見，我們定義此條件為：對於每個 ，在從  中選取  時，以高概率滿足

對於每個  均成立，其中對於每組參數  及 ，

現在，假設存在一個演算法 ，在給定  的情況下，能夠從均勻參數  以及隨機硬幣  所構成的分佈中，根據條件 （對所有 ）進行均勻抽樣。則若  中的元素本身是從  中抽樣得到，則以概率 ， 的第一個輸出  將等於 。因此，如果存在一個樣本數 ，使得對於  的無監督學習問題在統計上是可識別但在計算上卻困難，則過程在這種分佈意義下是難以逆轉的。但 Impagliazzo 與 Luby 證明，不僅弱單向函數的存在，連分佈式單向函數的存在也蘊含標準單向函數的存在，因此任何計算上困難的無監督學習問題都能產生這樣的候選。

帶噪聲奇偶學習 (LPN) 問題是被猜測為困難的無監督學習問題之一，並曾被提出作為密碼學的基礎。此處，模型的參數是一個字串 ，而一個樣本由一個隨機  以及一個位元

組成，其中  以概率  選取為 0，以概率  選取為 1（ 為某個常數）。利用測度集中結果可以證明，只要樣本數  至少為某個常數乘以 ，該模型在統計上是可識別的，但目前已知最好的「高效」演算法需要  的樣本數和運行時間（另有改進版本以犧牲部分誤差和運行時間換取較少的樣本數）。因此，若這個演算法無法改進以在最優樣本數和多項式時間內運行，則單向函數便存在。

Goldreich 的單向函數候選

Goldreich 提出了一個非常優雅且具體的單向函數候選，已引起多位研究者的關注。定義一個  圖為一個二分圖，其左側有  個頂點、右側有  個頂點，且每個右側頂點的度數為 。Goldreich 的函數  由一個  圖  與一個謂詞  所參數化。對於每個  以及每個 ，Goldreich 函數的第  個輸出位定義為其中 中頂點  的左鄰集合記為 ，而  表示  在坐標集  上的限制。

Goldreich 猜想，只要謂詞  足夠「無結構」，且圖  具有足夠良好的擴展性，則該函數便為單向函數。隨後的一些工作通過展示某些自然演算法族並未反駁這一猜想而提供了支持證據；其他工作則指出需要在選擇謂詞  時加以注意，確保其平衡性，並避免存在可能使問題變得更容易的其他特性。後來的研究還暗示 Goldreich 的函數甚至可能是一個偽隨機生成器。更多關於 Goldreich 函數及其變體的已知構造、攻擊方法，以及數個令人驚訝的應用，可參見相關調查報告。

隨機電路

或許將足夠多的操作拼湊在一起便得到單向函數這一直覺，最直接的形式化來自 Gowers 的一個猜想（另見相關文獻）。他猜想，對於每個 ，存在某個多項式 ，使得如果我們選取一個序列

其中每個  為作用於  上的隨機局部置換，則函數

將會是一個偽隨機函數。我們稱  為局部置換，若它是通過對輸入的三個位元應用一個在  上的置換得到。也就是說，存在  以及一個置換 ，使得對於所有  有 ，而

這個序列  的選擇構成了偽隨機函數的種子。由於偽隨機函數蘊含單向函數，這又提供了另一個候選。

基於公開密鑰假設的對稱密碼學

雖然這是一個顯而易見的事實，但值得一提的是，所有蘊含公開密鑰密碼學的假設同時也暗示了對稱密碼學。因此，我們可以基於整數分解、離散對數、帶噪聲奇偶學習，以及其他所有曾被提出作為公開密鑰加密與數位簽章基礎的假設來構造單向函數。

公開密鑰密碼學：概述

我們已經見識到候選的對稱密碼加密方案種類繁多。從文獻的粗略搜尋來看，似乎公開密鑰系統也極多。然而，目前研究較深入的候選方案僅分為兩大類：一類是基於某些具體阿貝爾群上代數問題的困難性，另一類則是基於線性碼或整數格上幾何問題的困難性；見圖 1。

圖 1：公開密鑰密碼系統的兩個「主流」家族

這兩大家族是否包含了所有現有安全的公開密碼方案？或者，也許（若你認為大規模量子計算將成為現實，或者基於群的家族中現有的經典演算法可獲得顯著改進）安全的公開密鑰密碼學唯一來源就是格／編碼？簡短的回答是我們根本不知道，但在本文中我想探討更詳細的答案。

我們將討論文獻中提出的一些替代性的公開密鑰系統，探究它們安全性的證據，以及它們在多大程度上與前兩大家族真正不同。我們還會探討，提出候選方案並試圖破解這些方案這種做法是否是我們所能做到的最佳方法，或是否存在一種更有原則的方式來論證密碼方案的安全性。

如前所述，我們的討論本質上是主觀的。我不知道有何客觀方法能斷言兩個密碼方案屬於「同一家族」或是「彼此不同」。一些讀者可能會質疑公開密鑰密碼學基礎存在任何危機或潛在危機的說法，甚至有人可能認為對於對稱與公開密鑰密碼學安全性的證據之間並無真正差異。儘管如此，我仍希望即使是這些讀者，也能從本文中獲得一些值得深思的啟發。

備註：有人可能會問，公開密鑰與對稱密碼學之間是否真的存在本質上的差異，還是這僅僅反映了我們的無知。也就是說，是否可能僅根據任意的單向函數構造出一個公開密鑰密碼系統，從而建立在與對稱密碼加密相同的假設之上？答案是我們不知道，但在一項開創性工作中，Impagliazzo 與 Rudich 證明，透過標準的黑盒安全歸約形式無法實現這一點。具體而言，他們證明，即便給定一個隨機 Oracle（這是一個理想化的單向函數），也無法構造出一個具備黑盒證明的密鑰交換協議，使其能夠對所有以多項式時間（甚至  時間，其中  為誠實方所花費的時間）運行的對手保持安全。Barak 與 Mahmoody 將此改善為  時間，從而與下文中討論的 Merkle 1974 年協議相匹配。

兩大「主流」公開密鑰構造

現在討論兩大公開密鑰構造家族——這些家族源自於 1970 年代末期由 Diffie 與 Hellman、Rivest、Shamir 與 Adleman、Rabin、Merkle 與 Hellman，以及 McEliece 提出的最早系統。

「代數」家族：基於阿貝爾群的構造

一些最早的公開密鑰加密方案基於離散對數與整數分解問題，而這些方案至今仍是部署最廣、研究最深入 的構造。這些方案由 Diffie 與 Hellman、Rivest、Shamir 與 Adleman 以及 Rabin 等人提出，事後我們得知這些方案其實在情報界由 Ellis、Cocks 與 Williamson 幾年前已經發現。後來，Miller 與 Koblitz 又分別提出了基於橢圓曲線群中離散對數問題的類似方案。

這些方案具有豐富的代數結構，這不僅對它們在公開密鑰應用中的使用至關重要，也促成了一些非平凡的演算法結果。這些成果包括：

• 整數分解與離散對數問題均屬於 TFNP 類，即 NP 搜索問題中每個輸入皆保證有解。除非 NP = coNP，否則此類問題無法通過 Cook 歸約證明為 NP-hard；此外，還有其他關於這些問題複雜度包含關係的結果。

• 整數分解問題以及在  上的離散對數問題存在次指數演算法，其運行時間大致為 ，其中  為位元複雜度。

• 最近，在小特徵有限域上的離散對數問題已被證明存在準多項式時間演算法。

• 對於橢圓曲線，目前尚無通用的次指數離散對數演算法，但對於某些具有大虧格的曲線家族，已知存在次指數演算法。

• Shor 演算法為整數分解與離散對數問題提供了多項式時間的量子演算法。

「幾何」家族：基於格／編碼／背包的密碼系統

第二種公開密鑰加密候選方案也有相當悠久的歷史。1978 年，Merkle 與 Hellman 提出了他們的背包方案（該方案及其幾個變種後來被格歸約技術破解）。同年，McEliece 提出了一種基於 Goppa 碼的方案。1996 年，Ajtai 在一項開創性工作中展示了如何利用整數格，在最壞情況假設下構造單向函數。受此工作啟發，Goldreich、Goldwasser 與 Halevi 以及 Ajtai 和 Dwork 分別提出了基於格的公開密鑰加密方案（後者也基於最壞情況假設）。大約在同一時期，Hoffstein、Pipher 與 Silverman 構造了 NTRU 公開密鑰系統，從後來看，該系統可以視為一種類似於前述格方案，但基於具有特殊結構的格。2003 年，Regev 提出了改進版的 Ajtai-Dwork 密碼系統；同年，Alekhnovich 提出了一種基於帶錯誤奇偶學習問題（雖然噪聲非常小）的 Ajtai-Dwork 系統變種，但這是以採用平均情況而非最壞情況的困難假設為代價。關於基於格的密碼學更全面的概述，可參見相關綜述。

備註 （離散性 ＋ 噪聲 ＝ 困難性？）：一種理解這些方案的方法是，它們依賴於高斯消元演算法在整數或有限域上的脆弱性。這與在實數上即使面對帶噪線性方程也能解決的穩健最小二乘最小化演算法形成對比。然而，在離散環境中（例如，當  受限於整數，或所有方程皆模某個  時），尚未有最小二乘最小化的類似方法被發現。這一問題及其變種被認為具有困難性，正是上述密碼系統安全性的基礎。

帶錯誤學習問題（LWE）：Regev 提出了上述直覺中最乾淨且最有用的形式化，他提出了以下假設：

定義 4。對於函數  以及 ，帶錯誤學習問題（LWE）的參數為 ，其任務是從  個形式為

的樣本  中恢復一個固定的隨機密鑰 ，其中  是在  中隨機選取的，而  則是從標準差為  的正態分佈中選取的。

圖 2：Regev 基於 LWE 問題的簡單公開密鑰密碼系統 。只要這些參數下 LWE 成立且 ，該方案便安全；只要噪聲參數  為 ，解密便能成功。

LWE 假設即是假設對於某些形式為  的 （其中  為一個足夠大的常數），此問題是困難的。Regev 與 Peikert 證明，該問題亦等價於其判定版本（在參數上略有損失），在該版本中需要區分形如  的樣本與其中  僅僅是  中的一個獨立隨機元素的樣本。利用這一歸約，可以很容易地證明 LWE 蘊含了公開密鑰密碼系統的存在，參見圖 2。

Regev 證明，若參數為  的 LWE 問題易解，則存在一個  因子（最壞情況）的近似量子演算法，用於解決格上 gap 最短向量問題。請注意，即使有人認為量子計算並非物理上可實現的模型，這樣的歸約仍然具有意義，且近期論文亦給出了經典的歸約 。

LWE 假設正迅速成為公開密鑰密碼學的核心，因為大量用於「純」公開密鑰加密的方案，以及具有更強特性的加密方案（如全同態、基於身份等）均依賴於這一假設，並且已有若干工作成功地將群論世界中的構造與直覺「移植」到基於 LWE 的原語中。

理想／環 LWE。基於格問題的理想或環變體對應於矩陣  具有某種結構，使得可用  個數而非  個來描述，並且通常能夠利用類似快速傅立葉變換的演算法進行更快運算。這樣的優化對於實際應用至關重要。更多關於這一假設及其用途，請參見手稿 [Pei16]。

近似 GCD。儘管在基於格的密碼學中，我們通常考慮高維格，但當涉及的數足夠大時，也可以考慮非常低維甚至一維的格。對於此類格，常用的計算問題是近似最大公因數 (GCD) 問題，其中給定的樣本是通過將一個秘密數  的整數倍加上一些微小噪聲得到的，目標是恢復 （或至少區分該分布與均勻分布）。近似 GCD 已被用於構造各種基於格方案的類似構造。

基於格方案的結構特性。對於這些方案，已知以下結構特性：

• 所有已知的基於格的公開密鑰加密方案均可利用對格最接近向量問題的  近似演算法的 oracle 訪問來破解。Goldreich 與 Goldwasser 證明，若 SZK 類（其為  的子集）屬於 （或 ），則存在這樣一個高效演算法。Aharonov 與 Regev 證明，若 ，此結果亦成立。請注意，儘管大多數專家認為  不屬於 ，但這一結果仍可視為展示這些基於格的方案具有一些計算結構，而這些結構在許多單向函數候選中並不共享。

• 與基於格的方案不同，我們尚不清楚若 ，Alekhnovich 的方案是否會變得不安全，儘管其使用了極低噪聲的帶錯誤奇偶學習的變體，這似乎類似於具有近似因子大於  的最接近向量問題。Ben-Sasson 等人最近的一個結果表明，使用如此少量的噪聲可能是此類一般型方案的固有限制。

• Shor 演算法核心的求階問題可視為更一般隱藏子群問題的一個實例。Regev 證明了對於二面體群，從格問題到該問題的歸約。Kuperberg 為該問題提供了一個次指數時間（即  時間）的量子演算法 ，但由於 Regev 的歸約具有二次膨脹，該演算法並未導致基於格問題的次指數量子演算法。

• 一系列近期結果顯示，對於具有短基（該基由單一向量的平移構成）的主理想格，這些問題在量子與經典上均顯著更容易求解。

總而言之，若基於群論的方案因量子或經典原因而失效，這些方案仍然代表我們目前對安全公開密鑰系統的最佳希望。然而，這些方案中最實用的變體也正是結構更為明確的變體，即使是相對輕微的演算法進展（例如次指數級的經典或量子演算法）也可能導致公開密鑰尺寸需要平方增大，甚至更大。儘管這僅是多項式級別的增長，但在現實世界中可能帶來重大影響。人們不能期望僅僅將一個  或  位元的密鑰「插入」到設計用於  位元密鑰的協議中並期望其能照常運作，這樣的結果可能會對我們在互聯網上進行安全保護的方式帶來顯著變革。例如，這可能導致權力的集中，密鑰交換變得極其昂貴，使用者僅能與少數大型企業和政府共享公開密鑰，而小型公司則不得不通過這些大型企業來進行通信路由。

備註 （Impagliazzo 的世界）。在一篇出色的綜述中，Impagliazzo  將計算複雜度的一個主要任務定義為確定我們所處的幾個在質上截然不同的「世界」中哪一個是真正存在的，參見圖 4。也就是說，他探討了根據我們目前所知，計算複雜度的未解問題可能落入的各種可能性，並觀察到它們如何影響演算法與密碼學。正如第 2 節所論，有非常充分的證據表明單向函數存在，這將排除 Impagliazzo 命名的三個世界：「Algorithmica」、「Heuristica」與「Pessiland」。本文可視為試圖理解排除潛在「Minicrypt」世界的證據——在該世界中，對稱密碼學（即單向函數）存在，但公開密鑰密碼學不存在。Impagliazzo 將存在公開密鑰密碼、可靠多方計算及其他類似原語的世界稱為「Cryptomania」；如今，人們也將甚至更為奇特的原語（如不可區分混淆存在的世界稱為「Obfustopia」。

圖3 ： 一個非主流公鑰密碼學備選的不完備列表

圖 4：來自 [Imp95] 的 Impagliazzo 世界觀的變體。我們重新定義 Cryptomania 為 LWE 成立的世界，並以 “Obfustopia” 表示存在不可區分混淆器 (IO) 的世界。

替代性的公開密鑰構造

上述基於群論及基於格的家族代表了公開密鑰加密的主要理論與實踐基礎，以及更先進的應用，包括安全多方計算、全同態加密和其他許多原語。然而，文獻中還提出了其他方案。我們在此不進行全面調查，但會提供一些參考（另一種觀點可參見 NIST 報告；如今，這類替代性構造通常歸類於「後量子密碼學」）。

Merkle 謎題

第一個由學術研究者提出的公開密鑰加密方案是 Ralph Merkle 的「基於謎題」方案，他在 1975 年提交給 ACM 通訊期刊，並在他於加州大學柏克萊分校開設的本科安全課程項目提案中有所描述，見圖 5。

圖 5：在 Merkle 基於拼圖的公鑰加密中，誠實方大約調用  次理想單向函數，而敵手若僅調用  次則無法破解該方案。

Merkle 的方案在一個理想化（且未完全規範化）的模型中，可使運行該方案所需的工作量與破解該方案所需的工作量之間產生最多達二次的差距。Biham、Goren 與 Ishai 證明，此模型可以利用指數級強的單向函數來實例化。

Merkle 猜測應該有可能獲得一個公開密鑰方案，使得誠實方與敵手之間的工作量存在指數級的差距，但他未能提出一個具體的候選方案。（第一個做到這點的是 Diffie 與 Hellman，他們根據 John Gill 的建議考慮模指數運算，提出了如今被稱為 Diffie-Hellman 密鑰交換的方案。）後續工作證明在將單向函數建模為隨機 Oracle 並以對該函數的查詢次數來衡量運行時間的設定下，Merkle 最初的協議是最優的。

需要注意的是，儘管  安全性與我們所期望的還有很大差距，但並非完全不可接受。正如 Biham 等人指出的，任何超線性的安全保證隨著技術進步都只會變得更好，因為隨著誠實方能夠承擔更多計算，其工作量與敵手工作量之間的比例也會隨之增大。

其他基於代數的構造

還有其他幾種公開密鑰加密方案的提議。其中一些方案為了實現更高的效率或其他吸引人的特性，使用了比上述更強的假設。我們在此僅簡要提及那些試圖使用質上不同的計算假設的方案。

隱藏域方程。Patarin 根據 Matsumoto 與 Imai 的工作提出了隱藏域方程 (HFE) 密碼系統。該系統基於有限域上二次方程問題的一種「植入」變種的難度。原始的 HFE 系統曾被 Kipnis 與 Shamir 破解，且一些變種也遭受過攻擊。目前看來，針對基於 HFE 的數位簽章已知的攻擊較少，但我們在此主要關注公開密鑰加密；更多已知攻擊細節可參考相關資料。

同源星。Rostovtsev 與 Stolbunov 提出了一個基於尋找兩個橢圓曲線之間同源（即一個代數同態）的密碼方案。儘管該方案受到了橢圓曲線密碼學的啟發，其安全性並不直接歸結於標準橢圓曲線密碼系統的安全性。具體而言，目前尚無已知的量子演算法能夠攻擊該方案，儘管有一些相關結果。此外，還有人提出以編織群braid groups的共軛問題作為密碼學的基礎，但針對這些提議也已有一些攻擊方法被展示。

組合(?) 構造

Applebaum、Barak 與 Wigderson [ABW10] 試圖探討是否能夠基於組合問題平均情況困難性的猜想來構造公開密鑰加密。誠然，這個術語並未有明確定義，儘管他們的焦點大多集中在約束滿足問題上，而這些問題可謂是典型的組合問題。

[ABW10] 基於以下猜想提出了一個公開密鑰加密方案的構造（見圖 6）。

圖 6：基於 Goldreich 生成器的 ABW 加密方案（簡化變種）

• 局部偽隨機生成器：這是對第2節中討論的 Goldreich 單向函數安全性假設的一種加強。也就是說，我們假設可以獲得一個將  位元映射到  位元的偽隨機生成器，其中每個輸出位都對固定數量  的輸入位應用某個謂詞 。此外，我們假設可以透過使用第 2 節中定義的隨機  二分圖來選擇哪些輸入位映射到哪些輸出位來實現此目標。
• 不平衡擴展問題：這是區分一個隨機  二分圖與一個在其中植入了一個大小為  的左側頂點集合  的圖的問題，其中要求  在右側的鄰居數至多為 （而在隨機圖中你預期會有約  個鄰居）。圖擴展問題已被廣泛研究，目前在這一參數範圍內尚無已知演算法。

當  相較於  越大時，第一個假設越強，而第二個假設則越弱。增大參數  會使第二個問題變得更難（事實上，根據  的不同，在某一點上該假設甚至會無條件成立，因為即使在隨機圖中也極可能存在這樣一個非擴展集合）。此外，總是存在一種在  時間內解決擴展問題的方法，因此較小的  使問題在數值上更容易。 [ABW10] 證明，若對一組參數 ，其中 ，這兩個假設均成立，則存在一個公開密鑰密碼系統。

根據構造，上述密碼系統的安全性無法超過 ，這比 Merkle 謎題所達到的  要好得多，但仍遠非理想。它還依賴於  與 poly(n)2 複雜度之間那微妙的區別。 [ABW10] 展示了如何獲得不同的權衡，如果我們不是對偽隨機生成器使用非線性函數 ，而是使用一個線性函數並添加一些概率性附加噪聲。為了實現高效解密，噪聲水平  應滿足 ，因此我們考慮的噪聲水平越低（也就是我們對偽隨機生成器的假設越強），我們能承擔的  值就越大。特別地，若我們假設噪聲水平足夠低，則可以使  變得足夠大，以完全避免第二個假設（關於檢測非擴展集合困難性）的需求。然而，有證據表明，在此情況下第一個假設變得更具「結構性」，因為它允許存在一個非構造性的短證據。

使用這樣的線性函數  引出了這樣一個問題：這些方案在多大程度上與基於編碼的方案（如 Alekhnovich 的）有所不同。事實上，這些方案之間存在相似之處，而主要差異在於使用了不平衡擴展假設。一個重要的問題是要找出該問題在組合性與代數性之間的區分程度。我們尚未完全理解這個問題，甚至還未找到合適的形式定義方法，但這似乎是判斷 [ABW10] 方案是否真正不同於基於編碼／格的構造的關鍵。一方面，不平衡擴展問題在「感覺上」是組合性的；另一方面，我們要求集合  的鄰居數少於  本身，這意味著如果我們對於  中每個右側頂點  定義一個線性方程，其對應於  中變量之和，則對應於  的這些方程是線性相關的。因此，這個問題可以被視為尋找一個短線性依賴的任務。

從噪聲水平來考慮這個問題可能比區分組合性與代數性更為恰當。也就是說，可以認為基於編碼／格構造的主要問題並非在於線性方程的代數性質（畢竟，背包問題與近似  問題均為 NP-hard），而在於它們使用的噪聲水平低於 （或等價地，使用的近似因子大於 ），這賦予它們某種結構，該結構可能成為潛在弱點的來源。特別地，使用如此小的噪聲與在格問題中使用大於  的近似因子非常相似，這也是基於格的方案能在 NP  coNP 中被破解的原因。然而，目前對於 [Ale11] 或 [ABW10] 方案均未有類似結果。

這種觀點引出了以下開放性問題：

• 我們是否可以基於解決  個隨機  方程（在  個變量上），其中有一個植入解滿足 （對於某個常數 ）的困難性，來構造公開密鑰加密方案？
• 對不平衡擴展問題的依賴是否在問題中引入了新的結構？例如，是否存在一個非確定性程序來證明圖中不存在一個短的非擴展子集？

對第二個問題，若能獲得一個針對不平衡擴展問題（參數與 [ABW10] 使用的匹配）的最壞情況 NP 近似困難性結果，便可作為否定答案的一個證據。目前我們尚不知此類結果是否有可能成立。

由不可區分混淆構造的公開密鑰密碼學

從 Diffie 與 Hellman 早期的著作開始，他們認為公開密鑰密碼學至少不是天生不可能的，其中一個原因如下：給定一組區塊密碼／偽隨機置換 ，可以想像固定一個隨機密鑰 ，並令  為一個在輸入  時輸出  的程式。現在，若將  透過某個「優化編譯器」編譯成低階表示（例如組合語言），就可以想像從該表示中「提取」密鑰  將十分困難。因此，人們期望能夠構造一個公開密鑰加密方案（或更精確地說，一個陷門排列族），方法是令公開加密密鑰為  的這個表示（其能計算映射 ），而將私密解密密鑰（或陷門）設為能計算映射  的秘密密鑰 。看來，獨立在英國情報機構 GCHQ 發明公開密鑰密碼學的 James Ellis 也有類似的想法。

Diffie 與 Hellman 從未能找到足夠好的該想法的實例化方案，但多年來，人們一直在嘗試尋找能夠將一個程式  轉換為功能等價但「難以理解」形式的混淆編譯器。許多實際的混淆嘗試已被破解，而論文指出，混淆安全性的自然定義其實是無法實現的。然而，該論文給出了一個較弱的安全定義，稱為*不可區分混淆 (IO)*，並指出其不可能性結果並未排除 IO 的可能性。（參見相關調查報告）

在最近的一次突破中，有人提出了一個 IO 編譯器的候選構造。他們還展示（見圖 7）一個 IO 編譯器足以實現 Diffie 與 Hellman 僅基於單向函數構造公開密鑰加密方案的夢想。從初步看來，這或許就像用鑽石製成的開瓶器一樣合理：畢竟，我們已經能夠基於含錯誤學習假設構造公開密鑰加密，而若能基於 LWE 構造 IO，將是一項具有廣泛應用的重大突破。事實上，若 LWE 容易，則目前許多候選 IO 構造都將輕易被破解。（而實際上，即便如此，它們也可能被破解。）

然而，先驗地來看，要達成 IO 是否必須依賴代數方法並不明顯。雖然目前看來，這一目標與我們現有的任何技術均相去甚遠，但我們可以期待，或許通過更具組合性或程式轉換的方法，而不依賴 LWE，就能構造出 IO 混淆器。一線希望來自於這樣一個觀察：儘管 IO 有著眾多應用，但到目前為止，我們尚未能獲得例如全同態加密這類原語，而這類原語會暗示 （另見相關文獻）；相比之下，這些原語卻可以從 LWE 推出。

安全性論證：我們需要證明  與  難以區分。由於  的偽隨機性，這一情形難以區分於  從  中隨機選取的情形。但在高概率下，，因此  與  均為恆零函數，進而依據 IO 性質， 與  難以區分。

圖 7：由不可區分混淆與單向函數構造的公開密鑰加密方案。

計算困難性是規則還是例外？

只要 P 與 NP 的問題仍未解決，密碼學就必須依賴未經證明的假設。區分例如 LWE 困難性這樣的假設與假設生成對稱密鑰加密所依賴問題的困難性，是否真的有意義？這是一個合理的疑問。畢竟，許多人會爭辯，我們唯一真正證明  的證據，就是眾多嘗試為 NP-難問題設計演算法卻屢屢失敗，而對於 LWE 假設亦存在同樣的證據。

然而，我確實認為這些假設之間存在質的差異。原因在於，假設  能夠產生一個連貫而美麗的計算困難性理論，且該理論與目前所有觀察結果相符。因此，我們接受這一理論，不僅因為我們不知道如何駁斥它，更因為根據奧卡姆剃刀原則，應當接受最簡潔、最節省的理論來解釋我們所認知的世界。單向函數的存在，以及它與其他問題之間所展示的豐富歸約網絡，也構成了這樣一個理論。事實上，這些歸約已表明單向函數是幾乎所有密碼學依賴的最小假設。

相比之下，儘管 LWE 有許多推論，但尚未證明其對於「Cryptomania」而言是最小的假設，換言之，目前尚未知道是否有任何原語（例如公開密鑰加密，甚至更強的全同態加密）能推出 LWE。此外，我們也沒有一個清晰的平均情況困難性理論來蘊含 LWE 的難度（或公開密鑰加密的存在）。

事實上，我認為可以公平地說，我們根本沒有一個明確的平均情況困難性理論。主要原因在於，歸約 —— 作為最壞情況困難性理論以及密碼學原語之間歸約網絡的基石 —— 在這種情況下似乎應用非常有限。通常，從問題  到問題  的歸約，通常將  的一般實例轉換成  的一個具有結構的實例。例如，從 3SAT 到 3COL 的典型歸約，將一個一般公式  轉換成一個圖 ，該圖具有特定形式，其中特定的小工具對應於  中的每一個子句。這足以證明若  在最壞情況下困難，則  亦然，但並不能證明若  在例如均勻隨機實例上困難，則  也同樣困難。因此，歸約在關聯不同問題最壞情況複雜度或利用某一問題的猜測平均情況困難性來展示其他針對性實例問題的困難性方面極為有用。然而，總體而言，我們尚未能利用歸約來關聯自然平均情況問題的難度，於是我們擁有一組彼此不可歸約的不可比較任務，包括整數分解、離散對數、RSA 問題、尋找植入團、尋找 3SAT 公式中植入的賦值、LWE 等，彼此間沒有任何歸約。

即使是成功的最壞情況複雜度理論，也可說更多是描述性或預測性的，而非解釋性的。也就是說，它告訴我們哪些問題是困難的，但並未真正解釋為何它們困難。雖然這似乎不是一個明確定義的問題，就像問「為什麼 17 是質數？」一樣，但讓我試著賦予其更多含義，並說明一個解釋性計算困難性理論在平均情況複雜度等情況下如何可能有所幫助，而在這些情況下歸約似乎無法提供幫助。

那麼，到底什麼使得一個問題變得容易或困難？為了獲得一些線索，我們可以觀察算法專家在求解問題時採用的技巧，以及密碼學家在構造困難問題時所做的努力。顯然，存在大量求解問題的算法技術，尤其是許多巧妙的資料結構與優化方法，這些方法在理論上可能僅能帶來中等程度的改進（例如降低指數），但在實際應用中卻能產生決定性影響。然而，若我們僅限於那些能證明問題能以比窮舉搜索更好方式求解的技術，就會發現有一些主題反覆出現。其中一個主題便是局部搜索。從一個初始解的猜測出發，然後進行局部改進，這是許多算法背後的重要工作馬。這類算法關鍵在於問題具有一種結構，使得局部最優解（或至少是你可能遇到的所有局部最優解）對應於全局最優解。換句話說，它們依賴於某種形式的凸性。

另一個主題是利用代數消去。最簡單的這種結構便是線性性，在這種情況下，我們可以不使約束的複雜度激增而不斷從舊約束中推導出新約束。具體而言，一個代數消去的經典例子是高效計算矩陣行列式的算法，儘管至少一個標準定義涉及計算指數級項數之和，但該算法依然能夠奏效。

在密碼學方面，當應用密碼學家試圖構造一個難以逆轉的函數（如雜湊函數或區塊密碼）時，也會出現一些反覆出現的主題。為了使一個函數難以逆轉，設計者試圖引入非線性（即該函數在任何域上均不應呈現線性或近似線性，實際上應具有高代數次數，以使其難以「線性化」）以及非局部性（我們希望輸入與輸出位之間的依賴結構是「擴散」或「分散」的）。實際上，這些主題不僅在應用構造中出現，也出現在如 Goldreich 的 [Gol11] 以及 Gowers 的 [Gow96] 等理論候選中（各自將某類參數推向極端）。

綜合上述觀察，這可能引導我們形成一種世界觀：除非某個問題具有使其變得容易的結構性原因，否則應當假定計算問題是困難的。基於這種結構的理論能夠幫助預測，甚至進一步解釋目前我們無法通過歸約證明困難性的眾多計算問題的難度。然而，我目前並不知道有任何如此明晰的理論不會最終「預測」出某些實際上可由巧妙算法或改變表示方式解決的問題是困難的。在綜述 [BS14] 中，Steurer 與我試圖通過猜想平方和凸規劃在某些領域中是最優的，來提出一種潛在的方法以建立這樣的理論。雖然提出這樣的猜想似乎是在從密碼學作為一門科學倒退到「煉金術」的方向，但我們仍希望能夠在不犧牲密碼理論預測力與數學精確性的前提下，提煉出一些實踐者所具有的「煉金術師直覺」。然而，這項研究仍處於初期階段，我們甚至還不知道如何正確形式化我們的猜想，更不用說嘗試證明它們或研究其影響。我真心希望最終能夠出現一個解釋性的困難性理論，無論是通過凸優化還是其他方法，這一理論不僅能幫助我們設計出具有更堅實安全基礎的密碼方案，還能為高效計算這一神秘現象提供更多啟示。