一個密碼學證明可以通過讓缺失的模擬器難以被證明來隱藏其秘密

訣竅不是證明秘密被隱藏了

從零知識最簡單的版本開始。

Alice 想說服 Bob：某個數獨謎題有解。如果她把解發過去，Bob 就信服了，但謎題也就被毀了。她想要的東西更奇怪：一個證明解存在、卻不洩露解本身的證明。

這就是零知識證明的承諾。證明者（Alice）說服驗證者（Bob）某個陳述為真，同時除了該陳述為真這一點之外不洩露任何東西。

問題在於，這個承諾是有代價的。一個普通的數學證明有兩個令人舒適的特徵。它是一條消息：你把它寫下來，交出去，然後走開。而且它是完美可靠的：一個假的陳述根本沒有任何有效的證明。經典的不可能性結果表明，零知識必須放棄這兩個特徵——而且不僅僅是二者一起放棄；每一個特徵單獨來看都是禁區。

首先，零知識證明需要對話。如果 Alice 發送一條消息，而事先沒有安排任何可信設置，那麼零知識保證就會崩潰——而且無論你願意為交換而放棄多少可靠性，這一點都成立。

其次，零知識證明需要對錯誤有一點點容忍。事實證明，要求完美可靠性也會悄悄地摧毀交互：一個無論做出哪些隨機選擇都永遠不會被欺騙的驗證者，不如乾脆事先把那些選擇固定下來——而一旦驗證者是可預測的，Alice 就可以在一條消息裡回答所有問題，這恰恰就是前面已經崩潰的那種情形。

Rahul Ilango 的論文講的是一種繞過這道雙重高牆的方法。不是假裝這堵牆不存在，也不是在那個不可能的設定下造出經典的零知識。這一手更微妙：削弱「不洩露任何東西」的含義，但以一種能保留密碼學家實際上可以檢驗的安全性質的方式來削弱它。

這個結果被稱為有效零知識。

舊的檢驗：存在一個模擬器

將零知識形式化的經典方法用到了一個虛構的助手，叫作模擬器。

想法是這樣的：想像一個叫 Jane 的人，她不知道 Alice 的秘密。如果 Jane 完全靠她自己就能生成一些看起來和 Bob 本會從 Alice 那裡收到的證明一模一樣的證明，那麼 Alice 的證明並沒有教給 Bob 任何新東西。Jane 在沒有 Alice 秘密的情況下就已經能偽造出這種體驗了。

所以經典零知識要求有一個真正的模擬器。必須存在一個高效的演算法，它能在不知道秘密——用行話說就是見證——的情況下生成看起來像模像樣的假證明；對數獨來說，見證就是那張解好的網格。

這個定義很強大，但它也恰恰是舊的不可能性發作的地方。直覺是這樣的。一個真正非交互的證明只是一個字串。一旦 Bob 拿到了這個字串，他就可以把它拿給別人看：他獲得了向他人證明該陳述的能力，這聽起來已經不止是「什麼都沒有」了。經典定理把這個直覺銳化成了上面那些不可能性。

這個區別的超級數獨版本

下面是一種刻意簡化的、用來感受這個區別的方式。

在這個類比的嚴肅部分，不要用普通的 9×9 數獨。它太小、太有限了：電腦可以直接解出它，或者證明它無解。取而代之，想像一族 MegaSudoku(n)（超級數獨）謎題。把通常的規則放大：選擇一個塊大小 n，令 N = n^2，構建一個 N × N 的網格，劃分為 n × n 的塊，使用 N 個符號。普通數獨只不過是那個很小的 n = 3、N = 9 的情形：一個 9×9 的網格、3×3 的塊和九個符號。只有當允許 n 增長，並且當網格可以承載額外的小配件（gadget），使它表現得像一個偽裝成數獨謎題的 SAT 公式時，證明複雜度的故事才真正開始。一個 SAT 公式只不過是一列是/否約束：你能否給這些變數賦上真/假值，使得每一個約束都被滿足？

見證仍然很容易想像。Alice 知道超級數獨的一種完整的合法填法。Bob 想要被說服這樣一種填法存在，但 Alice 不想把它洩露出來。如果她把整個填法發過去，Bob 就信服了，但秘密也就沒了。

