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 \bmod p\) 。

通过下面的 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 * y^c \bmod p\) 成立，则说明 Prover A 确实知道 \(y\) 对应的私钥 \(x\) 。这是因为：
\[\begin{aligned} g^z &= g^{r+cx} \\ &= g^r \cdot g^{cx} \\ &= t \cdot (\boldsymbol{g^x})^c \\ &= t \cdot \boldsymbol{y}^c \end{aligned}\]

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

通过下面的 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”，这是因为希腊字母 \(\Sigma\) 的写法和交互流程有点像。