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

關鍵不在於證明秘密已被隱藏

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

Alice 想讓 Bob 相信一個數獨有解。如果她把解答傳給 Bob，Bob 會相信，但數獨也就被破壞了。她想要的是更奇怪的東西：證明解答存在，卻不透露解答本身。

這就是零知識證明的承諾：證明者（Alice）讓驗證者（Bob）相信某個陳述為真，除了這個陳述確實為真的事實之外，什麼也不透露。

問題在於，這個承諾是有代價的。一般數學證明有兩個令人安心的特點。第一，它是單一訊息：你把證明寫下來、交出去，然後離開。第二，它是完美健全的：虛假陳述根本沒有任何有效證明。經典的不可能性結果指出，零知識必須放棄這兩項特點——而且不只是兩者不能同時保留；每一項單獨都不行。

首先，零知識證明需要對話。如果 Alice 在事先沒有安排任何可信設定的情況下只傳送一則訊息，零知識保證就會崩潰——不論你願意以多少健全性作為交換，這點都成立。

其次，零知識證明需要容許一點錯誤。事實證明，要求完美健全性也會悄悄摧毀互動性：一個無論隨機選了什麼都永遠不會被騙過的驗證者，還不如預先固定那些選擇——而一旦驗證者變得可預測，Alice 就能用單一訊息回答所有問題，這正是前一種情況已經失敗的地方。

Rahul Ilango 的論文提出了一條繞過這道雙重高牆的路。不是假裝高牆不存在，也不是在不可能的設定中製造經典零知識。這個做法更細緻：削弱「什麼都不透露」的含義，但以一種保留密碼學家實際能檢驗的安全性質的方式削弱它。

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

舊測試：模擬器存在

將零知識形式化的經典方法，會引入一個虛構的助手，稱為模擬器。

想法是這樣：想像有一位不知道 Alice 秘密的 Jane。如果 Jane 完全靠自己，就能產生看起來與 Bob 從 Alice 那裡收到的證明相同的內容，那麼 Alice 的證明就沒有教給 Bob 任何新東西。即使沒有 Alice 的秘密，Jane 也能預先偽造出同樣的經歷。

因此，經典零知識要求一個真實存在的模擬器。必須有一個有效率的演算法，能在不知道秘密——術語稱為 witness，也就是「見證」；對數獨而言，見證就是解出的棋盤——的情況下，產生看似真實的證明。

這個定義很強，但也正是舊有不可能性結果發揮作用的地方。直觀來說，真正非互動的證明只是一串字串。Bob 一旦取得那串字串，就可以把它展示給別人：他獲得了向其他人證明該陳述的能力，而這聽起來已經不只是「什麼都沒有」了。經典定理把這個直覺進一步精確化為前述的不可能性。

超大型數獨版本的差異

以下用一個刻意簡化的例子，幫助我們感受其中差異。

嚴肅討論這個類比時，不要使用普通的 9×9 數獨。它太小，也太有限：電腦可以直接解出來，或證明它無解。請改想像一族 MegaSudoku(n) 數獨。把通常的規則放大：選定區塊大小 n，令 N = n^2，再建立一個 N×N 的棋盤，分成 n×n 的區塊，使用 N 種符號。普通數獨只是很小的 n = 3、N = 9 情況：9×9 棋盤、3×3 區塊和九種符號。只有當 n 可以增長，而且棋盤能攜帶額外的小工具，使它表現得像一個披著數獨外衣的 SAT 公式時，證明複雜度的故事才開始。SAT 公式只是一份真假限制清單：能不能替變數指定真／假值，使每項限制都得到滿足？

這個見證仍然很容易想像。Alice 知道超大型數獨的一份完整、有效填法。Bob 想被說服這樣的填法存在，但 Alice 不想透露它。如果她傳送整份填法，Bob 會相信，但秘密也就消失了。

在經典零知識版本中，Alice 和 Bob 會互動。一種老派的心智模型使用覆蓋的牌片。Alice 藏起已解出的棋盤，在每一輪之前秘密重新命名符號，讓 Bob 檢查一個隨機選出的局部限制：一列、一欄、一個區塊，或一個小工具。如果揭開的儲存格顯示彼此不同的符號，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 的定理，其具體收益是：對每一本規則書，都存在一串確實不可滿足的公式，規則書無法用短證明反駁它們——更關鍵的是，有一個有效率的演算法可以產生這串公式。最後這項性質稱為一致生成性，它把整個想法從存在性主張變成 Alice 真能執行的演算法：她的誘餌來自生產線，而不是憑空出現。

密碼學上的做法，就是利用這種證明能力的不足。

這個構造在做什麼

以下是論文構造的骨架版。

