2012 Shafi Goldwasser & Silvio Micali —— 零知識證明：證明你會，卻不說答案#

「你如何證明自己知道秘密，卻一個字都不洩漏？這個謎題 在 1985 年被兩位伯克利師生解開，從此『證明』一詞的 定義被改寫。」

案件檔案#

前因#

1980s，姚期智（2000 案）與 Blum（1995 案）已定義 「多項式時間攻擊者的不可辨識」。下一個謎題： 證明本身也會洩密——你證明 3-coloring 有解的同時， 可能被迫交出著色法。Goldwasser 與 Micali 在 Berkeley 師從 Blum，把這個不適感變成定理。

線索與推理#

線索一：互動證明系統（IP，1985 GMR 論文）#

證明者 P（全知）↔ 驗證者 V（多項式時間、可擲骰）
性質：
  完備性：命題真 → 誠實 P 必能使 V 接受
  健全性：命題假 → 任何作弊 P 極難騙過 V
  零知識：V 只學到「命題為真」，別無他物
          （形式化：V 所見可由模擬器單獨重現）

「零知識」的定義是模擬式的：若驗證者自己就能 模擬出所見的 transcript，那他什麼也沒學到——定義 本身就是偵探式推理。

線索二：Graph 3-coloring 的零知識協議（1986）#

1. P 隨機置換顏色，對每個頂點的顏色做位元承諾
2. V 隨機挑一條邊，P 只打開這條邊兩端：顏色必相異
3. 重複 n 輪；每輪 P 重新隨機置換
V 檢查了所有邊的局部一致性，卻沒得到整體著色

承諾 + 挑戰 + 隨機化的三拍結構，成為一切 ZK 協議 的節奏。深層結果：IP = PSPACE（Shamir 1992）—— 互動把可證明的範圍擴到驚人的廣度。

線索三：GM 加密（1982）#

第一個語義安全的公鑰加密：

c = (g^r mod p, m · h^r mod p)   （Goldwasser–Micali 原版為二次剩餘）
隨機化 r → 同一明文每次密文不同 → 敵人無法逐位元學習

隨機性是安全的必需品——與 Yao 的偽隨機理論（2000 案） 合流，確立「可證明安全」的證明範式（歸約到困難問題）。

線索四：複雜度側翼#

GM 亦定義多證明者互動（MIP → PCP 定理的通道）， 直接連到近似性的不可證明界——密碼學回饋了純複雜度理論。

理論評析#

本案的雙重革命：

「隨機性在驗證者手中」是健全性的來源；「隨機性 在證明者手中」是零知識的來源——同一枚硬幣的兩面。

後果#

• 區塊鏈的 zk-SNARK/zk-Rollup（隱私交易、擴容） 是零知識的 2020s 大爆發。
• 身分驗證協議（不送密碼、只送證明）成為標準方向。
• Goldwasser 亦是首位獲圖靈獎的女性理論家；Micali 另創 Aland（Algorand）區塊鏈。

關聯案件#

→ 2000-Andrew-Yao與偽隨機性及複雜度理論、2002-Rivest-Shamir-Adleman與RSA公鑰加密、1995-Manuel-Blum與計算不可辨識及密碼學