零知识证明

零知识证明（Zero Knowledge Proof，ZKP）是指证明者 P 在不透露任何其他信息的情况下能够向验证者 V 证明某个陈述是真的。也就是说，证明结束时，验证者 V 除了知道这个陈述是真的之外，不知道其他任何信息。

这听上去很不靠谱啊？如果一个人要向我证明某件事，但他又不愿意告诉我更多关于这件事的信息，我凭什么相信他呢？但 Goldwasser 等人在 [GMR85] 里面告诉我们：没错！这真的可以办到！

为了让我们对零知识证明有一个直观的感受，可以先来看一个例子。比如 P 要向 V 证明自己有某个保险箱 S 的钥匙，但他不想直接把钥匙给 V，那么他们可以商量出这样一个协议：V 知道保险箱 S 中有某个物品 T，且其他任何地方都没有这个物品，那么 P 如果能将物品 T 拿到 V 面前，V 就可以认为 P 确实有保险箱 S 的钥匙。在这个过程中，P 并没有直接将钥匙交给 V，在协议结束时，V 除了知道“P 有保险箱 S 的钥匙”之外，不知道任何其他的信息。也就是说，P 和 V 商量出来的协议其实是一个零知识证明协议。

在正式定义零知识证明前，我们需要阐明几个问题，否则零知识证明的数学定义会让我们觉得莫名其妙。

什么是“知识”？

知识（Knowledge）这个词放在一个数学名词里显得非常奇怪，至少我是这么认为的。我能接受的一个解释是：这里的知识其实是指计算角度的知识增益（gain of knowledge）。

如果有人告诉我们“1+2=3”，那么很显然我们没有增长任何知识；但是如果有人告诉我们 4999 和 49787是 248885213 的因子，那么很大概率我们是增长了知识的。造成这种差异的原因是，我们可以自己算出前者，但（不借助计算器的情况下短时间内）算不出后者。

因此在零知识证明中，验证者 V 不知道其他任何信息，是指 V 不能通过和证明者 P 的交互获取 V 本无法通过自身的计算而得到的知识增益。

从 IP 到 ZKP

零知识证明中也有证明者 P 和验证者 V，这说明我们可以将它看成是交互证明的特殊形式，也就是在交互证明的基础上加上了“零知识”这个约束。不难发现，这个约束其实是针对证明者 P 的，因为 P 要保证在向 V 证明陈述的同时也不泄露其他任何信息。

同时注意到，在交互证明的定义中，证明者 P 计算能力是无限制的（computational unbounded），可是这只存在于理论世界里，在现实中并不存在算力无限的机器。因此零知识证明中给出了更加合理的假设，即假设证明者 P 也和验证者 V 一样，是计算能力有限的（computational bounded），更确切地说，他们的计算能力是多项式（polynomial）级别的，这在密码学中又经常被称为“efficient”。

然而上面的这个假设产生了一个新的问题：既然现在 P 和 V 的计算能力都一样了，那么不管陈述是什么，P 能计算的，V 同样也能计算，那么在这个假设下证明陈述都是一个问题，更别谈零知识了。因此 P 一定还会有一个额外的输入，并且 V 不知道这个输入。当要证明的陈述为 $x \in L$ 时，这个额外的输入 $\omega$ 就是证明陈述的证据（witness），这种情况下，$x$ 和 $\omega$ 可以看成是满足关于语言 $L$ 的一个二元关系（relation），把这个二元关系抽象成为二元组集合 $R_L$，那么 $x$ 和 $\omega$ 所满足的关系就可以表达成 $(x, \omega) \in R_L$。

视野和模拟

在密码学中，视野（View）和模拟（Simulate）是两个很重要的概念。下面将它们带入到零知识证明的场景中来解释。

如图，证明者 P 和验证者 V 有一个共同的输入（common input）$x$，除此之外，P 本身还有一个秘密的输入 $\omega$，P 试图向 V 证明陈述 $x \in L$ 是真实的并且除此之外不想让 V 知道更多的信息。于是 P 和 V 遵循某个符合这个要求的零知识证明协议开始交互，交互产生的信息称为记录（Transcript）。

在上述场景中，中间的共同输入（PART I）和交互记录（PART II）是公开的，而左侧 P（PART III）与右侧 V（PART IV）进行的本地计算是保密的。因此 P 的视野（view）就是 P 本地进行的计算和所有公开的信息（PART I + II + III），而 V 的视野就是 V 本地进行的计算和所有公开的信息（PART I + II + IV）。

在零知识证明中的要求中，证明结束时，V 除了知道陈述是真实的之外，不知道其他任何信息。那么要想正式定义零知识证明，就必须要先解决这样一个问题：怎么去用数学语言去描述“不知道其他任何信息”这个条件呢？这不太好回答。