固定一份規則書——例如 ZFC。在證明複雜度假設下，存在一串能有效率產生的公式；它們實際上不可滿足，但規則書沒有證明它們不可滿足的短證明。

現在建立一個如下形式的單一訊息證明：

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

特殊的困難公式並不可滿足。因此，如果底層證明機制是完美健全的，接受這則訊息仍然代表真正的陳述為真。這就提供了完美健全性。

但對零知識式安全性而言，想像特殊的困難公式如果可滿足。那麼它的見證就能在不知道真正見證的情況下，用來模擬證明。公式在現實中不可滿足——但規則書無法有效率地證明這一點。因此，它也無法有效率地證明模擬器不可能存在。

這就是支點。系統不是靠產生經典模擬器來藏起秘密。對一大類可觀察的安全測試而言，它是把秘密藏在規則書無法證明模擬器不存在這件事背後。

論文聲稱了什麼

主要定理分成幾層。核心結果如下：

在一項標準密碼學假設——存在非互動見證不可區分證明，這是廣受研究且可由數個已建立的假設套件推出的物件——以及「不存在（無窮多次的）最佳證明系統」這項證明複雜度猜想下，對每一份規則書，論文都能為 NP/SAT 構造一個單一訊息的證明者與驗證者；它具有完美健全性且無需設定，並相對於該規則書達到有效零知識。（各類謎題問題通常都可歸結為 NP/SAT 這個標準的困難核心；超大型數獨只是它的一種外觀。）

對於保留可證偽安全性質的更廣泛主張，論文再加入一項標準假設，即去隨機化信念 P = BPP（大致來說：隨機性不會為演算法帶來本質上的額外能力）。

把定理語言翻譯出來：

• 證明只有一則訊息。
• 沒有可信設定。
• 虛假陳述無法被證明。
• 證明者不是經典零知識——它沒有模擬器。
• 但經典零知識所有可證偽、基於遊戲的安全性後果，都能在這個設定中達成。

「可證偽」很重要。它表示安全性失敗可以透過在一場遊戲中執行攻擊者來測試。許多密碼學安全性定義都採用這種形式：攻擊者能否區分兩個加密結果、反轉某個函數、取回見證，或在指定實驗中獲勝？定理針對每一項可證偽性質，各自給出一個證明者。單一證明者同時享有每一項可證偽性質，很可能是不可能的——舊有的可重用性攻擊（「Bob 可以把證明展示給其他人」）本身就是一項可證偽性質，而且在這裡確實失敗。論文提出的是，一個單一證明者可以合理地涵蓋所有自然的可證偽性質——也就是密碼學實務中實際出現的那些——但這部分是建立在「自然」這個非正式概念，以及一項明確猜想上的條件性定理。這項保證針對的是可觀察的失敗，而不是每一種哲學上或基於模擬的秘密意義。

有一個具體推論值得點名：這個構造產生了第一批具一致生成證明者的非互動見證隱藏證明——「謎題的證明不會幫助你找出解答」，而且無互動、無設定——這個聽來謙遜的物件，幾十年來一直難以構造。

這不代表什麼

這一節是讓文章保持誠實的地方。

它不表示舊有不可能性定理錯了。這個構造是藉由改變定義來避開它們。

它不提供無互動、無設定且具完美健全性的普通經典零知識。論文明確指出，構造出的證明者沒有模擬器。

它不表示證明無法被重複使用。單一訊息證明仍然可以展示給其他人看；論文沒有保留否認性風格的性質。（具有可信設定的非互動零知識也有相同限制。）

它不表示這是一個可以立即部署的實用協定。這是複雜度理論與密碼學基礎研究。結果依賴證明複雜度和密碼學中的重大假設，而這個構造談的是原則上可能做到什麼。

它不把「哥德爾」變成神奇的安全原語。哥德爾的連結是透過證明系統、最佳證明系統和不完備性的有限類比建立的。可用的直覺不是「不完備性保護你的密碼」。而是：如果規則書無法有效率地證明模擬器不可能存在，那麼需要這項證明的攻擊，就能在安全性定義層次被擋下來。

為什麼仍然有趣

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

這就是這篇論文令人不尋常的地方。它幾乎把公理和規則書當成密碼學資源來處理。通常的不可能性結果說，健全性和模擬之間存在張力。Ilango 的動作，是把這種張力放到證明論的帷幕後：模擬器不存在，但形式系統無法有效率地揭露模擬器不存在這件事。

對讀者而言，令人意外的部分不是它將取代今日的零知識系統。至少不會直接取代。真正意外的是，數理邏輯的一項限制可以被建設性地使用：不只是作為一道牆，也可以作為某種掩護。

證據有多強？