在經典零知識的版本裡，Alice 和 Bob 進行交互。一個老派的思維模型用到了蓋住的方塊。Alice 把解好的網格藏起來，在每一輪之前偷偷地給符號重新命名，然後讓 Bob 檢查一個隨機選中的局部約束：一行、一列、一個宮，或者一個 gadget。如果被揭開的格子顯示出的符號兩兩不同，Bob 就增加了幾分信心。然後一切又被蓋起來，符號也被重新命名一遍。（有一個小麻煩：謎題給定的提示需要一個額外的技巧，因為給符號重命名也會把它們藏起來。下面的說明解釋了經典協議如何解決這個問題；對於接下來的內容，這個玩具式的圖景已經足夠了。）

這並不是論文裡的協議。它是經典零知識的思維模型：

• Alice 和 Bob 來回往復。
• Bob 選擇隨機的檢查。
• Alice 只揭示局部的一致性，而不是整個解。
• 隱私性的證明是通過表明 Bob 所看到的視圖本可以在沒有 Alice 秘密解的情況下被生成來實現的。

所以經典零知識是圍繞一個肯定的事實建立起來的：

一個模擬器真的存在。

現在把那些令人舒適的部分去掉。Alice 發送一個證明字串，然後走開。沒有可信設置，沒有事先準備好的共享隨機字串，而且 Bob 絕不能接受一個假的謎題。這就是經典零知識無法存活的那個設定。

在這個訣竅之前，還需要一個角色。固定一個規則手冊：邏輯學家意義上的一個形式證明系統——一組固定的公理，加上用來檢查書面數學證明的機械規則。ZFC，即數學的標準公理，就是那個典範的例子。從這裡開始的一切，都是相對於一個事先選定的規則手冊來陳述的，而且這個選擇是靈活的：這個構造對你固定的任何規則手冊都成立，包括 ZFC。

（一個關於用詞的說明，借自論文本身：這裡的「證明系統」始終指的是這個規則手冊——那個檢查數學證明的形式系統——而絕不是 Alice 發送的消息。Alice 和 Bob 的那套機制被稱為「證明者和驗證者」。）

哥德爾風格的版本保留了超級數獨的故事，但改變了證明。

挑選第二個顯示尺寸相同的約束系統，把它叫作 D。就故事而言，S 和 D 是兩個格式相同的 MegaSudoku(n) 謎題。在幕後，D 可能一開始是一個尺寸不同的困難邏輯公式；如果需要，可以用一些無害的虛設約束把它填充起來，讓它適配同一個網格。D 是由一個實際上不可滿足的邏輯公式構造出來的：不存在任何一種可能的賦值能讓它所有的約束都為真，就像一個壞掉的謎題沒有合法的完成網格一樣。一個玩具式的例子會是一個既要求「X 為真」又要求「X 為假」的公式。所以 D 沒有合法的填法。

但 D 不能是一個容易被揭穿的壞掉的謎題。上面那個玩具例子就不合格：任何規則手冊都能用一行反駁「X 且非 X」。D 必須以一種所選規則手冊無法用簡短論證來證實的方式為假。如果規則手冊能用一個簡短的證明反駁 D，下面的故事就會崩塌：那條本可能在沒有 Alice 秘密的情況下產生證明的替代路線，就可以被形式地排除掉，隱私保證也隨之一起排除掉。所以 D 是從一個固定規則手冊無法高效反駁的族中挑選出來的：在那個規則手冊內部，不存在關於 D 無解的簡短證明。

於是 Alice 的一條消息證明所針對的是一個二選一的陳述：

要麼真正的超級數獨 S 有解，要麼誘餌 D 有解。

這就是那個邏輯上的聯繫。D 並不是以某種能讓 S 為真的魔法方式生成的。這個證明並不是在論證「D 無解，因此 S 有解」。它證明的是析取式 S 或 D。完美可靠性說的是一個假的析取式不可能有有效的證明。既然 D 在現實中為假——它沒有解——那麼這個析取式能為真的唯一途徑就是 S 為真。所以如果證明被接受，S 就必然有解。誘餌沒法讓一個假的 S 變成真的。

但對於零知識風格的那一部分，問一問如果 D 確實有解會發生什麼。那個誘餌的解會充當一個替代的見證。它會讓某人在不知道 Alice 真正的超級數獨解的情況下也能產生證明——換句話說，就是一個模擬器。在現實中 D 沒有解，所以這條模擬器路線是封閉的。關鍵在於，規則手冊無法高效地證明它是封閉的。

所以 D 有兩項工作。對於可靠性，D 為假，因此一個關於「S 或 D」的有效證明強制 S 成立。對於有效零知識，D 難以反駁，因此規則手冊無法迅速排除那條本會讓模擬成為可能的誘餌路線。

所以安全性的檢驗不再是：

我們能否證明一個模擬器真的存在？

它變成了：

你的規則手冊能否高效地證明這個模擬器不可能存在？

