零知识证明 (Zero-Knowledge Proof)

零知识证明是一种保护隐私的证明方式，它的历史最早可以追溯到 1985 年由 Goldwasser, Micali 和 Rackoff 的文章¹。简单来说，零知识证明协议中存在两个实体，即证明方 $\mathcal{P}$ 和验证方 $\mathcal{V}$ 。 $\mathcal{P}$ 需要让 $\mathcal{V}$ 相信自己知道某个 witness $w$ ，但又不能将 $w$ 直接告诉 $\mathcal{V}$ 。

最直观的例子就是 $\mathcal{P}$ 知道 $h$ 的离散对数 $w$ ，（即 $g^w=h\ \mathsf{mod}\ n$ ），同时 $\mathcal{P}$ 希望能让 $\mathcal{V}$ 信服，但又不能直接将 $w$ 展示给 $\mathcal{V}$ 。乍一听有种悖论的感觉，但实际上是有很多方法可以做到。

In fact, the theory of zero-knowledge proofs tells us that any NP-statment can be proved efficiently in zero-knowledge.

1. Schnorr's scheme

Schnorr 的证明方案²分为三步：

Schnorr's scheme

$\mathcal{P}$ 想证明自己知道 $h$ 的离散对数 $w$ （即 $h=g^w\ \mathsf{mod}\ n$ ），那么：

$\mathcal{P}$ 随机选取一个 $u\leftarrow_R\mathbb{Z}_n$ ，并将 $a=g^u$ 发送给 $\mathcal{V}$ ；
$\mathcal{V}$ 随机选取一个 $c\leftarrow_R\mathbb{Z}_n$ ，并发送给 $\mathcal{P}$ ；
$\mathcal{P}$ 计算 $r=u+cw$ ，并把 $r$ 发送给 $\mathcal{V}$ ， $\mathcal{V}$ 只需要验证 $g^r\overset{?}{=}ah^c$ 。

这个方案满足三个性质： Completeness、Special soundness、Special honest-verifier zero-knowledgeness。

Completeness：因为 $g^r=g^{u+cw}=g^u*g^{cw}=ah^c$ ，所以此方案是完备的；
Special soundness：如果有满足条件的 $(a;c;r)$ 和 $(a;c';r')$ ，那么可以通过知识解析器（extrator）计算出 $w$ 的值，即 $w=(r-r')/(c-c')$ ；
Special honest-verifier zero-knowledgeness：在不知道 $w$ 的情况下，可以“通过先取 $r$ 和 $c$ ，再计算 $a=g^r/h^c$ 的方式” 生成一个满足条件的 $(a;c;r)$ ，这样算出的 $(a;c;r)$ 与协议中的 $(a;c;r)$ 具有相同的概率分布。

2. Sigma-Protocol

如果满足上述三个性质，那么这个协议又可以称作 $\Sigma$ -protocol。在 $\Sigma$ -protocol 中，我们把 $\mathcal{P}$ 拥有的知识称为 witness，用 $w$ 表示，双方共同的输入用 $v$ 来表示。下面对三个性质进行说明。

Completeness 主要证明 “ 如果 $\mathcal{P}$ 知道 $w$ ，那么通过这个协议一定能说服 $\mathcal{V}$ ”，因此证明的方式就比较 straightforward；
Soundness 的意思是 “ 如果 $\mathcal{P}$ 不知道 $w$ ，那么它能够完成验证的几率是可以忽略不计的” 证明需要使用逆否命题，即如果能较轻松完成证明，那么 $\mathcal{P}$ 就会知道 $w$ 。加上 Special 之后就变成，对于一个 $\Sigma$ -protocol，如果有一组 $(a;c;r)$ 和 $(a;c';r')$ ，且 $c\neq c', r\neq r'$ ，那么我们可以构造一个知识解析器（knowledge extractor）将 witness 计算出来；
Special honest-verifier zero-knowledgeness，证明的思想来自 simulation-based，比较正式的描述是：存在一个 p.p.t 算法 $S$ （simulator），对于任意的 $v\in L_R$ 和 $c\in C$ ， $S$ 都能生成一个 $(a;c;r)$ ，而且它的分布概率与原协议将 $v,c$ 作为输入，及 $(v,w)\in R$ 所产生的结果的分布概率是一样的。

问题1

如果把 Schnorr 协议的第三步改成 $r=cu+w$ ，验证时用 $g^r\overset{?}{=}a^ch$ ，（当然 $u\leftarrow_R\mathbb{Z}_n^*$ ），那么它还是 $\Sigma$ -protocol 吗？

