零知識協議

密碼學中，**零知識證明**（英語：zero-knowledge proof）或**零知識協議**（zero-knowledge protocol）是一方（證明者）向另一方（檢驗者）證明某命題的方法，特點是過程中除「該命題為真」之事外，不泄露任何資訊。因此，可理解成「零洩密證明」。例如，欲向人證明自己擁有某情報，則直接公開該情報即可，但如此則會將該細節亦一併泄露；零知識證明的精粹在於，如何證明自己擁有該情報而不必透露情報內容。這也是零知識證明的難點。

若該命題的證明，需要知悉某秘密方能作出，則檢驗者單憑目睹證明，而未獲悉該秘密，仍無法向第三方證明該命題（即單單轉述不足以證明）。待證的命題中，必定包含證明者宣稱自己知道該秘密，但過程中不能傳達該秘密本身。否則，協議完結時，已給予檢驗者有關命題的額外的資訊。此類「知識的零知識證明」是零知識證明的特例，其中待證命題僅有「證明者知道某事」。

交互式零知識證明中，需要各方互動，靠通訊過程證明某方具備某知識，而另一方檢驗該證明是否成立。

也有某種非交互式零知識證明，但證明之所以成立，依賴計算假設（典型假設是理想的密碼雜湊函數）。

## 生活範例

以下有一個熟知的故事，總結零知識證明的若干重要概念。故事最早由 Jean-Jacques Quisquater 及同事發表於〈如何向貴子弟解釋零知識協議〉。設有小靜（證明者）和阿嚴（驗證者）兩人。

故事中，小靜發現洞穴中某扇魔法門的開門暗號。洞穴呈環形，入口在一側，對側則有魔法門隔斷。阿嚴想知小靜是否已知該暗號，但小靜很注重隱私，不希望泄露暗號予阿嚴，也不想全世界知道她有暗號之事。

兩人分別將入口左右兩條通道標示為 A 路、B 路。首先，阿嚴在洞口外，待小靜進入洞內。小靜自行選擇行 A 路或 B 路，但阿嚴不准窺視小靜所選為何。然後，阿嚴行入洞穴，均勻隨機喊出 A 路或 B 路，表明希望小靜由該方向返回。假若小靜確實知道暗號，則很易達成，因為即使起初所選不是同一條路，她也可以開門通過，從另一條路返回。

然而，若她其實不知道暗號，則祗有一半概率能從阿嚴所選的方向返回，因為阿嚴隨機選 A 路和 B 路，恰有一半機會選中起初小靜進入的方向。若兩人重複以上過程，比如連續 20 次，則小靜靠運氣全部碰巧從正確方向返回的概率，將會很小（約一百萬分之一）。

所以，若小靜連續多次從阿嚴所選的方向返回，則阿嚴可以推斷，小靜很可能知道暗號。

以下考慮第三方的觀點。即使假設阿嚴佩戴隱蔽的鏡頭，錄影所見的整個過程，鏡頭所見亦只有阿嚴喊「A！」小靜從 A 路返回；或阿嚴喊「B！」小靜從 B 路返回。此種片段極易由兩人共謀偽造（祗需小靜與阿嚴事前商討多次驗證中阿嚴將選該串 A、B 的次序），從而對第三方而言，不具說服力，即阿嚴無法藉此向第三方證明小靜知道暗號。事實上，即使錄影換成現場在阿嚴身旁監視亦同，因為兩人可能一早已協調綵排好。

但是，若阿嚴在鏡頭前擲硬幣，然後按該硬幣喊 A 或 B，則協議不再零知識。該段錄影可能足以說服第三方，兩人無法偽造，因為阿嚴難以準確擲出預定的 AB 次序。於是，雖然證明過程沒有泄露暗號予阿嚴，但是阿嚴可藉此說服世人，證明小靜知道暗號，與小靜起初的意欲完全相反。不過，數碼的密碼學中，「擲硬幣」以偽隨機數生成器實作，類似於一枚結果已預定好的硬幣，但該結果（由其隨機種子決定）僅有硬幣主人知道。若阿嚴的硬幣實際是以此法運作，則協議又回復為零知識協議，因為兩人又有可能共同偽造「實驗」結果，所以使用偽隨機數生成器與擲真硬幣不同，前者不會向世人泄露小靜知道暗號。