如果答案是否定的，就會得出某種出人意料地強的結論：每一個滿足如下兩條的安全保證——(a) 可以通過運行一個測試來觀察到，並且 (b) 在那個規則手冊內部，可證明地從模擬器的存在推出——實際上都成立。對它們中任何一個的成功攻擊，本身就相當於那個缺失的簡短反駁，而那個缺失的簡短反駁並不存在。這就是「有效零知識」裡「有效」的那一部分。

所以課堂上的對比是：

經典零知識： 這些證明是安全的，因為存在一個模擬器。

哥德爾風格的有效零知識： 對於可觀察的安全性測試，這些證明被當作是安全的，因為規則手冊無法高效地證明這個模擬器不可能存在。

第二個斷言更弱。它也正是論文能夠保留那三個打垮了經典版本的特徵的原因：一條消息、無設置和完美可靠性。

新的檢驗：你無法證明模擬器不存在

Ilango 的鬆弛改變了問題。

經典零知識問的是：

是否存在一個模擬器？

有效零知識問的是某種更弱的東西：

你所選的規則手冊能否高效地證明不存在任何模擬器？

這聽起來像是一個技術性的躲閃，但它正是核心思想。這個構造處於一種奇怪的狀態：模擬器實際上並不存在——論文對這一點說得很明確——但你所固定的那個規則手冊無法高效地證明它不存在。如果你所關心的每一個壞後果都需要這樣一個反駁，那麼對於那些後果來說，這個系統仍然表現得像零知識。

這裡就是哥德爾登場的地方。不是作為裝飾，也不是「哥德爾讓密碼學變安全」。這個聯繫是證明論意義上的。一個規則手冊被稱為最優的，如果它在一個精確的意義上是可能的最好的那一個：每當任何一個規則手冊能用一個簡短的證明反駁某種相關類型的公式時，那個最優的規則手冊也能，用一個至多多項式地更長的證明。Krajíček 和 Pudlák 在 1989 年猜想不存在最優證明系統：無論你固定哪個規則手冊，總有另外某個規則手冊能遠為簡潔地證明某一族真陳述。這是證明複雜度的核心未解猜想之一，也是哥德爾不完備性定理在有限的、複雜度理論意義上的表親：有些真陳述在你所固定的規則手冊裡沒有簡短的證明——不是因為它們原則上不可證明，而是因為每一個固定的規則手冊都會留下一些簡短的真理，它們沒有簡短的證明。

論文假設這個猜想（以一個稍強的「無窮頻繁」形式，這是把猜想用於密碼學時的標準做法）。根據 Krajíček 和 Pudlák 的一個定理，回報是具體的：對每一個規則手冊，都存在一個公式序列，它們確實不可滿足，規則手冊無法用簡短的證明反駁它們——而且，至關重要的是，一個高效的演算法能夠生成它們。最後那個性質，即一致性（uniformity），正是把整個想法從一個存在性斷言變成 Alice 真正能運行的一個演算法的東西：她的誘餌 D 是從流水線上下來的，而不是憑空變出來的。

密碼學上的這一手，就是把那種證明能力的短缺利用起來。

這個構造在做什麼

下面是論文的構造，被剝到只剩它的骨架形狀。

固定一個規則手冊——比如說 ZFC。在證明複雜度假設之下，存在一個可高效生成的公式序列，它們實際上不可滿足，但規則手冊沒有關於它們不可滿足的簡短證明。

現在構建一個如下形式的一條消息證明：

要麼真正的陳述可滿足，要麼這個特殊的困難公式可滿足。

這個特殊的困難公式是不可滿足的。所以如果底層的證明機制是完美可靠的，接受這條消息仍然意味著真正的陳述為真。這就給出了完美可靠性。

但對於類似零知識的安全性，想像這個特殊的困難公式確實可滿足。那麼它的見證就可以被用來在不知道真正見證的情況下模擬證明。這個公式在現實中不可滿足——但規則手冊無法高效地證明這一點。所以它無法高效地證明這個模擬器不可能存在。

這就是那個樞紐。這個系統不是通過產生一個經典的模擬器來隱藏秘密的。對於一大類可觀察的安全性測試來說，它把秘密藏在了規則手冊無力證實模擬器不存在的背後。

論文主張了什麼

主定理是分層的。核心結果是這樣的：

