零知识证明：Sigma协议

参考书籍：

Boneh D, Shoup V. A graduate course in applied cryptography[J]. Recuperado de https://crypto. stanford. edu/~ dabo/cryptobook/BonehShoup_0_4. pdf, 2017.Lindell Y. How to simulate it–a tutorial on the simulation proof technique[J]. Tutorials on the Foundations of Cryptography, 2017: 277-346. 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 X,Y X,Y是可有效识别有限集（ efficiently recognizable finite sets），有效关系是二元关系： R ⊆ X × Y R\subseteq X \times Y R⊆X×Y，其中 y ∈ Y y \in Y y∈Y叫做声明（statement），如果 ( x , y ) ∈ R (x,y) \in R (x,y)∈R那么 x x x叫做 y y y的证据（witness）

关系的语言（Language）

证明系统

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

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

诚实验证者零知识（HVZK）

Sigma Protocol Sigma协议

令 R R R是一个有效关系，那么sigma协议是关于 R R R的二元组 ( P , V ) (P,V) (P,V)
协议如下：

执行过程为：

Schnorr’s Identification Protocol

Schnorr协议是Sigma协议的实例化，基于离散对数问题。
令 X = Z q X=Z_q X=Zq​， Y = G Y=G Y=G， R = { ( α , u ) ∈ X × Y ∣ g α = u } R=\{(\alpha,u) \in X \times Y | g^\alpha = u\} R={(α,u)∈X×Y∣gα=u}，协议如下：

执行过程为：

首先， P P P选择一个随机数 α t \alpha_t αt​，将承诺 u t u_t ut​发送给 V V V。然后， V V V选择一个挑战 c c c， P P P生成对这个挑战的响应 α z \alpha_z αz​（随机的，与 α t \alpha_t αt​相关，但是与 c c c独立）。最后， V V V验证确实满足 α z = α t + α c \alpha_z = \alpha_t + \alpha c αz​=αt​+αc，所以相信 P P P确实拥有 α \alpha α。

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

Zero-Knowledge Proof for 3-Coloring 方案

图的着色问题是NP问题。下面利用承诺协议，给出三着色的零知识证明方案：

上述协议也符合Sigma协议的范式。

安全性

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

然而上述证明是不够的，我们需要构建一个模拟器 S S S，它可以只根据公开信息获得相同的对话记录。模拟器构建如下：

模拟器调用验证者，猜测验证者想要请求的边，给这条边端点涂上不同色其他随意。然后发送染色的承诺。如果猜对了，那么模拟器成功。如果猜错了，模拟器就回滚（rewinding，技术上利用虚拟机快照实现）验证者，重新猜测，直到猜对。最终，模拟器中的验证者视图和真实世界的会话没有区别。

注意，真实世界中，证明者 P P P和验证者 V V V是独立实体，因此恶意证明者 A A A没有回滚 V V V的能力。