還有另一種做法，小靜以獨一次實驗已可向阿嚴證明自己知道暗號，而不泄漏。方法是，兩人一同走入洞口，然後阿嚴目送小靜沿 A 路走，沒有原路折返，但從 B 路返回。如此，小靜必然已向阿嚴證明自己知道暗號，而沒有告知阿嚴暗號。不過此種證明亦非零知識：若第三方觀察到過程，或阿嚴有錄影，則該證明對第三方具說服力。換言之，小靜無法宣稱自己與阿嚴串通，所以無法向第三方說該證明無效。如此，小靜無法控制何人得知她擁有暗號之事。

 

## 定義

零知識證明要具備下列三種性質：

**完備（complete）**
: 若所要證之事為真，則誠實（意即依協議行事）的證明者能說服誠實驗證者。

**健全（sound）**
: 若命題為假，則作弊證明者僅得極小機會能說服誠實驗證者該事為真。

**零知識（zero-knowledge）**
: 若命題為真，則驗證者除此之外，過程中沒有得悉任何其他資訊。換言之，僅知命題為真（而不知祕密本身）已足以「想像」出一個交互的情境，其中證明者的確知道該秘密。此性質能嚴格定義為：每個驗證者皆有相應的模擬器，輸入欲證事實時，無需求助於證明者，已可輸出一套通訊謄本，看似誠實驗證者與證明者的通訊記錄。

前兩種性質，更廣義的交互式證明系統亦應具備。第三種性質使該交互證明稱為零知識。

零知識證明不算數學證明，因為尚允許有很少（但非零）概率，令作弊證明者能向驗證者「證明」假命題。該概率稱為可靠度誤差（soundness error）。換言之，零知識證明是概率「證明」，而非決定性。不過，也有技巧將可靠度誤差壓到忽略不計。

零知識的嚴格定義，需要抽象計算模型，如常見的圖靈機。設 $P$ 、 $V$ 、 $S$ 為三部圖靈機。某語言 $L$ 的交互式證明系統 $(P,V)$ 為**零知識**，意思是對任意概率多項式時間（PPT）驗證者 ${\widehat {V}}$ ，皆有 PPT 模擬器 $S$ 使得：

　
: $\forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\widehat {V}}\left[P(x)\leftrightarrow {\widehat {V}}(x,z)\right]=S(x,z)$

其中 $\operatorname {View} _{\widehat {V}}\left[P(x)\leftrightarrow {\widehat {V}}(x,z)\right]$ 是 $P(x)$ 與 ${\widehat {V}}(x,z)$ 間交互的全記錄。證明者 $P$ 通常假設具無限計算能力（實踐上，常為機率圖靈機）。直觀理解，某交互證明系 $(P,V)$ 為零知識，即對任意驗證者 ${\widehat {V}}$ ，皆存在某高效模擬器 $S$ （視乎 ${\widehat {V}}$ 而定），給定任何輸入，可以重現 $P$ 與 ${\widehat {V}}$ 間的對話。定義中的輔助串 $z$ ，是用作放置任何「前備知識」（包括預知 ${\widehat {V}}$ 運行時擲得的硬幣結果）。定義推出， ${\widehat {V}}$ 不能利用預知串 $z$ 從與 $P$ 的對話中發掘出資訊，因為若給予 $S$ 該串，則也同樣可以重現 ${\widehat {V}}$ 與 $P$ 間的對話。

以上為完美零知識的定義。若將定義中，驗證者 ${\widehat {V}}$ 的視角（view）與模擬相等之要求，改為僅要求計算上無法分辨，則得到**計算零知識**的定義。

## 計算範例

### 離散對數

前段概念適用於較實際的密碼學場景。設小靜欲向阿嚴證明，自己知道某群某指定元素的離散對數。