在一個標準的密碼學假設——非交互見證不可區分證明的存在，這是一類被充分研究過的對象，可從若干已確立的假設包中推出——之下，以及在不存在（無窮頻繁）最優證明系統這個證明複雜度猜想之下，論文為每一個規則手冊的選擇都構造了一個針對 NP/SAT 的一條消息證明者和驗證者，它具有完美可靠性、無設置，並且相對於那個規則手冊是有效零知識的。（NP/SAT 是各種謎題式問題的標準「最難公分母」；超級數獨是它所穿的一件戲服。）

對於那個關於保留可證偽安全性質的更寬泛的主張，論文再添加一個標準假設，即去隨機化的信念 P = BPP（大致是說：隨機性沒有給演算法帶來任何本質上的額外能力）。

把定理的語言翻譯過來：

• 證明是一條消息。
• 沒有可信設置。
• 假的陳述無法被證明。
• 這個證明者不是經典零知識的——它沒有模擬器。
• 但經典零知識的每一個可證偽的、基於博弈的安全性後果，都可以在這個設定中實現。

「可證偽」這一點很重要。它意味著一次安全失敗可以通過在一場博弈中運行一個對手來測試。許多密碼學的安全定義都有這種形式：對手能否區分兩個密文、求逆一個函數、恢復一個見證，或者贏得某個指定的實驗？這個定理為每一個可證偽的性質各給出一個證明者，一次一個。一個同時享有每一個可證偽性質的單一證明者很可能是不可能的——舊的可重用性攻擊（「Bob 可以把證明拿給別人看」）本身就是一個可證偽的性質，而它在這裡確實失敗了。論文的提議是，一個單一的證明者有理由能夠涵蓋所有自然的可證偽性質——那些在密碼學實踐中真正出現的性質——但那一部分是一個條件性的定理，依賴於一個非正式的「自然」概念，外加一個明確的猜想。這個保證針對的是可觀察的失敗，而不是保密性的每一種哲學意義或基於模擬的意義。

有一個具體的推論值得點名：這個構造給出了第一個帶有一致證明者的非交互見證隱藏證明——「一個謎題的證明並不能幫你找到它的解」，沒有交互也沒有設置——這是一個聽起來不起眼、卻抵抗了數十年構造嘗試的對象。

這不是在說什麼

這是讓整篇文章保持誠實的那一節。

它並不是說舊的不可能性定理是錯的。這個構造是通過改變定義來繞開它們的。

它並沒有給出無交互、無設置和完美可靠性的普通的、經典的零知識。論文明確地說，所構造的證明者沒有模擬器。

它並不意味著這個證明不能被重用。一條消息的證明仍然可以拿給別人看；論文並沒有保留可否認性那一類的性質。（帶可信設置的非交互零知識也有同樣的局限。）

它並不意味著這是一個可以部署的實用協議。這是複雜度理論和密碼學基礎。這個結果依賴於來自證明複雜度和密碼學的重大假設，而這個構造關乎的是原則上什麼是可能的。

它並沒有把「哥德爾」變成一個魔法般的安全原語。哥德爾的聯繫是通過證明系統、最優證明系統以及不完備性的有限類比來實現的。可用的直覺不是「不完備性保護你的密碼」。而是：如果一個規則手冊無法高效地證明一個模擬器不可能存在，那麼那些需要該證明的攻擊就可以在安全定義的層面被擋住。

為什麼它無論如何都很有趣

密碼學常常把困難性轉化為安全性。因數分解是困難的，所以 RSA 式的假設變得有用。格問題是困難的，所以格密碼學變得有用。這裡的困難性更奇怪：不是「難以計算出一個秘密」，而是「難以證明某個證明對象不可能存在」。

這就是為什麼這篇論文讓人感覺不同尋常。它幾乎把公理和規則手冊當作密碼學資源來對待。通常的不可能性說的是，可靠性和模擬之間存在一種張力。Ilango 這一手，是把這種張力放到一道證明論的帷幕後面：模擬器不存在，但形式系統無法高效地揭露這種不存在。

對一個讀者來說，令人驚訝的部分並不是這將取代今天的零知識系統。它大概不會，至少不會直接取代。令人驚訝的部分在於，一個來自數理邏輯的局限性可以被建設性地使用：不只是作為一堵牆，而是作為一種掩護。

證據有多強？

這是一篇定理論文，所以「證據」的含義不同於一篇生物學或天文學論文。問題不在於一個實驗是否被複現。問題在於那些定義、假設和證明鏈條是否支持這個主張。

證明是形式化的，而且論文對它的假設說得很明確。這些假設不是隨隨便便的。非交互見證不可區分證明是密碼學中的標準對象，可從若干已確立的假設包中推出。不存在最優證明系統這個猜想是證明複雜度中的一個核心猜想。P = BPP 是一個標準的去隨機化信念，只用於那個更寬泛的可證偽性質定理。

