simulationPart2

How To Simulate It – A Tutorial on the Simulation Proof Technique-Part2

Simulating the View of Malicious Adversaries– Zero Knowledge

零知识仿真考虑的是恶意对手（尤其是恶意验证者），他们的行为可能是任意的，不一定符合协议规范。零知识中没有私人输入或输出，模拟器需要在证明中生成验证者的观点，而不需要考虑输入和输出的额外复杂性。

Defining Zero Knowledge

Notation

$A$：概率多项式时间机器

$A(x,y,r)$：机器A在输入$x$，辅助输入$y$和随即磁带$r$上的输出。

$n=|x|$：语句$x$的长度

$output_B(A(x,y,r_A),B(x,y,r_B))$：表示乙方在公共输入$x$上与甲方交互执行的输出，其中甲方有辅助输入$y$和随机磁带$r_A$，乙方有辅助输入$z$和随机磁带$r_B$

$output_B(A(x,y),B(x,z)),output_B(A(x,y,U_m),B(x,z,U_m^\prime))$

$m$：是 A（或B）在大小为$|x|$的输入上使用的随机比特数。

The definition

语言$L$的交互式证明系统包括一个证明者$P$和一个验证者$V$，在共同输入$x$时，证明者$P$试图让验证者$V$相信$x \in L$。这样的证明系统具有以下两个特性：