例如，給定數 $y$ 、質數 $p$ 、生成元 $g$ ，小靜希望證明自己知道某數 $x$ 使 $g^{x}{\bmod {p}}=y$ ，而不泄漏 $x$ 。事實上，知曉 $x$ 之事，本身可用作身份證明，即小靜可藉此證明該 $y$ 值是由她先暗中選某隨機值 $x$ ，再計算 $y=g^{x}{\bmod {p}}$ ，公諸所有潛在的驗證者。如此，若某人證明自己知道 $x$ ，則相當於證明自己即小靜，因為學者相信離散對數很難計算，即其他人無法從 $y$ 倒推出 $x$ 值。

證明協議如下：每輪，小靜預備隨機數 $r$ ，計算 $C=g^{r}{\bmod {p}}$ ，將該值傳予阿嚴。收到 $C$ 後，阿嚴隨機請求下列兩者之一：小靜公開 $r$ 值，或 $(x+r){\bmod {(p-1)}}$ 值。單獨看任何一個值，其分佈皆是均勻隨機，所以協議每輪皆不泄露任何機密。

阿嚴可以驗證所得回應。若問 $r$ ，則可以計算 $g^{r}{\bmod {p}}$ ，檢查是否等於 $C$ 。若問 $(x+r){\bmod {(p-1)}}$ ，則可以計算 $g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}$ ，而該值應當等於 $C\cdot y{\bmod {p}}$ ，所以亦驗證 $C$ 值是否滿足該條件。若小靜確實知道 $x$ 值，理應很易回答阿嚴的任一條問題。

若小靜預知阿嚴採用何種盤問，則很易作弊，在不知 $x$ 的情況下，向阿嚴假裝自己知道 $x$ ：若她知道阿嚴將要問 $r$ ，則如常繼續，選 $r$ ，計算 $C=g^{r}{\bmod {p}}$ ，告知阿嚴 $C$ 值；她可以答出 $r$ 值。另一方面，若她知道阿嚴將問 $(x+r){\bmod {(p-1)}}$ ，則取隨機一個 $r'$ 值，計算 $C'=g^{r'}\cdot \left(g^{x}\right)^{-1}{\bmod {p}}$ ，然後發送 $C'$ 值予阿嚴（阿嚴會以為該值為 $C$ 值）。當阿嚴要求公開 $(x+r){\bmod {(p-1)}}$ 值時，小靜公開 $r'$ ，但這足以讓阿嚴驗證結果，因為他計算的值實為 $g^{r'}{\bmod {p}}$ ，是等於 $C'\cdot y$ ，因為 $C'$ 正是小靜一早乘上 $y$ 的逆元而計出。

然而，若有某輪驗證中，阿嚴的問題與小靜預估的有出入，則小靜無法計算出要答的結果（假定該群的離散對數問題難解）。若她揀選 $r$ 並公開 $C=g^{r}{\bmod {p}}$ ，則無法作弊給出服眾的 $(x+r){\bmod {(p-1)}}$ 值來通過阿嚴的檢查，因為不知道 $x$ 。又若她揀選 $r'$ 值，偽裝成 $(x+r){\bmod {(p-1)}}$ ，則要回答公開值的離散對數，但她無法回答，因為該值是由已知值乘出，而非某已知值以 $g$ 為底的冪，所以她不能計出其離散對數

所以，作弊的證明者僅得 $1/2$ 概率通過某輪驗證。重複足夠多輪，成功作弊的概率可壓到任意小。

#### 撮要

小靜要證知道 $x$ 值（如其密碼）。

1. 小靜與阿嚴約定某質數 $p$ ，及域 $\mathbb {Z} /p\mathbb {Z} $ 的乘法生成元 $g$ 。
2. 小靜計算 $y=g^{x}{\bmod {p}}$ ，傳送予阿嚴。
3. 重複以下步驟若干次：
  1. 小靜選某個均勻隨機數 $r\in U[0,p-2]$ ，計算 $C=g^{r}{\bmod {p}}$ ，傳送 $C$ 予阿嚴。
  2. 阿嚴問小靜 $(x+r){\bmod {(p-1)}}$ 或 $r$ ，二選其一。若問前者，則阿嚴驗證 $(C\cdot y){\bmod {p}}\equiv g^{(x+r){\bmod {(p-1)}}}{\bmod {p}}$ 。若問後者，則他驗證 $C\equiv g^{r}{\bmod {p}}$ 。

 $(x+r){\bmod {(}}p-1)$ 之值，可視為 $x{\bmod {(}}p-1)$ 的加密。若 $r$ 確為隨機，在 $0$ 至 $(p-2)$ 間均勻分佈，則 $(x+r){\bmod {(p-1)}}$ 也同樣均勻分佈，所以不會泄漏任何關於 $x$ 的資訊（見一次性密碼本）。