論文還論證說，這些假設是恰當的代價，而不是一個隨意搭起來的腳手架：它證明了一個逆命題，表明這些假設本質上是必要的——如果像這樣的構造根本存在，那麼非交互見證不可區分證明就必然存在，並且（在承認標準單向函數的前提下）不可能存在最優證明系統。而且這些假設是「雙贏」的：反駁它們中的任何一個，本身就會是證明複雜度、密碼學或複雜度理論中的一個里程碑式的發現。

但由於這個結果是條件性的，它的可信度也是條件性的。如果那些假設不成立，定理的解讀就會改變。而且即便那些假設成立，這個保證也不是完整的經典零知識；它是論文那個鬆弛過的、證明論意義上的版本。

所以恰當的可信度是：對於論文確立了一個自洽的條件性可能性結果這一點，是高的；對於它的假設描述了我們實際所處的密碼學世界這一點，是中等的；而對於任何即時的實用後果，則是低的。

為什麼這很重要

這篇論文打開了一條本應封閉的路線。

經典理論說：完整的零知識不可能是無設置的一條消息，也不可能是完美可靠的。Ilango 的論文說：如果我們要的是零知識那些可以在安全博弈中被測試的後果，並且如果我們允許安全定義取決於一個規則手冊能或不能高效反駁什麼，那麼許多有用的行為就可以被恢復——用一條消息、無設置和完美可靠性。

這並不是一個小小的定義上的微調。它是一種思考密碼學保證的不同方式。不要只問什麼存在，而要問你的規則手冊能排除什麼。不要把不可證明性當作一種哲學上的煩擾，而要把它當作一種結構來使用。

實用的世界可能不會在明天就改變。但概念上的地圖變了。現在有了一種形式上的意義，在這種意義下，「沒有人能高效地證明秘密洩露了」可以強到足以恢復許多我們本想從「秘密沒有洩露」中得到的、基於博弈的保護。

這就是為什麼哥德爾理應出現在標題裡。

乾淨的總結

零知識證明讓一個證明者能夠說服一個驗證者某個陳述為真，而不洩露見證。經典的不可能性結果說，零知識不可能被塞進無設置的一條消息裡，也不可能具有完美可靠性。Rahul Ilango 的論文並沒有反駁那些不可能性。它定義了一個更弱的概念，即有效零知識：它不是要求一個模擬器真的存在，而是要求一個所選的證明系統——一個像 ZFC 那樣的形式規則手冊——無法高效地證明不存在任何模擬器。在來自密碼學（非交互見證不可區分證明）和證明複雜度（不存在最優證明系統）的重大假設之下，論文為 NP/SAT 構造了無設置、完美可靠的一條消息證明者，它們逐個性質地實現了零知識那些可證偽的、基於博弈的後果。一個單一的證明者涵蓋所有「自然的」這類性質，是一個更進一步的、部分帶有猜想性的擴展——而要涵蓋字面意義上每一個可證偽的性質，則很可能是不可能的，因為證明仍然是可重用的。這個結果是理論性的、條件性的，不是一個已部署的原語，但它展示了一種把證明論意義上的不可證明性用作密碼學資源的新方法。

不扯淡核查

論文展示了什麼： 在所陳述的假設之下，人們可以為 NP/SAT 構建一條消息、無設置、完美可靠的證明者，它們相對於任何所選的證明系統都是有效零知識的，並且實現了經典零知識每一個可證偽的、基於博弈的後果。

什麼是有道理但並未被無條件證明的： 所需要的證明複雜度和密碼學假設成立。它們是嚴肅的、被充分研究過的假設——而且論文表明它們不僅充分，還本質上是必要的——但仍然是假設。

它沒有展示什麼： 無交互、無設置和完美可靠性的經典零知識；一個可以部署的實用系統；證明的可否認性或不可重用性；或者哥德爾不完備性定理本身就能保障密碼學的安全。

主要局限： 這個保證是零知識的一個鬆弛；最寬泛的版本依賴於多個假設；單一通用證明者的那些主張仍然部分帶有猜想性；而且這個結果主要是基礎性的。

一個普通讀者應該有多少信心？ 如果接受那些定義，那麼對於這是一個重要的條件性理論結果這一點，信心是高的。對於這些假設抓住了現實這一點，是中等的。對於即時的實用部署，是低的。安全的要點是：這篇論文並沒有打破零知識的不可能性；它找到了一種新的、證明論意義上的方法，繞過它們當中對許多安全博弈來說重要的那些部分。