Schnorr's Protocol, A ZK Proof for Dlog (Prove You Know Your Private Key)

上面提到， 一个协议的某参与者如果需要发送其公钥给其它人时，那么这个参与者需要证明他掌握这个公钥对应的私钥。否则，这个协议可能不安全。 是否有例子来说明这种不安全性呢？答案是有的，比如 Rogue Key Attack。

下面以 Schnorr 多签协议的例子来说明一下 Rogue Key Attack。假设 Alice 和 Bob 要组成 2-2 Schnorr 多签协议，协议的大概流程是，Alice 把她的公钥 $Q_A=s_A\cdot G$ 发送给 Bob，而 Bob 也把他的公钥 $Q_B=s_B\cdot G$ 发送给 Alice，这样它们两个人对外的共同公钥是 $Q=Q_A+Q_B=(s_A+s_B)\cdot G$ ，共同私钥是 $s_A+s_B$ 。

如果协议中没有要求 Alice/Bob 提供证明，来证明他们分别知道其对应的私钥（即 $s_A$ 和 $s_B$ ），则这个协议有安全问题。比如 Bob 作恶，发送给 Alice 的公钥并不是 $Q_B$ ，而是把 $Q_B-Q_A$ 发送给 Alice，这样，算出来的共同公钥就是 $Q_A+(Q_B-Q_A)=Q_B$ 了，从而 Bob 一个人就掌握了这个共同公钥背后的私钥 $s_B$ 了。

如果要求 Bob 证明他知道他所提交的公钥所对应的私钥，则上面的 Rogue Key Attack 就可以避免，因为 $Q_B-Q_A$ 所对应的私钥为 $s_B-s_A$ ，Bob 不知道 Alice 的私钥 $s_A$ ，显然 Bob 无法证明他知道 $s_B-s_A$ 。

假设 DSA 参数分别为 $(p,q,g)$ ，其中 $p,q$ 是大素数，且满足 $q\mid p-1$ ，私钥 $x$ 为 $\{1,2,\cdots ,q-1\}$ 中随机数，公钥为 $y=g^{x}modp$ 。

通过下面的 3 趟交互过程，Prover A 可以向 Verfier B 证明他确实知道 $y$ 对应的私钥 $x$ ，这个过程没有泄露私钥 $x$ 。

Schnorr's Protocol:

        Prover A                                       Verfier B
--------------------------                     --------------------------

从 [1,q-1] 中选择随机数 r
计算 t = g^r mod p                --- t --->


                                  <-- c ----     选择随机数 c


计算 z = r + c x mod q            --- z --->      验证：g^z = t * y^c mod p 是否成立？

最后一步，如果 Verfier B 验证 $g^z=t\ast y^{c}modp$ 成立，则说明 Prover A 确实知道 $y$ 对应的私钥 $x$ 。这是因为：
$$\begin{array}{rl}{g}^z& =g^{r+cx}\\ & =g^r\cdot g^{cx}\\ & =t\cdot ({\mathit{g}}^{\mathit{x}}{)}^c\\ & =t\cdot {\mathit{y}}^c\end{array}$$

假设椭圆曲线，某私钥 $d$ 为 $\{1,2,\cdots ,n-1\}$ 中随机数，公钥为 $Q=dG$ 。

通过下面的 3 趟交互过程，Prover A 可以向 Verfier B 证明他确实知道 $Q$ 对应的私钥 $d$ ，这个过程没有泄露私钥 $d$ 。

Schnorr's Protocol:

        Prover A                                       Verfier B
--------------------------                     --------------------------

从 [1,n-1] 中选择随机数 r
计算 T = r G                      --- T --->


                                  <-- c ----     选择随机数 c


计算 z = r + c d mod n            --- z --->      验证：T = z G - c Q 是否成立？

Schnorr Protocol 是一种 Sigma Protocols，形如图 2（摘自：A Graduate Course in Applied Cryptography, by Dan Boneh and Victor Shoup）所示的协议都是 Sigma Protocols。

一个 Sigma Protocol 共有 3 趟，3 趟所发的消息分别为 commitment、challenge、response。 之所以称为“Sigma Protocols”，这是因为希腊字母 $\mathrm{\Sigma }$ 的写法和交互流程有点像。