1. 完备性：这说明，当诚实的$P$和$V$就共同输入$x\in L$进行交互时，那么$V$确信$x\in L$这一语句的正确性（但最多可忽略的概率除外）。
2. 健全性：这说明当$V$在共同输入$x \in L$上与任何（作弊的）证明者$P$交互时，$V$将以最多可忽略的概率被说服。(因此，$V$不可能被骗去接受一个错误的陈述）。

如果存在一个模拟器，可以仅从语句生成验证者的观点，那么这个证明就是零知识。我们要指出的是，被破坏的验证者可以输出任何它想输出的东西，包括它的观点。

在本文定义中，我们仅考虑黑盒情况和$NP$语言情况

Definition 5.1 Let $(P,V)$ be an interactive proof system for an $NP-language L$, and let $R_L$ be the associated $NP-relation$. We say that $(P,V)$is black-box computational zero knowledge if there exists a probabilistic-polynomial time oracle machine $S$ such that for every non-uniform probabilisticpolynomial time algorithm $V^*$ it holds that:

$\{output_{V^*}(P(x,w),V^*(x,z))\}_{(x,w)\in R_L, z\in \{0,1\}^*}\stackrel{c}{\equiv} \{S^{V^*(x,z,r,\cdot)} \}(x)_{x\in L,z \in \{0,1\}^*}$

where $r$ is uniformly distributed, and where $V^*(x,z,r\cdot)$ denotes the next-message function of the interactive machine $V^*$ when the common input $x$, auxiliary input $z$ and random-tape $r$ are fixed (i.e., the next message function of $V^*$ receives a message history $m^\prime$ and outputs $V^∗(x,z,r,m^\prime))$.

定义5.1：设 $(P,V)$ 是一个 $NP$ 语言 $L$ 的交互式证明系统，$R_L$ 是相关的 $NP$ 关系。如果存在一个概率多项式时间的预言机器 $S$，使得对于每一个非一致的概率多项式时间算法 $V^*$，都有以下等价关系成立：

$\{output_{V^*}(P(x,w),V^*(x,z))\}_{(x,w)\in R_L, z\in \{0,1\}^*}\stackrel{c}{\equiv} \{S^{V^*(x,z,r,\cdot)} \}(x)_{x\in L,z \in \{0,1\}^*}$

其中 $r$ 是均匀分布的，$V^*(x,z,r\cdot)$ 表示当公共输入 $x$、辅助输入 $z$ 和随机带 $r$ 固定时，交互式机器 $V^*$ 的下一条消息函数（即 $V^*$ 的下一条消息函数接收一个消息历史 $m^\prime$ 并输出 $V^∗(x,z,r,m^\prime)$）。

这段话的意思是，对于一个 $NP$ 语言的交互式证明系统 $(P,V)$，我们称它为黑盒计算零知识，如果存在一个概率多项式时间的预言机器 $S$，使得对于任何非一致的概率多项式时间算法 $V^*$，系统的输出与 $S$ 机器的输出在计算上是不可区分的。这里的 “不可区分” 指的是，即使有一个强大的对手，也无法有效地区分两个输出集合的差异。

在这个定义中，$P$ 是证明者，$V$ 是验证者，$V^*$ 是一个可能的恶意验证者。$x$ 是公共输入，$w$ 是证明者的私有见证，$z$ 是辅助输入，$r$ 是随机带。预言机器 $S$ 被用来模拟证明者 $P$ 的行为，以产生一个与实际交互过程中验证者 $V^*$ 观察到的输出在计算上不可区分的输出。

简而言之，这个定义说明了一个交互式证明系统是零知识的，如果存在一个模拟器 $S$，它可以在不知道证明者私有见证 $w$ 的情况下，仅仅通过与恶意验证者 $V^*$ 的交互，生成一个与真实交互过程中 $V^*$ 观察到的输出在计算上不可区分的输出。这保证了即使验证者尝试作弊，也无法获得关于证明者私有见证的任何信息。

Preliminaries– Commitment Schemes

$c=Com_n(x;r)$：通过使用随机字符串$r$和安全参数$n$对$x$的承诺

$if\ c=Com_n(x;r), decom(c)=(x,r)$

perfect binding 是一个重要的概念，它确保了一个承诺方案（commitment scheme）的安全性。承诺方案允许一个人承诺一个值而不立即透露它，同时确保该值在未来可以被验证。

$for\ all\ x_1 \ne x_2, C_{x_1}\cap C_{x_2}, where\ C_{x_1}=\{c|\exist r:c=Com(x_1;r\},C_{x_2}=\{c|\exist r:c=Com(x_2;r\}$

Computational hiding对于任何有限计算能力的攻击者来说，对不同字符串的承诺在计算上是无法区分的。换句话说，即使攻击者使用所有可用的计算资源，他们也无法确定承诺是对哪个字符串做出的。

$C_0\stackrel{c}{\equiv}C_1, C_b=\{Com(b;U_n\}_{n\in N}$

LR-security of commitments

$LR-oracle$（$Left\ or\ Right\ oracle$）的定义是通过向对手提供一个甲骨文来实现的，这个预言机接收两个等长输入，要么总是返回对第一个（左）输入的承诺，要么总是返回对第二个（右）输入的承诺。对手的任务就是确定它收到的是左承诺还是右承诺。

我们将其定义为

$LR_{Com}^b(x_0,x_1)=\{Com(x_b), if |x_0|=|x_1|\\ \{\perp, otherwise$

其中敌手$\mathcal{A}$要么被给予$LR_{Com}^0$要么被给予$LR_{Com}^1$并且要尝试能够区分这两个。

Experiement $LR-commit_{Com,\mathcal{A}}(1^n)$

1. Choose a random $b\leftarrow \{0,1\}$
2. Set $b^\prime \leftarrow \mathcal{A}^{LR_{Com}^b(\cdot,\cdot)}(1^n)$
3. Output 1 if and only $b^\prime=b$

如果$Com$是一个非交互式完全约束承诺方案，对非均匀对手具有安全性，那么对于每个非均匀概率-多项式时间对手$\mathcal{A}$，都存在一个可忽略的函数$\mu$，使得

$Pr[LR-commit_{Com,\mathcal{A}}(1^n)=1]\le \frac{1}{2}+\mu(n)$

我们将在下文中指出，非均匀安全性是必需的。

Non-Constant Round Zero Knowledge

考虑零知识证明中的三着色问题和汉密尔顿性。

这类协议通常包含着三部分：

1. $P$发送承诺（commitment）
2. $V$发送挑战（challenge），并要求$P$打开承诺
3. $P$发送合适的回应（decommitment）

考虑三色问题，这类问题要求证明，在一个图$G$中，要求为$G$中每一个顶点涂色，使得相邻两个顶点的颜色不同。证明者承诺一个随机的有效着色，验证者要求打开与一条边相关的颜色。图中必须至少有一条边能为证明者承诺着色的边的两个端点分配相同的颜色。如果验证者要求打开这条边的颜色，那么证明者就会被发现作弊。因此，证明者作弊的概率最多为$\frac{1}{|E|}$，其中$E$是边的合集

通过重复证明 $n\cdot |E|$次（其中$n$是图的个数），我们可以得出证明者作弊的概率最多$(1-\frac{1}{|E|})^{n\cdot |E|} < e^{-n}$可以忽略不计。因此，这个证明是正确的。

对于这个问题的模拟器证明思路，如果模拟器提前知道要查询的边，那么它就可以在该边的端点上随机承诺不同的颜色，而在其他地方承诺垃圾颜色。根据承诺方案的隐藏特性，这将是无法区分的。我们将看到，模拟器只需重复猜测要提前查询的边，直到猜对为止。

The rewinding technique (with commitments as envelopes)

首先，我们将描述如何构建一个模拟器，当我们把承诺建模为完美的信封时，信封在打开之前什么也不会显示。

构建模拟器的关键工具是重绕（rewind）。

模拟器调用验证器，并猜测一条随机边$e=(v_i,v_j)\in_R E$，希望验证器能查询这条边。

然后，模拟器会向验证者发送着色承诺。

如果验证者回复边$e^\prime=e$，那么模拟器就为$e$中的节点打开信封，本次迭代的模拟就完成了。否则，模拟器会将验证器倒退到迭代的起点并再次尝试，这次选择一条新的随机边。如此反复，直到$e^\prime = e$，模拟器就成功了。

这种倒退不同于一般的倒退，它存在一定的失忆性，也就是不会记录失败的情形，就如同虚拟机的快照功能，可以快速回到某个时刻的某种状态。不失一般性的情况下，模拟器选择边的概率是$\frac{1}{|E|}$，期望次数为$|E|$，当执行超过$n\cdot|E|$次rewinding后，能够确保模拟器以极大的概率最终通过挑战。

这种设计下，验证者在模拟中的视图分布与其在实际执行中的视图分布完全相同。两者之间的区别在于，在真实证明中没有rewinding。

模拟器是如何实现rewind功能的

具体来说，模拟器可以从Oracle中获取验证者的下一个信息函数$V^*(x,z,r,\cdot)$。这意味着，它提供了一份传入信息的副本$\vec{m}=(m_1,m_2,...)$，并在$V^*$具有输入$x$、辅助输入$z$、随机磁带$r$和传入信息$\vec{m}$时，接收回发送的下一条信息。现在，倒带实质上就是$S$用$(r,(m_1,m_2,m_3))$调用其甲骨文，然后再用$(r,(m_1,m_2,\vec{m}))$调用，以此类推。

零知识属性与健全性不矛盾

模拟器可以在不知道证明者的情况下证明定理，作弊者不可以，因为模拟器拥有证明者所不具备的额外能力，rewind。

上述承诺模型过于简单，我们还需要证明：

首先，必须证明验证者的视图在模拟和实际执行中是不可分的。

需要证明模拟在$n|E|$次尝试内成功停止，除非概率可以忽略不计。

关于中止情况的处理

在模拟阶段，如果$V^*$没有返回某条有效的边，可以让真正的验证者将任何无效回复解释为默认边。

Theorem：Let $Com$ be a perfectly-binding commitment scheme with security for non-uniform adversaries. Then, the 3-coloring protocol of is black-box $computational\ zero\ knowledge$.

Proof：

$S$是一个模拟器，给定一个图$G=(V,E),V=\{v_1,...,v_n\}$，以及对某个个概率多项式时间$V^*(x,z,r,\cdot)$的访问

工作原理如下：

1.$S$将消息历史副本$\vec{m}$初始化为空字符串$\lambda$

2.以下步骤重复$n\cdot |E|$次

（a）$S$设置$j=1$

（b）$S$随机选择一条边$(v_k,v_l)\in_RE$并给两个点不同颜色。形式上，$S$选择$\phi(k)\in_R\{1,2,3\}$并且\phi(v_l)\in_R\{1,2,3\} \textbackslash {\phi(v_k)}。对于其余的v_i \in V \textbackslash {v_k,v_l}，$S$设置$\phi(v_i)=0$

（c）对于$i=1,...,n$，$S$计算$c_i=Com(\phi(v_i))$

（d）$S$发送$(c_1,...,c_n)$给$V^*$。形式上，$S$查询与该向量连接的$\vec{m}$，并让$e\in E$作为回复

（e）如果$e=(v_k,v_l)$，那么$S$将承诺$(c_1,...,c_n)$和$(decom(c_k),decom(c_l))$发送给$\vec{m}$。形式上，$S$更新字符串$\vec{m}\leftarrow (\vec{m},(c_1,...,c_n),(decom(c_k),decom(c_l)))$

（f）如果$e \ne (v_k,v_l)$，那么$S$设置$j \leftarrow j+1$。如果$j = n\cdot |E|$，则$S$输出失败符号$\perp$，否则返回第2b步。

3.$S$输出$V^*$的任何结果。

为了证明模拟器$S$，我们构建一个新的模拟器$S^\prime$，它每次都知道正确的着色方法。

我们强调$S^\prime$并不是一个有效的模拟器，因为它得到的是$\phi$。相反，它是用于证明的思想实验。

现在，$S^\prime$的工作方式与$S$完全相同，只是在每次迭代中，它都会在$\{1,2,3\}$上随机选择一个置换$\pi$，设置$\phi(v) = \pi(\phi(v))$，并对所有$i$计算$c_i = Com(\phi(v_i))$，这与真正的证明者完全相同。

我们要首先证明，模拟器$S^\prime$和$V^*$的输出是一致的，即对于每个$V^*,(G,\phi)\in R_L,z\in \{0,1\}^*$：

$\{output_{V^*}(P(G,\phi),V^*(G,z))\}\equiv \{S^{\prime V^*\{G,z,r,\cdot\}}(G,\phi)|S^{\prime V^*\{G,z,r,\cdot\}} (G,\phi)\ne \perp\}$

由于二者都是对有效着色的随机排列的承诺，因此两者的分布是相同的。唯一不同的是，$S^\prime$提前选择了一条边$e$，并且只有当$V^\prime$发送的查询等与$e$时才结束迭代。

接下来证明，$S^\prime$最多以可忽略的概率输出$\perp$。在一次循环中，$n\cdot |E|$次都没选中$e$的概率是

$(1-\frac{1}{|E|})^{n\cdot |E|} < e^{-n}$，对于$n\cdot|E|$轮循环中，概率不会超过$n\cdot|E|\cdot e^{-n}$，也就满足

$\{S^{\prime V^*(G,z,r,\cdot)}(G,\phi)|S^{\prime V^*(G,z,r,\cdot)}(G,\phi)\ne \perp\}\equiv \{S^{\prime V^*(G,z,r,\cdot)}(G,\phi)\}$

最终，我们得到$S$和$S^\prime$是不可区分的：

$\{S^{\prime V^*(G,z,r,\cdot)}(G,\phi)\} \stackrel{c}{\equiv} \{S^{ V^*(G,z,r,\cdot)}(G,\phi)\}$

假设存在一个概率多项式时间验证器$V^*$、一个概率多项式时间区分器$D$和一个多项式$p(\cdot)$，对于一个无限序列$(G,\phi,z),(G,\phi)\in R,z\in\{0,1\}^*$

$|Pr[D(G,\phi,z,S^{\prime V^*(G,z,r,\cdot)}(G,\phi))=1]-Pr[D(G,\phi,z,S^{ V^*(G,z,r,\cdot)}(G,\phi))=1]| \ge \frac{1}{p(n)}$

我们利用$LR-commit$实验作为证明方法，攻击者$\mathcal{A}$接收$(G,\phi,z)$作为辅助输入

1.$\mathcal{A}$输入$G,z,r$，初始化$V^*$

2.然后$\mathcal{A}$输入$(G,\phi),V^*(x,z,r;\cdot)$，但算法$\mathcal{A}$需要一些改动

（1）对于随机选择的边$e=(v_k,v_l)$，生成承诺$c_k=Com(\phi(v_k)),c_l=Com(\phi(v_l))$

（2）对于其他的所有点，攻击者以$(0,\phi(i))$来询问$LR-oracle$，用$c_i$作为返回值

3.当算法$S^\prime$结束后，算法$\mathcal{A}$调用区分器$D$并把$S^\prime$的输出作为区分器的输入，区分器输出什么，算法$\mathcal{A}$输出什么

此时我们发现，当$LR-oracle$随机选择bit是1的时候，承诺与$S^\prime$相同，0的时候，与$S$相同。

$Pr[LR-commit_{Com,\mathcal{A}}(1^n)=1|b=1]=Pr[D(G,z,S^{\prime V^*(G,z,r,\cdot)}(G,\phi))=1]$

$Pr[LR-commit_{Com,\mathcal{A}}(1^n)=1|b=0]=Pr[D(G,z,S^{\prime V^*(G,z,r,\cdot)}(G,\phi))=0]$

于是我们有：

$Pr[LR-commit_{Com,\mathcal{A}}(1^n)=1]\ge \frac{1}{2}+\frac{1}{2p(n)}$

最终，我们得到：

$\{output_{V^*}P(G,\phi),V^*(G,z)\} \stackrel{c}{\equiv} \{S^{V*(G,z,r,\cdot)}(G)\}$

关于证明技巧的讨论。

首先够造模拟器，然后找到模拟器与现实证明者之间的区别，如果这些区别能够一次证明不可区分，那就一步即可证明，如果不能的话，就将这些区别划分成多个能够证明的不可区分。然后逐步调整不同点，从模拟器到真实情况一点一点地变换过去。这种技术也被称为混合论证（hybrid argument）。除了模拟证明以外，还有一种经典的证明方式是游戏证明（game-based proof）。模拟证明与游戏证明的区别在于，模拟证明是从先构造模拟器，然后从理想情况一点点转移到真实情况中，而游戏证明是从真实情况一点点转移到一个理想的情况中。

Constant-Round Zero-Knowledge

我们将三着色问题进行修改，将其变成一个常数轮的协议。

当我们简单地考虑并行运行$n\cdot |E|$轮协议的时候，但我们根本无法证明这仍然是零知识。

当并行时，证明者一次性发送$n\cdot |E|$份承诺，验证者一次性向证明者发送$n\cdot |E|$条随机的边，但此时rewind不再适用，在并行下，模拟器一次想要猜对的概率是$|E|^{-n|E|}$。因此，对于这种没有合适的证明方法的方案，可以通过修改协议来使得能够证明成功。这也是一种设计密码学方案的小技巧，有的时候可以通过一些小改变来使得一个方案满足可证明安全。

修改后的协议具体细节如下：

1.证明者选定相关perfectly-hiding承诺的信息并发送给验证者，用$Com_h$表示

2.$V$选择$N=n\cdot |E|$条随机的边，$e_1,...,e_N\in_RE$，$q=(e_1,...,e_N)$是query字符串，$V$用$Com_h$来隐藏$q$

3.$P$准备$N$份像非常数论的协议的承诺，$Com$发送给$P$

4.$V$decommit $q$

5.如果验证者的decommit是无效的，那么证明者直接abort。否则证明者对于query的每一条边都decommit。

6.验证者当且仅当所有的检查都通过的时候，输出1。

其中值得注意的是，验证者发给证明者的承诺是perfectly hiding的，而证明者发给验证者的承诺是perfectly binding的。

经过这样修改的协议可以确保验证者在承诺后是无法更改选择的边的，于是模拟器在验证者decommit字符串$q$后就会知道所有挑战值，然后rewind到验证者发完承诺的时候，此时模拟器就相当于提前知道了所有的挑战值，于是模拟器就可以很容易通过挑战了。

但是除此以外还有一些细节需要说明，也就是对于发生中止的情况要单独考虑进来。首先要考虑的就是验证者在decommit字符串$q$的时候是无效的，所以会发生abort。这存在的问题是，验证者的decommit阶段是在rewind之后，那么可能会出现，验证者第一次decommit是正常的，模拟器也从中获得了所有挑战值，但是在模拟器rewind以后，第二次验证者decommit无效导致模拟器中止。看似这种情况并不会对协议产生影响，但是这样会导致模拟器产生abort的概率与真实情况下产生abort的概率不同（因为模拟器需要两次都通过才能不abort），那么势必会导致产生的分布是可区分的。更糟糕的是，无法像非常数轮那样，即使验证者发送的decommit无效，证明者也继续运行，并将无效的边视为某一条默认的边。因为如果这样做的话，如果验证者decommit无效，模拟器就没有办法准备正确的挑战边，那么一次rewind将无法保证能够顺利通过挑战。因此，解决这个问题的方法是如果第一次abort了，那模拟器就直接abort，如果第一次没abort，那么无论接下来就不去理会验证者发来的commitment是否能够decommit成功（如果decommit不成功就继续循环直到成功），因为此时已经知道了对应的挑战值。

剩下的需要关注的点在于，verifier使用的commitment scheme是perfectly hiding的，所以最多只能是computationally binding，也就意味着$V^*$有可能decommit出有效的值$q^\prime=q$，但此时simulation就失效了。因此需要把这部分情况考虑进来，用归约的方式把这部分证明。

另一个需要注意的问题在于，模拟器的运行时间可能并不是期望多项式时间的。假设验证者$V^*$不abort的概率为$\epsilon$，那么我们可以估算出模拟器的运行时间大概为$poly(n)\cdot(1-\epsilon(n)+\epsilon(n)\cdot\frac{1}{\epsilon(n)})$ ，但实际上需要考虑到commitment并不是perfectly hiding的，所以一旦恶意验证者是可以区分commitment的话，那么验证者可以只要判断收到的是garbage commitment就可以一直abort，令模拟器永远无法通过挑战。所以真正计算运算时间的时候应该把这部分概率考虑进去，即$poly(n)\cdot(1-\epsilon(n)+\epsilon(n)\cdot\frac{1}{\epsilon(n)-\mu(n)})$ 。看似这个式子仍然可以满足期望多项式时间，但如果$\epsilon(n)$的概率值与$\mu(n)$的概率过于接近的话，运行时间将可能会是指数级别的。有关运行时间的问题是一个共性问题，一旦rewind前后的分布是不同的（即使不可区分），而且想要整个模拟继续运行下去需要攻击者达到某种条件（比如，攻击者不能abort），那么就都可能会面临这个问题。

安全性证明

令$Com_h$是一个perfectly-hiding承诺机制， $Com$是一个perfectly- binding 承诺机制，它们都具有对于non-uniform概率多项式时间攻击者算法下的安全性。那么上述常数轮的协议满足黑盒计算零知识安全性（模拟器的运行时间是期望多项式时间）

证明：

我们给出模拟器的构造

1. 模拟器$S$调用$V^*$并选定相关承诺的信息输入进去。

2. 模拟器$S$得到验证者$V^*$的commitment$c$。

3. 模拟器$S$发送给$V^*$garbage commitments然后获得$V^*$的decommitment输出。

4. 如果decommitment是无效的，那么直接中止。否则，把decommited的字符串表示为$q=(e_1,...e_n)$，并执行以下步骤。

5. 模拟器 $S$ rewind到最开始并获得了commitment $c$ （因为 𝑉∗ 的random tape是固定的，所以 $c$ 是一样的，那么就能确保 $q$ 是一致的）：

6. 1. 模拟器 $S$ 生成 $N$ 个承诺向量 $\vec{c_1},...,\vec{c_N}$ 。选择验证者挑战的边设置为不同的着色，其余的着色均是0（garbage值）。模拟器将承诺向量发送给验证者$V^*$，并得到回复。
   2. 如果 $V^*$ 没有生成有效的decommitment，那么模拟器 $S$ 回退到前一步（用新的随机性）。
   3. 如果 $V^*$ 生成有效的decommitment但是 $q^\prime \ne q$ ，那么模拟器 $S$ 输出ambiguous并中止。
   4. 否则，$V^*$ 退出循环并进行到下一步。

7. 模拟器 $S$ 向 $V^*$ 继续发送对应点的decommitment，然后输出 $V^*$ 的输出。

然而目前的模拟器构造还不够，因为还没有解决运行时间超过期望多项式时间的问题。