我们换个思路。考虑到 V 在证明开始时，它的视野只有PART I；到证明结束时，它的视野变成了PART I + II + IV，可是这多出来的 PART II + IV 并没有带给 V 更多的知识，因为零知识证明要求 V “不知道其他任何信息”。也就是说，PART II + IV 对 V 来说没有任何计算上的知识增益，V 甚至可以自己在本地瞎捣鼓出一堆输入输出（假设是PART V）当做 Part II + IV 而没有任何不良影响！也就是视野 PART I + II + IV 和视野 PART I + V 在 验证者 V 看来是差不多的（更严谨一点，这称为不可区分的 indistinguishable）。验证者 V 这个在本地瞎捣鼓出类似于与真实的 P 交互的视野的过程就是模拟（simulate）。

零知识证明的定义

现在，我们可以正式地定义零知识证明了。

---

（定义：零知识证明） 给定语言（Language）$L$ 以及关系（Relation）$R_L$，若存在多项式时间（Efficient）的算法元组$(P, V)$，满足：

• 完备性 Completeness：$\forall \ x \in L, \exists \ \omega \in R_L(x)$，​

  $$Pr[P(x, \omega) \leftrightarrow V(x) \mbox{ accepts}] = 1$$

• 可靠性 Soundness: $\forall \ x \notin L, \forall \mbox{ unbounded cheating prover P}$*，

  $$Pr[P^*(x, \omega) \leftrightarrow V(x) \mbox{ accepts}] \le 1/2$$

• 零知识性 Zero-konwledge：$\exists \mbox{ Simulator } S, \forall \mbox{ bounded cheating verifier } V$*，$\forall \ x \in L, \forall \ \omega \in R_L(x)$，

  $$\mbox{VIEW}_{V^{*}}(P(x, \omega) \leftrightarrow V^{*}(x)) \simeq S^{V^{*}}(x)$$

  则称算法元组 $(P, V)$ 为关系 $R_L$ 的零知识证明协议。

---

定义中，完备性和可靠性与交互证明定义中的类似，而零知识性就是用数学语言将上一节的讨论重新描述了一遍。一个协议须要同时满足定义中的三个条件，才能称之为零知识证明协议。

图同构的零知识证明

如图为构造出的图同构（Graph Isomorphism，GI）的零知识证明协议。

对照着零知识证明的定义，我们可以有如下分析。

• 完备性 Completeness：

  如果 $b=0$，那么 $H=\phi(G_b)=\pi(G_0)$，验证通过；

  如果 $b=1$，那么 $H=\phi(G_b)=\pi \circ \omega (G_1) = \pi(G_0)$，验证通过。

• 可靠性 Soundness：

  如果 $x \notin L$，即 $G_0$ 和 $G_1$ 不同构，那么就不存在同构关系 $\omega$，于是 P 就只能欺骗 V。主要到 P 发送的 $H$ 最多只能满足 $b=0$ 或者 $b=1$ 其中一个的验证，由于V 关于 b 的选择是随机的，于是 P 得逞的概率为 $\frac{1}{2}$ 。同样的，这个概率可以通过不断重复图中的证明协议而增强到 $(\frac{1}{2})^n$ 。

• 零知识性 Zero-knowledge：

  在图中的证明协议中，一个被验证者 V 接受的交互记录（即 V 的视野）为一个三元组 $(H, b, \phi)$。其中 $b$ 是随机选取的，而 $H = \pi(G_0)$，考虑到 $\pi$ 也是随机选取的同构映射，那么在不知道 $\pi$ 的情况下，$H$ 也是随机的。同样地，可以证明在不知道 $\pi$ 的情况下，$\phi$ 也是随机的。同时，这个三元组满足关系 $H = \phi (G_b)$。要想要模拟这个视野，模拟器 S 只需要

  1. $b’ \gets \{0, 1\}$ ；
  2. $\phi’ \gets \{ \mbox{All permutations between } G_0 \mbox{ and } G_1 \}$ ；
  3. $H’ := \phi’ (G_{b’})$ ；
  4. 将 $H’$ 发送给 $V$*，如果 $V$* 返回的 $b$ 恰好等于 $b’$，那么 S 就输出 $(H’, b’, \phi’)$，否则回到步骤1。

  注意到 $V$* 对 $b$ 的选择只能是随机的，因此模拟器 S 执行一轮上述步骤的就能输出三元组的概率为 $\frac{1}{2}$，而每轮的结果是相互独立的，于是模拟器 S 能输出三元组的期望值（except）为执行两轮上述操作。这样的情况我们说，模拟器 S 可以在期望意义下的多项式时间（expected polynomial time）内终止。

可以发现，在证明结束后，V 虽然相信了 $G_0$ 和 $G_1$ 同构（假设交互记录最后被 V 接受），但不知道两者为什么同构，因此 V 没有得到任何关于两者同构关系 $\omega$ 的信息，这也正体现了协议的零知识性。

参考资料

[GMR85]: Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof-systems.” symposium on the theory of computing (1985): 291-304. pdf: http://groups.csail.mit.edu/cis/crypto/classes/6.876/papers/gmr-ZK.pdf

Scribes of Berkeley CS 276: Cryptography (Fall 2014). website: https://people.eecs.berkeley.edu/~sanjamg/classes/cs276-fall14/

Slides on Zero knowledge and some applications by Helger Lipmaa. pdf: http://kodu.ut.ee/~lipmaa/teaching/Bergen2004.pdf