1985 - 零知識證明（Goldwasser–Micali 的密碼學革命）#

案件摘要#

1985 年，Shafi Goldwasser 與 Silvio Micali 在 STOC 發表 Probabilistic Encryption（與 Rivest、Blum 等人的互動證明工作同期），提出了一個顛覆直覺的概念：

\[ \boxed{\text{「我可以證明某件事為真，卻不透露任何其他資訊」}} \]

這就是零知識證明（zero-knowledge proof）： - 證明者（prover）知道祕密（如密碼、私鑰）； - 驗證者（verifier）被完全說服「祕密存在」； - 但驗證者學不到祕密本身——連一個位元都學不到！

\[ \text{說服力} + \text{零洩漏} = \text{零知識證明}. \]

同年他們還提出機率加密（probabilistic encryption）—— 加密時擲骰子，同一明文每次加密結果都不同，徹底治好了確定性加密（如 RSA 裸用）的字典攻擊弱點。 這對搭檔於 2012 年共同獲得圖靈獎—— 零知識證明是現代密碼學與區塊鏈的「隱形基石」。

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

公開金鑰密碼學的弱點（1977 RSA）： RSA 公開金鑰密碼學（見 2002-RSA公開金鑰.md）讓任何人都能加密，但 RSA 是確定性加密：同一明文 \(m\) 永遠加密成同一密文 \(c = m^e \bmod N\) 。

\[ \text{確定性加密} \Rightarrow \text{攻擊者可建立「明文-密文字典」逐條比對}. \]

若明文空間很小（如「買/賣/持有」三種訊息），攻擊者加密所有候選再比對—— 密碼學在理論上被攻破了（儘管分解大整數仍然困難）。 - Diffie–Hellman 的啟發（1976）： Diffie 與 Hellman 在《密碼學的新方向》提出機率與互動可以進入密碼學—— 金鑰交換本身就是一個互動協定。但他們沒有給出嚴格的定義：「什麼叫做『安全』？」「什麼叫做『洩漏』？」—— 這些問題懸而未決，等著 Goldwasser 與 Micali 來破解。 - 互動證明與 NP 完全（1971 Cook）：傳統的「證明」是一份靜態的文件（見 1971-庫克NP完全.md）： NP 問題的解可以被檢驗，但檢驗過程會看光整份證明。

\[ \text{靜態證明（1971）} \xrightarrow{\text{Goldwasser–Micali（1985）}} \text{互動證明（interative proof）}. \]

Goldwasser 與 Micali 的洞察：讓證明變成一場對話—— 驗證者拋出隨機挑戰，證明者即時回應；對話可以「只透露結論，不透露內容」。 - Shannon 資訊理論的尺度（1948）： Shannon 用位元量化資訊（見 1948-香農資訊理論.md）—— 這讓「零洩漏」可以被嚴格定義：驗證者所能計算的任何量，不看互動也能自己算出來（模擬器思想）。

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

第一條線索：互動證明系統#

互動證明系統 = 證明者 \(P\) 與驗證者 \(V\) 的隨機對話： - 輸入：公共命題 \(x\) （如「我知道 \(y\) 的離散對數」）； - \(P\) 與 \(V\) 交換多輪訊息（ \(V\) 用隨機挑戰）； - \(V\) 最後輸出「接受」或「拒絕」。

\[ \text{靜態證明} \xrightarrow{} \text{互動證明} \xrightarrow{} \text{零知識證明（對話還能零洩漏）}. \]

第二條線索：零知識的三性質#

定義（Goldwasser–Micali, 1985）：零知識證明必須同時滿足： 1. 完備性（completeness）：若命題為真且雙方誠實，驗證者必然接受； 2. 可靠性（soundness）：若命題為假，任何冒充的證明者都幾乎必然被拒； 3. 零知識性（zero-knowledge）：驗證者互動後學到的一切，都存在一個模擬器（simulator）不看祕密就能產生——

\[ \boxed{\text{模擬器思想：互動紀錄 ≡ 模擬紀錄（故互動不洩漏任何資訊）}} \]

模擬器是整個定義的靈魂——它把「洩漏」從模糊的直覺變成可證明的數學命題：既然模擬器能憑空造出一模一樣的對話，那對話裡就不可能藏著祕密。

