零知识证明

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

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

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

生活範例

山洞中，小靜隨機選擇A路或B路，阿嚴則在洞外等候

阿嚴選一個出口

小靜準確出現在阿嚴所選的出口出現

阿里巴巴洞

以下有一個熟知的故事，總結零知識證明的若干重要概念。故事最早由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)}}$值。單獨看任何一個值，其分佈皆是均勻隨機，所以協議每輪皆不泄露任何機密。

大圖的哈密頓環

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

此場境中，小靜知道某大圖$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$哈密頓環的資訊。