這是一篇定理論文，因此「證據」的含義不同於生物學或天文學論文。問題不是實驗是否重現，而是定義、假設和證明鏈是否支持該主張。

證明是形式化的，論文也明確列出假設。這些假設並非隨意。非互動見證不可區分證明是密碼學中的標準物件，能由數個已建立的假設套件推出。不存在最佳證明系統是證明複雜度中的核心猜想。P = BPP 則是標準的去隨機化信念，只用於更廣泛的可證偽性質定理。

論文也主張，這些假設是恰當的代價，而非任意搭建的腳手架：它證明了一個逆命題，顯示這些假設在本質上是必要的——如果這類構造確實存在，那麼非互動見證不可區分證明必須存在，而且（假設標準的單向函數存在）最佳證明系統就不可能存在。這些假設還是「雙贏」的：反駁其中任何一項，本身都會成為證明複雜度、密碼學或複雜度理論中的里程碑發現。

但由於結果是條件性的，它的可信度也同樣是條件性的。如果那些假設失敗，定理的解讀就會改變。即使假設成立，這項保證也不是完整的經典零知識，而是論文所提出的、經過放寬的證明論版本。

因此，合理的信心是：論文確實建立了一個連貫的條件性可能性結果，這點的信心很高；它的假設描述了我們實際身處的密碼學世界，信心中等；任何立即的實務後果，信心偏低。

為什麼重要

這篇論文開啟了一條原本應該封閉的路。

經典理論說：完整零知識在沒有設定時不能只有一則訊息，也不能具備完美健全性。Ilango 的論文則說：如果我們要求的是那些能在安全性遊戲中測試的零知識後果，並讓安全性定義取決於規則書能否有效率地反駁某件事，那麼許多有用的行為都能被恢復——同時保留單一訊息、無設定和完美健全性。

這不是小小的定義調整，而是思考密碼學保證的一種不同方式。不要只問什麼存在，也要問你的規則書能排除什麼。不要把不可證明性視為哲學上的麻煩，而要把它當成結構使用。

實際世界或許不會在明天改變。但概念地圖改變了。現在有一種形式化意義上的說法：「沒有人能有效率地證明秘密已經洩漏」可能強大到足以恢復我們原本希望從「秘密沒有洩漏」取得的許多基於遊戲的保護。

這就是哥德爾會出現在標題中的原因。

重點摘要

零知識證明讓證明者能使驗證者相信某個陳述為真，卻不透露見證。經典不可能性結果指出，零知識無法在沒有設定的情況下被壓縮成單一訊息，也不能具備完美健全性。Rahul Ilango 的論文沒有反駁這些不可能性，而是定義了較弱的概念，即有效零知識：不要求模擬器真的存在，而要求選定的證明系統——像 ZFC 一樣的形式規則書——無法有效率地證明不存在任何模擬器。在密碼學的重大假設（非互動見證不可區分證明）和證明複雜度的假設（不存在最佳證明系統）下，論文為 NP/SAT 構造了無設定且具完美健全性的單一訊息證明者，逐項達成零知識中可證偽、基於遊戲的安全性後果。一個涵蓋所有「自然」此類性質的單一證明者，是更進一步、部分依賴猜想的延伸；而涵蓋字面上每一項可證偽性質則很可能不可能，因為證明仍可被重複使用。這項結果是理論性且條件性的，不是已部署的原語，但它展示了把證明論上的不可證明性當作密碼學資源的新方式。

務實檢視

**論文展示了什麼：**在既定假設下，可以為 NP/SAT 建立單一訊息、無設定、具完美健全性的證明者；相對於任何選定的證明系統，它們是有效零知識，並能達成經典零知識的每一項可證偽、基於遊戲的後果。

**合理但尚未無條件證明的內容：**所需的證明複雜度和密碼學假設確實成立。它們是嚴肅且經過充分研究的假設——論文也顯示它們不只是充分，而且本質上必要——但終究仍是假設。

**它沒有展示的內容：**無互動、無設定且具完美健全性的經典零知識；可以立即部署的實用系統；證明的否認性或不可重用性；或哥德爾不完備定理本身能保障密碼學。

**主要限制：**這項保證是零知識的放寬版本；最廣泛的版本依賴多項假設；單一通用證明者的主張仍部分建立在猜想上；而且結果主要屬於基礎研究。

**一般讀者應有多大信心？**如果接受這些定義，對這是一項重要的條件性理論結果，信心很高。對假設能否反映現實，信心中等。對立即實務部署，信心偏低。安全的結論是：這篇論文沒有打破零知識的不可能性；它找到了一種新的證明論方式，繞過其中對許多安全性遊戲而言真正重要的部分。