第三條線索：Schnorr 協議——離散對數的零知識證明#

設定： \(p\) 為大質數， \(g\) 為模 \(p\) 的生成元；證明者知道私鑰 \(x\) ，公鑰為：

\[ y = g^x \bmod p \quad\text{（離散對數難題：由 } y \text{ 反推 } x \text{ 不可行）} \]

單回合協議（承諾–挑戰–回應）： 1. 承諾：證明者選隨機數 \(r\) ，送出

\[ t = g^r \bmod p \]

挑戰：驗證者送隨機位元/隨機數 \(c\) ；
回應：證明者送出

\[ s = r + cx \bmod q \]

驗證：驗證者檢查

\[ g^s = t \cdot y^c \pmod p \]

為何成立： - 完備性： \(g^s = g^{r+cx} = g^r \cdot (g^x)^c = t \cdot y^c\) ✓ - 零知識性：驗證者只看到 \((t, c, s)\) ——而模擬器可先選 \(c, s\) 再算 \(t = g^s \cdot y^{-c}\) ，產生分布完全相同的紀錄（ \(r\) 被 \(c\) 的隨機性完美遮蔽）； - 可靠性：不知道 \(x\) 的冒充者只能瞎猜回應—— 每回合被抓出的機率為 \(1 - 1/q\) ，重複 \(n\) 回合後

\[ \Pr(\text{騙過 } n \text{ 回合}) = \left(\frac{1}{q}\right)^n \approx 0. \]

\[ \boxed{\text{承諾（藏住 } r\text{）} + \text{隨機挑戰 } c + \text{回應 } s = \text{零知識的身分證明}} \]

Python：Schnorr 零知識證明的模擬#

# Schnorr 零知識證明：真證明者通過驗證，冒充者被抓出
import random

random.seed(2026)
p = 1019          # 大質數（示範用小值）
g = 2             # 模 p 的生成元
q = p - 1         # g 的階

x = random.randrange(1, q)            # 私鑰（證明者保密）
y = pow(g, x, p)                      # 公鑰 y = g^x mod p
print(f"公開參數：p={p}, g={g}（g 的階 q=p-1={q}）")
print(f"私鑰 x={x}（證明者保密），公鑰 y = g^x mod p = {y}\n")

def schnorr(y, know_x, rounds=20):
    """know_x=True：誠實證明者；False：不知道 x 的冒充者"""
    ok = 0
    for i in range(rounds):
        if know_x:
            r = random.randrange(1, q)          # 承諾用的隨機數
            t = pow(g, r, p)                    # 承諾 t = g^r mod p
            c = random.randrange(0, q)          # 挑戰 c（驗證者擲）
            s = (r + c * x) % q                 # 回應 s = r + cx mod q
        else:
            t = random.randrange(1, q)          # 冒充者：瞎選承諾
            c = random.randrange(0, q)
            s = random.randrange(0, q)          # 冒充者：瞎猜回應
        if pow(g, s, p) == (t * pow(y, c, p)) % p:   # 驗證 g^s = t·y^c
            ok += 1
    return ok

ok1 = schnorr(y, True)
print(f"真證明者（知道 x）：20 回合通過 {ok1}/20")
r = random.randrange(1, q); t = pow(g, r, p); c = random.randrange(0, q)
s = (r + c * x) % q
print(f"  單回合示範：承諾 t=g^r mod p = {t}")
print(f"              挑戰 c = {c}")
print(f"              回應 s=r+cx mod q = {s}")
print(f"              驗證 g^s mod p = {pow(g, s, p)} == t·y^c mod p = {(t*pow(y, c, p)) % p} ✓")

ok2 = schnorr(y, False)
print(f"\n冒充者（不知道 x）：20 回合通過 {ok2}/20，被抓出 {20-ok2}/20")
print("  冒充者只能瞎猜 s → 每回合被逮住的機率 1-1/q = 1-1/1018 ≈ 99.9%")
print("  20 回合全騙過的機率 (1/q)^20 ≈ 10^-60 → 零知識且可靠")

輸出：

公開參數：p=1019, g=2（g 的階 q=p-1=1018）
私鑰 x=122（證明者保密），公鑰 y = g^x mod p = 793

