1985 - 互動式證明系統：Arthur–Merlin 與 IP#

案件摘要#

1985 年，Babai 提出「Arthur–Merlin 遊戲」，Goldwasser、Micali 與 Rackoff 同年提出互動式證明 IP。證明不再是靜態的一張紙，而是驗證者與證明者之間的隨機對話——由此誕生了零知識證明，並在 1992 年 culminate 於驚人的 \(\text{IP} = \text{PSPACE}\) 。

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

傳統 NP 證明：證明者交出一張靜態證書，驗證者多項式時間檢查。但這有兩個缺陷：
證書可能很長、洩露一切資訊（密碼學上不可接受）。
驗證是確定性的，毫無彈性。
1970 年代末密碼學革命（Diffie–Hellman 1976、RSA 1978）迫切需要「證明我知道秘密但不告訴你秘密」的技術。
Goldwasser 與 Micali（Berkeley 博士生）思考「知識」的定義；Babai（芝加哥大學）則從「隨機性加速驗證」的角度獨立切入。
案件動機：把證明變成遊戲——隨機性能否讓驗證更強？

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

互動式證明系統的定義#

一對機器 \((P, V)\) ：證明者 \(P\) （計算能力無限）與驗證者 \(V\) （多項式時間、機率式）進行 \(k\) 輪訊息交換。定義：

\[ L \in \text{IP}(k) \iff \exists (P,V):\quad \begin{cases} x \in L \implies \Pr[V \text{ 接受}] \ge \frac{2}{3} & (\text{完備性})\\ x \notin L \implies \forall P^*,\ \Pr[V^* \text{ 接受}] \le \frac{1}{3} & (\text{健全性}) \end{cases} \]

\[ \text{IP} = \bigcup_{k} \text{IP}(k) = \text{IP}(\text{poly}(n)) \]

Arthur–Merlin 遊戲（Babai 1985）#

Babai 的版本：隨機位元公開擲出（Arthur 的硬币 Merlin 也看得到）——「公開擲幣系統」。記 AM： - Arthur（驗證者）：先丟隨機位元 \(r\) ，問 Merlin 問題。 - Merlin（證明者）：無限計算力，回答答案 \(a\) 。 - Arthur 用多項式時間檢查 \((x, r, a)\) 。

Babai 證明 \(\text{MA} \subseteq \text{AM}\) 等包含關係，並猜測隨機性可以極大化驗證能力。Goldwasser–Sipser（1986）證明私密擲幣與公開擲幣等價： \(\text{IP}(k) = \text{AM}(k+2)\) 的廣義版本——兩條路殊途同歸。

零知識證明（zero-knowledge, GMR 1985）#

GMR 的核心定義：一個互動協議是零知識的，若驗證者從互動中「學不到任何東西」——形式化為：存在模擬器 \(S\) ，能在多項式時間內產生與真實互動統計上不可區分的 transcript：

\[ \forall V^*,\quad \{S(x)\} \approx \{\text{View}_{V^*}(P, V, x)\} \]

3SAT 的零知識協議範例（3-著色法）： 1. 指定 3SAT 公式 \(\phi\) 對應的圖 \(G_\phi\) （變數-文字圖）， \(\phi\) 可滿足 ⟺ \(G_\phi\) 可 3-著色。 2. 證明者 P 拿著合法 3-著色 \(c: V \to \{1,2,3\}\) ，隨機置換顏色後，把每個頂點的顏色鎖進密碼箱（承諾承諾 commitment）交給 V。 3. V 隨機選一條邊 \((u,v)\) ，P 只打開這兩個箱子。 4. V 檢查 \(c(u) \neq c(v)\) 。 5. 重複 \(n\) 輪。

import random

def zk_3coloring_round(colors, edges):
    # 承諾階段：隨機置換顏色後「鎖箱」
    perm = {1: random.randint(1,3), 2: random.randint(1,3), 3: random.randint(1,3)}
    while len(set(perm.values())) < 3:
        perm = {c: random.randint(1,3) for c in (1,2,3)}
    boxes = {v: commit(perm[colors[v]]) for v in colors}   # 承諾函數（模擬）
    # 挑戰階段：驗證者隨機挑一條邊
    u, w = random.choice(edges)
    revealed_u = open_box(boxes[u])   # 只有這兩個箱子被打開
    revealed_w = open_box(boxes[w])
    return revealed_u != revealed_w   # 通過 ⟺ 兩頂點異色

# 重複 n 輪：作弊者每輪被逮住的機率 ≥ 1/|E|，n 輪後作弊成功率 ≤ (1-1/|E|)^n

V 學到了什麼？只看到「兩個隨機顏色不同」——這個資訊 V 自己也能生成。零知識。

Shamir 1992： \(\text{IP} = \text{PSPACE}\)#

1992 年 Shamir 證明（基於 Lund–Fortnow–Karloff–Nisan 的算術化技術）：

\[ \text{IP} = \text{PSPACE} \]

驚人結論：隨機互動讓驗證能力從 NP 一路暴增至 PSPACE——互動 + 隨機性 = 極大的驗證力量。注意此證明不相對化（繞過了 1975 年 BGS 的障礙），是相對化障礙之後第一批「新式武器」。

結案 -- 後果與影響#

密碼學的基石：GMR 的零知識證明成為現代密碼學的支柱——身份驗證協議（Fiat–Shamir 1986）、安全多方計算、門檻簽名。Goldwasser 與 Micali 因此獲 2012 年圖靈獎。
區塊鏈的影響：
zk-SNARK / zk-STARK：零知識的簡潔非互動證明，用於 Zcash 隱私交易、以太坊 Rollup 擴容。
「可驗證計算」：把繁重計算外包，只驗證短短的證明——直接繼承 IP 的精神。
複雜度理論的重塑： \(\text{IP} = \text{PSPACE}\) 開啟了「算術化」技術，直接鋪路 PCP 定理（1990s）與 \(\text{MIP} = \text{NEXP}\) （多證明者版本）。
哲學衝擊：「什麼是證明」被改寫——證明可以是機率性的、互動的、洩露最少的。

關鍵人物與文獻#

László Babai："Trading Group Theory for Randomness", STOC 1985（Arthur–Merlin 遊戲）。
Shafi Goldwasser、Silvio Micali、Charles Rackoff："The Knowledge Complexity of Interactive Proof-Systems", STOC 1985（IP 與零知識）。
Shafi Goldwasser、Michael Sipser（1986）：私密/公開擲幣等價性。
Adi Shamir："IP = PSPACE", JACM 39(3):577–595, 1992。
Lund、Fortnow、Karloff、Nisan（1990/1992）：算術化技術（代數方法）。
Fiat、Shamir（1986）：Fiat–Shamir 轉換，互動零知識 → 非互動簽名。