### 大圖的哈密頓環

下列方案是曼紐爾・布盧姆提出。

此場境中，小靜知道某大圖 $G$ 的哈密頓環。阿嚴知道 $G$ 但不知該環（比如說小靜將該圖列印給阿嚴）。一般相信，找大圖的哈密頓環，在計算上並不可行，因為相應的決定問題已證為 NP 完全。小靜欲證自己知道該環，但不想泄漏出去，原因可能是阿嚴打算向小靜買，但付款前希望先驗證小靜知道；也可能是全世界衹得小靜知道該環，所以小靜向阿嚴證明此事，是為向阿嚴核實自己身份。

小靜為證明自己知道哈密頓環，與阿嚴作若干輪驗證。每輪中：

* 一開始，小靜預備圖 $H$ ，是與 $G$ 同構（即 $H$ 與 $G$ 一樣，但頂點的標籤不同）。若小靜知道 $G$ 的哈密頓環，則因為 $H$ 與 $G$ 間的同構由她揀選，她很易找到 $H$ 中對應的哈密頓環。
* 小靜秘諾 $H$ 。此處可選任意密碼學秘諾機制，甚或直接將 $H$ 的頂點編號，然後對 $H$ 的每條邊，將兩端編號寫在小紙片上，反轉蓋在檯面。總之，秘諾目的是使小靜此後無法竄改 $H$ ，但同時不讓阿嚴提早知道 $H$ 的資訊。
* 阿嚴隨機問小靜以下兩事之一：給出 $H$ 與 $G$ 間的同構（見圖同構問題）；或給出 $H$ 的哈密頓環。
* 若問兩圖的同構，則小靜先展示 $H$ （將檯面全部紙翻開），並給出 $G$ 頂點與 $H$ 頂點的對應表。阿嚴可以驗證該對應關係是否滿足圖同構的條件。
* 若問哈密頓環，則小靜衹翻開在 $H$ 的哈密頓環上的紙片。如此，阿嚴已可驗證 $H$ 有哈頓頓環。

秘諾一步必須使阿嚴在第二種情況能驗證該環確實由 $H$ 的邊構成。一種做法是，逐條邊分別秘諾。

#### 完備

若小靜確知 $G$ 中的哈密頓環，則阿嚴詢問同構時，她很易回答（該同構為她所選），而阿嚴問 $H$ 中的哈密頓環時，她同樣很易回答（ $G$ 有哈密頓環， $G$ 與 $H$ 間的同構為所她選，所以可以找到 $H$ 中對應的環）。

#### 健全

若小靜不知哈密頓環，則衹能預先猜測阿嚴會問何種問題，相應準備某個與 $G$ 同構的圖，或另一個不相關的哈密頓圖。然而，因為她不知 $G$ 的哈密頓環，所以無法同時做兩件事。於是，若以上驗證重複 $n$ 次，則小靜矇混過關的概率僅得 $2^{-n}$ ，從而實際意義上，衹需合理多輪驗證，已使造假者寸步難行。

#### 零知識

小靜的回答不泄漏原圖 $G$ 的哈密頓環，因為每一輪，阿嚴衹會得悉 $H$ 與 $G$ 的同構，或是 $H$ 的哈密頓環，兩者之一，但他需要對同一個 $H$ 同時得知兩者，纔能構造出 $G$ 中的哈密頓環。如此，衹要小靜每輪預備一幅不同的圖 $H$ ，就能保密。若小靜不知 $G$ 的哈密頓環，但不知為何已事前得知阿嚴每輪會問的問題，則她可以作弊。例如，若小靜預知阿嚴該輪會問 $H$ 的哈密頓圖，則大可以祕諾一幅與 $G$ 無關的哈密頓圖。與之類似，若小靜預知阿嚴會問同構表，則她可以隨便預備一幅與 $G$ 同構的圖 $H$ （其中她不知道任何哈密頓圖）。阿嚴根本無需小靜在場，亦可獨自想像出自己將見的場面，因為他清楚自己將會問甚麼，將見的僅是一個環（而不顯示圖的其他部分）或一幅與 $G$ 同構的圖，即阿嚴可以自行模擬該協議。因此，阿嚴從每一輪驗證揭露之事，無法得到任何關於 $G$ 哈密頓環的資訊。