真證明者（知道 x）：20 回合通過 20/20
  單回合示範：承諾 t=g^r mod p = 812
              挑戰 c = 695
              回應 s=r+cx mod q = 799
              驗證 g^s mod p = 993 == t·y^c mod p = 993 ✓

冒充者（不知道 x）：20 回合通過 0/20，被抓出 20/20
  冒充者只能瞎猜 s → 每回合被逮住的機率 1-1/q = 1-1/1018 ≈ 99.9%
  20 回合全騙過的機率 (1/q)^20 ≈ 10^-60 → 零知識且可靠

結案 -- 後果與影響#

機率加密（1985）： Goldwasser–Micali 提出第一個可證明安全的機率加密：

\[ \text{加密} = \text{明文} + \text{隨機數（擲骰子）} \Rightarrow \text{同一明文，密文每次不同} \]

他們的方案用二次剩餘（Quadratic Residuosity 假設）：密文 \(c = m \cdot r^2 \bmod N\) （ \(r\) 為隨機數）；
這確立了密碼學的新範式：「安全」必須用機率與規約嚴格定義—— 今日一切密碼標準（TLS、AES 模式）都遵循「隨機化加密」的原則。
IP = PSPACE（1992）： Adi Shamir 證明互動證明系統的能力正好等於 PSPACE：

\[ \boxed{\text{IP} = \text{PSPACE（Shamir, 1992）}} \]

互動 + 隨機性 = 驚人的計算能力——連 PSPACE 完全問題（如國際象棋般龐大的博弈）都能被互動證明！這是計算複雜度理論的里程碑，源頭正是 Goldwasser–Micali 的 1985。 - 從零知識到 zk-SNARK（2013–）：後續研究把零知識證明變成簡潔的非互動證明：

\[ \text{零知識（1985）} \xrightarrow{} \text{zk-SNARK} \xrightarrow{} \text{區塊鏈隱私（Zcash、以太坊）} \]

Zcash（2016）：用 zk-SNARK 證明「交易合法」而隱藏金額與收付方；
以太坊：zk-rollup 把大量交易壓成一個小證明——擴容與隱私兼得；
計算量數百萬倍的證明，驗證只需幾毫秒。
身分驗證的應用： Schnorr 協議（1989）成為零知識身分驗證的標準：證明「我知道私鑰」而永不送出私鑰—— 相較於傳統密碼（伺服器必須儲存可比對的密碼），零知識無懈可擊。今日的 FIDO2 / WebAuthn（免密碼登入）正是這個思想的工程實現。
圖靈獎（2012）： Goldwasser 與 Micali 獲 2012 年圖靈獎：

\[ \boxed{\text{「革新了密碼學——為它打下可證明安全的數學基礎」}} \]

Goldwasser 是圖靈獎史上第一位女性得主（她現任教於 MIT 與 Weizmann 研究所）。密碼學自 Shannon（1948）與 Diffie–Hellman（1976）之後，由這對搭檔完成從藝術到科學的蛻變。 - 歷史定位：零知識證明把「證明」從文件變成對話、把「安全」從直覺變成定理——

\[ \text{互動證明（1985）} \xrightarrow{} \text{IP=PSPACE（1992）} \xrightarrow{} \text{zk-SNARK（2013）} \xrightarrow{} \text{區塊鏈隱私（2016）}. \]

一切從那場「不透露祕密的對話」開始。

關鍵人物與文獻#

S. Goldwasser：Probabilistic Encryption（1985，與 Micali）；零知識三性質與模擬器定義；2012 圖靈獎（首位女性得主之一）；圖靈講座 The Graph Isomorphism Problem（2015）。
S. Micali：機率加密與互動證明（1985）；zk-SNARK 之前身 CS proofs（1994，與 Goldwasser 等）；2012 圖靈獎。
A. Shamir：IP = PSPACE（1992）——互動證明能力的極限。
C. Schnorr：Schnorr 協議（1989）——離散對數的零知識身分驗證。
W. Diffie 與 M. Hellman：《密碼學的新方向》（1976）——機率與互動進入密碼學。
相關案件：2002-RSA公開金鑰.md、1971-庫克NP完全.md、2000-姚期智量子計算.md、1948-香農資訊理論.md。