零知識證明與公鑰密碼體制有何聯繫，是不是公鑰密碼體制本身的簽名就是一種零知識證明？

01-04

在公鑰環境下的挑戰-響應方案與身份識別方案中，零知識證明的思想中如何能體現？

簽名和認證協議不一定具有ZK的性質，這是我曾今犯過的一個錯誤。

Zero Knowledge是一個安全性質，不是實體。

說到零知識證明（zero knowledge proof）, 就得先弄清楚什麼叫「Knowledge」。

「知識就是力量」

-- 培根

比較下面兩個信息：（Information）

1. Alpha Go 在與李世石的第一局比賽里，第二手下在D16

2. Alpha Go 在與李世石的第一局比賽里，第一手結束後，內部的神經網路的結構是（#@%），連接權值依次是(x, y, ....)。

兩條信息如果都是真實的，其實都告訴你了Alpha Go第二手下在了哪裡（從第二條信息至少可以以很大概率模擬出Alpha Go的行為，相當於告訴了第二步）

可能你已經發覺，第一條信息，沒法幫助你預判alpha go在第三步第四步最大可能的應變。而信息二，如果把alpha go想像成一個人，則相當於告訴了你他腦袋裡正在想什麼，接下來最有可能做什麼，從而讓你可以以相當高的準確率來預測他的行為。甚至說，如果硬體相同，你相當於複製了一個alpha go!

密碼學中提到的Knowledge，正是類似於信息2的東西。簡單來說，能提高接收者的「計算能力」的消息被稱之為Knowledge。

比如，給出RSA公鑰(N, e), 當N足夠大時，在不知道N的兩個素因子 P與Q的情況下，很難求出私鑰d, 滿足 $d = e^{-1} mod phi(N)$

此時，如果攻擊者只知道公鑰的信息，他沒有計算d的能力。

而一旦告訴他P與Q，他就能高效地計算出d了，甚至只要N不變，給任意一個有效的e", 他都能算出相應的d"了。這裡的P、Q就是Knowledge。

聊完Knowledge，再來說說什麼是"互動式證明"（interactive proof system）

這種證明系統里，一般都有兩個角色，一個是Prover（證明者），一個是Verifier（驗證者）。系統的目的是讓prover證明給verifier看，某個斷言（Statement）是正確的。為此，首先要準備一些大家（verifier, prover）都知道的公共信息（Common Input）作為輸入，然後雙方你一步我一步地計算輸出一系列消息並發送給彼此，這些接下來消息記錄（transcript）被稱為一個證明。

比如Statement是「Prover知道大數N的因數分解」，common input是N。那麼很顯然，如果prover輸出P、Q，滿足N = P x Q，自然就證明了自己的確知道P、Q。

可惜的是，這個「顯然」的互動式證明過程，顯然泄露了knowledge。因為Verifier現在也可以分解N了。

類似的例子，如果Common Input是 $(g,p,Y =g^x)$ , 其中g是某個階數為大素數p的群的生成元，比如橢圓曲線上的點構成的群，這個群上的離散對數計算是困難的。

然後Statement是「Prover知道x」。證明過程是prover直接告訴verifier，滿足 $Y=g^x$ 的 x值。

這樣也同樣泄露了Knowledge,因為原先verifier自己是算不出x的。

Zero-Knowledge，說的就是這種證明過程里，並沒有任何的Knowledge被泄露。

也就是說，在收到Prover發送的所有信息後，Verifier也僅僅是知道「Statement is true」，而無法利用這些信息解決自己原本無法解決的問題。

下面是一個證明「Prover知道x」的，zero-knowledge證明：（Schnorr Protocol）

1. Common Input $(g,p,Y =g^x)$ , Prover P知道x

2. P隨機選擇r，發送 $a=g^r$ 給V

3.V隨機選擇 $e in { 0, 1}$ ，發送e給P

4. P計算z = r + xe，發送z給V

5. V驗證 $g^z = a Y^e$ ,相等的話就證明通過

Zero-Knowledge「沒有任何的Knowledge被泄露」，反過來說，就是指transcript（證明過程）必須在僅僅知道公開信息時，也可以高效地被simulate。

上面證明過程中包含 $(a, e,z)$ 三條消息

一個simulator可以先猜一下e, 然後取任意的z，最後計算 $a=g^z Y^{-e}$ ，很容易驗證，這樣產生的

$(a, e,z)$ 和原來真正的證明有一半的概率是相同分布的。所以上面的Schnorr Protocol是有ZK性質的。

但對於下面這個身份驗證協議（identification scheme），在不知道sk的情況下，simulator無法模擬/產生一個對任意給定m的簽名，也就沒法對所有的Verifier都產生有效的transcript。

例：一個Identification Scheme描述如下:

1. V,P完成初試設定，即共同持有相同的RSA modulus N，pk，同時P持有sk

2. 驗證開始，V發送任意的 $m in Z_{N}^*$ 給P

3. P發送在m上的RSA簽名給V

4. V驗證簽名，輸出1當簽名合法，否則輸出0

斷言：此Identification Scheme不是ZK的。

證明（sketch）:

（引自Zero-knowledge proof ）觀察ZK的定義，對於IPS（P，V）必須存在滿足下麵條件的Simulator S

$forall ppt hat{V} , exists ppt S : View_{hat{V}} [P(x) leftrightarrow hat{V}(x, z)] = S(x,z)$

也就是說，對於任意的V，模擬器S必須在僅拿到可公開信息（比如public key，也可能包括固定的challenge）的情況下，有效地模擬出 $P hat{V}$ 之間的對話。如果challenge是任意的m，V要求的是P產生對m的RSA簽名，在沒有sk的情況下，基於RSA假設，S是沒法在m上簽名，併產生相應的transcript的。

從另一個角度來說，每進行一次這種消息/簽名認證，攻擊者或者說是Verifier從transcript中總能得到在與P互動之前沒法計算的東西，即在某個m上的簽名，這一點也是knowledge leakage。所以基於RSA簽名的認證方案在這種情況並不具備ZK的性質。

再次強調，Zero-Knowledge是證明系統（proof system）的安全性質，不是固定的實體。

話說回來，要對一個實體來進行identification或者Authentication，基本上都需要他們證明某些statement,比如「我的確是用戶名為玄星的知乎用戶」或者「我的確持有相應的私鑰」。

這個證明的過程，其實是可以做到ZK的。

下面這篇paper里提到的identification scheme中的protocol就是ZK的。

另外，可以用到Non-Interactive Zero-Knowledge的相關性質把這個認證方案，轉化成一個簽名方案。https://eprint.iacr.org/2005/123.pdf （5.3節提到的Fiat-Shamir transformation https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic

這是把一個identification scheme轉化成signature schme的一種方法。）

總之，indentification scheme, signature schme以及ZK這幾個概念並不能互換或者完全包含彼此。

公鑰能夠認證一方或者雙方。

零知識只是向你證明一個東西我掌握了。但是你沒有辦法盜用我的證明過程。因為它使用協議分割的辦法，一次證明一部分。若干次之後你相信我掌握了這樣的東西。

不同的功能適用於不同的場景。

HANDBOOK of APPLIED CRYPTOGRAPHY 第十章都有了。