## 零知識條件的變式

「零知識」的定義有若干變形，分別在於如何嚴謹定義模擬結果「看似」真實的交互記錄：

**完美零知識（perfect zero-knowledge）**
: 模擬器與真正交互產生的概率分佈完全相等。離散對數範例即屬此類。

**統計零知識（statistical zero-knowledge）**
: 兩個分佈並非完全相等，但統計上接近，即有某個可忽略函數，使該兩列分佈在任意集合取值的概率差，皆小於該函數。

**計算零知識（computational zero-knowledge）**
: 無高效算法分辨兩個分佈。

## 應用

### 身份驗證

零知識證明的研究，是受身份驗證系統啟發。驗證時，一方要向另一方證明自己身份，通常藉賴證明自己持有某種袐密（如通行密碼），但不希望對方知悉該袐密，稱為**零知識知識證明**。不過，通行密碼一般不是太短，就是不夠隨機，不能用於許多零知識知識證明方案。零知識通行碼證明就是有考量密碼長度限制的一類零知識知識證明。

2015 年 4 月，Sigma 協議（「其中之一」證明，英語：one-out-of-many proofs）面世。2021 年 8 月，美國網絡基建、安全公司 Cloudflare 採用該種證明機制，以供應方硬體為私人網絡提供驗證服務。

### 道德行為

密碼學協議之中使用零知識證明，可以在不退讓隱私的情況下，確保各方誠實。粗略言之，方法是迫用戶零知識地證明，其所作所為是依足協議。由健全性，用戶必先確實跟從協議，纔能服眾。又由於證明是零知識，此過程並無犠牲用戶的隱私。

### 核裁軍

2016 年，普林斯頓電漿物理實際室與普林斯頓大學展示一個技巧，或許適用於未來的核裁軍談判。其特點是，無需揭露某物件內部的機密構造，亦可允許督查員判斷該物件是否核武器。

### 區塊鏈

零知識證明用於小零幣與大零幣協議中，最終於 2016 年發展成小零幣（2020 年改稱飛熔幣）和大零幣兩種加密貨幣。小零幣內置有混幣模型，以確保匿名，且該模型無需信任任何對等用戶或中央集權混幣者。用戶可以用另一種基準幣交易，也可以將該幣賣出買入小零幣。大零幣協議的模型也類似（該變式稱為非交互式零知識證明），而且可以掩蓋交易額，但小零幣則不能。大零幣的交易數據如此隱密，所以與小零幣相比，較不易受到隱私計時攻擊。不過，此層額外隱私，可能導致不能追蹤假幣，倘因此造成大零幣供給的超通漲，可能無法偵測到。

2018 年，防彈證明（bulletproofs）面世。其改進自非交互式零知識證明，不再需要可信的安裝環境。其後，實作成「結舌」協議（Mimblewimble protocol，Grin 和 Beam 兩種加密幣皆出自該協議）和門羅幣。2019 年，飛熔幣實作 Sigma 協議，是對應小零幣協議無可信環境的改進。同年，飛熔幣引入萊蘭托斯協議（Lelantus protocol），更自 Sigma 協議改進，隱去交易的源頭與金額。

## 沿革

零知識證明最早由莎菲・戈德瓦塞爾、希爾維奧・米卡利、查爾斯・拉克福三人於 1985 年發表，論文題為〈交互式證明系統的知識複雜度〉。該論文引入交互式證明系統的 **IP** 複雜度類，並構想出「知識複雜度」概念，衡量證明過程中，由證明者傳遞予驗證者的知識量。三人亦給出首個具體問題的零知識證明，即零知識地證明某數不是模 _m_ 的二次剩餘。連同鮑鮑伊・拉茲洛與什洛莫・莫蘭的另一篇論文，戈 - 米 - 拉三氏的論文發明了交互式證明系統。為此，五人同獲 1993 年首屆哥德爾獎。

