1989 - 零知識證明#

案件摘要#

1985–89 年，Goldwasser、Micali 與 Rackoff 發表《The Knowledge Complexity of Interactive Proof Systems》：定義零知識證明（zero-knowledge proof）——「我證明我知道秘密，但不告訴你秘密本身」。用互動 + 隨機挑戰實現：證明者回答驗證者的隨機問題，騙子會被抓住，但整個過程洩漏零資訊。這是密碼學最反直覺的發明——「證明」與「洩漏」的綁定被解開，成為區塊鏈、隱私保護、認證協議的基礎。

前因 -- 為什麼會有這個案子#

傳統「證明」的本質：你知道的秘密，證明給我看——但傳統證明必然洩漏（你告訴我答案或過程）。1980 年代的困境：

認證的洩漏：密碼認證——你告訴我密碼，我記住了，但你也就「暴露」了密碼（我可能冒充你）
知識的價值：知道秘密本身有價值——證明「知道」不應等於交出秘密

Goldwasser（當時 MIT 博士生，Shamir 的學生）的問題：能否證明「知道」而不洩漏「知道什麼」？ 答案驚人：能——用互動與隨機化。

線索與推理 -- 數學式、程式、理論#

零知識證明的三性質#

定義：語言 \(L\) （如「我知道離散對數 \(x\) 使 \(y = g^x\) 」）的零知識證明系統滿足：

完整性（completeness）：誠實的證明者一定能說服誠實的驗證者
可靠性（soundness）：騙子（不知道秘密）無法說服（機率 \(\le 1/2\) 或可忽略）
零知識性（zero-knowledge）：驗證者除「命題為真」外什麼都學不到——存在模擬器（simulator）能生成與真實互動無法區別的對話錄

零知識的數學化：存在多項式時間模擬器 \(S\) ，使得：

\[ \{S(\text{驗證者的隨機硬幣})\} \approx \{\text{真實互動的對話錄}\} \]

無法區別（indistinguishability，Yao 的計算隨機性概念，見 ../隨機算法/1985-Yao計算隨機性.md）——驗證者拿到的錄音自己就能造，所以沒有學到任何東西。

範例：圖同構的零知識證明#

命題： \(G_1 \cong G_2\) （兩圖同構），證明者知道同構 \(\sigma\) （ \(\sigma(G_1) = G_2\) ）。

協議（每輪）： 1. 證明者：隨機置換 \(\pi\) ，發送 \(H = \pi(G_2)\) （隨機重命名） 2. 驗證者：隨機挑戰 \(b \in \{1, 2\}\) ——「證明 \(H\) 與 \(G_b\) 同構」 3. 證明者：回答 \(\pi\) （ \(b=2\) ）或 \(\pi \circ \sigma^{-1}\) （ \(b=1\) ）

完整性：知道 \(\sigma\) 就能回答兩種挑戰。 可靠性：不知道 \(\sigma\) 的騙子只能事先猜 \(b\) （ \(b=1\) 或 \(2\) ），答錯機率 \(1/2\) —— \(k\) 輪後被抓機率 \(1 - 2^{-k}\) 。 零知識：驗證者看到的每輪 \(H\) 是隨機置換的圖——自己就能生成（模擬器先猜 \(b\) ，再生成 \(H\) ）。

Fiat–Shamir：從互動到非互動#

1986 年 Fiat 與 Shamir 發明去互動化：把驗證者的隨機挑戰換成雜湊：

\[ \text{挑戰 } b = H(\text{承諾} \parallel \text{訊息}) \]

推理：雜湊像「公開的隨機神諭」——證明者無法預測挑戰（雜湊單向），所以可靠性保留；但不需要互動（一次發出證明）。這使零知識證明可以嵌入簽章、區塊鏈——非互動零知識證明（NIZK）的誕生。

程式碼：零知識證明的概念（Schnorr 風格）#

import random, hashlib

P, G = 2**61 - 1, 3

def mod_pow(b, e, n):
    result = 1; b %= n
    while e > 0:
        if e & 1: result = result * b % n
        b = b * b % n; e >>= 1
    return result

# 證明者知道秘密 x（y = G^x mod P）——Schnorr 協議
x = random.getrandbits(40)          # 秘密
y = mod_pow(G, x, P)                # 公開

def prove(y, x, rounds=20):
    """每輪：承諾 -> 挑戰 -> 回應"""
    for _ in range(rounds):
        r = random.getrandbits(40)              # 承諾
        h = mod_pow(G, r, P)
        c = random.randint(0, 1)                # 驗證者隨機挑戰
        s = (r + c * x) % (P - 1)               # 回應
        # 驗證：G^s == h * y^c
        assert mod_pow(G, s, P) == h * mod_pow(y, c, P) % P
        if c == 0:
            pass                                 # 騙子可答（r 本身）
        # 騙子若不知道 x，只能猜 c——猜錯即被發現

def simulate(y):
    """模擬器：生成無法區別的對話錄——驗證者自己就能造！"""
    c = random.randint(0, 1)                    # 先猜挑戰
    s = random.getrandbits(40)
    h = mod_pow(G, s, P) * mod_pow(y, -c, P) % P
    return h, c, s                              # 與真實互動同分佈

random.seed(42)
prove(y, x)
h, c, s = simulate(y)
print(f"模擬器對話錄：h={h % 1000}..., c={c}——零知識性成立")
print("可靠性：騙子被抓機率 1 - 2^-k（k 輪）")

語義安全的框架#

Goldwasser–Micali 1984 的語義安全（semantic security）與零知識證明共同構成證明式安全（provable security）的方法論：

\[ \text{安全性定義（遊戲）} \to \text{反證：若能破解，可構造違反難解假設的演算法} \]

規約：破解密碼系統 ⟹ 解決難解問題（分解、離散對數、DDH）——與 RSA（見 1977-RSA.md）的單向性推理同源，但形式化為遊戲與規約。

結案 -- 後果與影響#

證明與洩漏的解綁：「知道」不再等於「交出」——密碼學最反直覺的發明。
認證的革命：零知識認證（Fiat–Shamir、Schnorr 簽章 1991）——證明身份不暴露密碼。
zk-SNARK/STARK（2013–2018）：非互動、簡潔的零知識證明——zkSync、Zcash 的隱私交易（見 2016-區塊鏈密碼學.md）。
PCP 定理（1990，見 ../計算理論/1990-PCP定理.md）：可驗證的機率式證明——零知識的理論極致。
MPC：多方安全計算（Yao 1982、GMW 1987）與零知識共同構成「隱私計算」的理論基礎。
圖靈獎：Goldwasser 與 Micali 獲 2012 年圖靈獎（機率式加密與零知識）。

關鍵人物與文獻#

Shafi Goldwasser（1958–）：MIT/UC Berkeley；圖靈獎 2012
Silvio Micali（1954–）：MIT；圖靈獎 2012
Charles Rackoff：共同作者
Goldwasser, Micali, Rackoff: The Knowledge Complexity of Interactive Proof Systems (1989, SIAM J. Comput.)
Fiat & Shamir：去互動化 (1986)
Schnorr：簽章協議 (1991)
Ben-Sasson et al.：zk-SNARK/STARK (2013–2018)
交叉參照：1976-DiffieHellman金鑰交換.md、../計算理論/1990-PCP定理.md、../隨機算法/1985-Yao計算隨機性.md、2016-區塊鏈密碼學.md