Zero-Knowledge Proof

一些术语

证据（Witness）：the value being proven knowledge of。仅Prover知道，不对Verifier泄露。
实例（Instance）：描述关系中除witness外的所有其它元素，均统称为instance。它是公开信息，对于Prover和Verifier均已知。
证明者（Prover）: the entity proving the knowledge of the witness
验证者（Verifier）：the other party that the prover needs to convince of the knowledge of witness
模拟器（Simulator）：提供“模拟”，它在理想世界（ideal world）中驻留，得到与真实世界（real world）相同的视图（view）分布

有效关系：令 $X, Y$ 是可有效识别有限集（ efficiently recognizable finite sets），有效关系是二元关系： $R\subseteq X \times Y$ ，其中 $\in Y$ 叫做声明（statement），如果 $\in R$ 那么 $x$ 叫做 $y$ 的证据（witness）

关系的语言（Language）
在这里插入图片描述

证明系统

一个证明系统，它需要满足两个条件：
1.完备性（Compeleness）：语言 $L$ ，对于诚实的 $P$ ，给定公共输入 $\in L$ ，那么 $V$ 需要确信 $\in L$ （除了可忽略的概率）
2.可靠性（Soundness）：语言 $L$ ，对于任意的（恶意） $P$ ，给定公共输入 $\notin L$ ，那么 $V$ 需要相信 $\in L$ 的概率可忽略

我们说一个证明是零知识的，如果存在一个模拟器 $S$ ，它可以仅根据公开信息就获得相同的验证者视图。

诚实验证者零知识（HVZK）

在这里插入图片描述

Sigma Protocol

Sigma协议

令 $R$ 是一个有效关系，那么sigma协议是关于 $R$ 的二元组 $(P, V)$
协议如下：
在这里插入图片描述
执行过程为：

Schnorr’s Identification Protocol

Schnorr协议是Sigma协议的实例化，基于离散对数问题。
令 $X=Z_q$ ， $Y = G$ ， $R=\{(\alpha,u) \in X \times Y | g^\alpha = u\}$ ，协议如下：
在这里插入图片描述
执行过程为：

协议安全性：Schnorr身份认证协议是 HVZK 的。

Zero-Knowledge Proof for 3-Coloring

方案

图的着色问题是NP问题。下面利用承诺协议，给出三着色的零知识证明方案：
在这里插入图片描述

安全性

由于图 $G$ 包含 $∣ E ∣$ 条边，任意不知道着色方案的PPT敌手只能随机着色，且图中至少有一条边的两个端点被分配了相同的颜色。因此重复 $n\cdot |E|$ 次后，敌手成功的概率至多为 $(1-\dfrac{1}{|E|})^{n\cdot |E|} \le e^{-n}$ ，可以忽略。