引述戈 - 米 - 拉三氏：

> 
> 該額外知識基本為 0 的情況尤其值得關注。我等證明，可以交互地證明某數非模 _m_ 的二次剩餘，而釋出零額外知識。其出奇之處是，若不給定 _m_ 的分解，則無高效算法判別某數是否模 _m_ 的二次剩餘。更甚者，任何已知的 **NP** 證明皆要表明 _m_ 的質因數分解。這就表明，在證明過程中添加互動，可能減少證明某定理所必須交流的知識。
> 
> 

二次非剩餘問題既有 **NP** 算法又有**反 NP** 算法，故位處 **NP** 與**反 NP** 兩類之交集中。其後找到有零知識證明的若干個問題，亦具同樣的性質，例如歐迪・戈德賴希未經正式出版的證明系統，可以驗證某數（為兩個未知質數之積）不是布盧姆整數，即並非兩個模 4 餘 3 的質數之積。

歐迪・戈德賴希、希爾維奧・米卡利、阿維・威格森更進一步證明，假定存在無懈可擊的加密法，則可以造出三色圖著色問題的零知識證明系統，而該問題本身為 NP 完全。又因為每個 **NP** 問題都可以高效化歸成該 NP 完全問題，所以在前述假定下，所有 **NP** 問題皆有零知識證明。需要該假定的原因是，正如前節範例，需要有秘諾的手段。若存在單向函數，則的確有牢不可破的加密法。此為廣泛引用的充分條件。另外也可能有物理方法實作。

更上一層樓，他們亦證明，圖不同構問題，即圖同構問題之補，有零知識證明。該問題已知屬於**反 NP**，但未知是否屬於 **NP** 或其他實際可行的複雜度類。更一般地，羅素・英帕利亞佐、莫迪凱・容二人，與米高・本 - 奧爾（Michael Ben-Or）及同事，兩組證明：同樣假設存在單向函數或牢不可破的加密，則任何屬於 **IP**（已證等於 **PSPACE**）的問題，皆有零知識證明。換言之，任何命題若可藉交互系統證明，則可零知識證明。

許多理論家不希望假設不必要的條件，所以試圖在不假定單向函數的條件之下，證明同樣的結論。有種做法稱為「多證明者交互式證明系統」（見交互式證明系統），即有多個獨立的證明者，而非僅得一個。驗證者可以將證明者逐個孤立，然後詰問，以免被作弊證明者誤導。無需任何難解假設，已可證明在此系統中，任何 **NP** 問題皆有零知識證明。

後來發現，網際網路等同時執行多個協議的環境中，較難構造零知識證明。研究並行零知識證明的先驅是辛西婭・德沃克、莫尼・納奧爾、阿米特・薩海。此類研究之中，重要成果有證據不可辨協議。與零知識相比，其性質較弱：可能有多種證據供證明者選擇採用何者作證，此時僅要求驗證者無法分辨證明者選擇為何，但證明者可以泄漏部分資訊，如全體證據組成的集合。儘管失去零知識性質，但此類協議的好處是，並行時不會遇到此前提及的問題。

變式尚有非交互式零知識證明。曼紐爾・布盧姆、保羅・費爾德曼（Paul Feldman）、米卡利證明，若證明者與驗證者共有一條隨機字串，則可以達成計算零知識，而毋須交互。

## 參見

* 配對式密碼學：給定 $f(x)$ 與 $f(y)$ ，無需知道 $x$ 、 $y$ ，已可計算 $f(x\times y)$ 。
* 安全多方計算：各方的輸入值保密，但共同計算出該些輸入對應的結果。
* 圈子簽名：可以簽署某文件，使圈外人無法得悉由圈內何人署名，衹知圈內有某人署名。
* 阿羅資訊悖論
* 密碼學協議
* 費蓋 - 菲亞特 - 薩莫爾身份認證
* 密碼學諸主題

## 註

## 參考文獻