Hint

如果有人让你给他举个例子说明 $\Sigma$ -protocol 是无法保证对 cheating verifiers 零知识，那你就可以使用这个例子。

首先是如何证明它是 $\sigma$ -protocol 的呢？难点在于第三步，对于按照这个协议产生的 $(a;c;r)$ 的分布为：

$\{(a;c;r):u\in_R\mathbb{Z_n^*;c\in_R\mathbb{Z}_n;a\leftarrow g^u;r\leftarrow_ncu+x}\}$

因为 $C$ 的空间为 $n$ ，一旦 $c$ 确定下来， $r$ 的取值就由 $u$ 决定，因此分布中每个 $(a;c;r)$ 出现的概率都是 $1/n(n-1)$

再考虑对于 simulator $S$ 的情况，因为 $S$ 不知道 $w$ ，而当它选择的 $r$ 刚好满足 $g^r=h$ 时，它就会知道 $c=0$ ；如果不满足这个关系，它就随机选取 $c$ ，因此它的分布可以看为：

$\{(a;c;r):r\in_R\mathbb{Z}_n; \begin{equation} \left\{ \begin{array}{rcl} c\leftarrow 0;u\in_R\mathbb{Z}_n^*;a\leftarrow g^u,& \mbox{if}\ g^r=h \\ c\in_R\mathbb{Z}_n^*;a\leftarrow (g^r/h)^{1/c},& \mbox{if}\ g^r\neq h \\ \end{array} \right. \end{equation} \}$

当 $g^r=h$ 时，一共 $(n-1)$ 中情况；当 $g^r\neq h$ 时，一共 $(n-1)(n-1)$ 中情况，因此所有 $(a;c;r)$ 的组合一共有 $n(n-1)$ 种，每种出现的概率均为 $1/n(n-1)$ 。与之前的分布是一致的。

对于 cheating verifiers，他们只需要将 $c$ 的值设为 $0$ ，即可获得 witness $w$ ，因此这个协议虽然是 $\Sigma$ -protocol，但并不能保证对 cheating verifiers 零知识。

对于 $\Sigma$ -protocol 有五种不同的组合方式，即 parallel composition, AND-composition, EQ-composition, OR-composition, 和 NEQ-composition。下面还是以 Schnorr 的协议来描述这些组合方式。

3-1. Parallel composition

对于 $\mathcal{P}$ 证明自己知道 $x_1=log_g h_1,x_2=log_g h_2$ ：

$\mathcal{P}$ -> $\mathcal{V}$ ： $\mathcal{P}$ 选取 $u_1,u_2\in_R\mathbb{Z}_n$ ，计算 $a_1\leftarrow g^{u_1}, a_2\leftarrow g^{u_2}$ ，并将 $a_1,a_2$ 发送给 $\mathcal{V}$ ；
$\mathcal{P}$ <- $\mathcal{V}$ ： $\mathcal{V}$ 选择 $c\in_R\mathbb{Z}_n$ ，将 $c$ 发送给 $\mathcal{P}$ ；
$\mathcal{P}$ -> $\mathcal{V}$ ： $\mathcal{P}$ 计算 $r_1\leftarrow_n u_1+cx_1,r_2\leftarrow_n u_2+cx_2$ ，并将 $r_1,r_2$ 发送给 $\mathcal{V}$ ； $\mathcal{V}$ 验证 $g^{r_1}\overset{?}{=}a_1h_1^{c}, g^{r_2}\overset{?}{=}a_2h_2^{c}$ 。

4. 构造数字签名

任意的 $\Sigma$ -protocol 都可以构造数字签名，这个想法是由 Fiat 和 Shamir 提出来的（Fiat-Shamir heuristic）。核心思想在于 $c$ 的构造，在一般的 $Sigma$ -protocol 中， $c$ 一般都是随机选取的。但是如果我们将 $c$ 取做某个值的哈希，比如

$c\leftarrow H(a,M)$

其中， $M$ 是需要签名的消息。这样的话，双方都可以得到同样的 $c$ ，同时还减少了一次交互。值得注意的是，这种构造的安全性是基于 random oracle 下的（因为哈希函数 $H$ 的使用）。这样构造的协议也称作非交互式的零知识证明（Non-interactive $\Sigma$ -protocol）。

Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208. ↩
Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174. ↩