为神马ZK的证明要用Simulator来定义?

首先注意一个信息$I$的私密性是和破解者$A$的计算能力有关的。比如说$x = w^2 \,mod\, n$是二次剩余(QR),其中$x$是公开的而$w$是私密的(即$I = \{w\}$)。那么普遍认为一个多项式时间的$A$是不能算出$w$的。如果我们定 义$A$关于$I$的知识为$K_A(I)$,那么在$A$为多项式时间的前提下,$w$的具体值是不包括在$K_A(I)$中的。那$K_A(I)$包括了什么呢? 虽然$A$不能算出$w$的具体值,但是$A$可以取$w’$且算出$w’^2$。如果$w’^2 \neq x$,那么$A$知道$w \neq w’$,这就可以 看成是$K_A(I)$中的元素。当然$A$可以取不同的$w’$,甚至可以采用不同的多项式算法,得到不同的关于$w$的知识,这些都是$K_A(I)$中的元素。

如果我们允许$A$运行任意长时间,那么$A$可以枚举所有的$w’$并计算$w’^2$,找出使得$w’^2 = x$的$w’$,于是$A$知道$w$只能在这些 $w’$中取值。显然这个可以运行任意长时间的$A$获得的知识不少于只能运行多项式时间的$A$,也就是后者的$K_A(I)$是前者的一个子集。

当然,即便是这个可以运行任意长时间的$A$,也不能精确地算出$w$是什么,所以即便对于计算能力任意强的破解者$A$,也有些知识不属于其$K_A(I)$。

然后考虑验证者$V$与证明者$P$的交互。什么叫做零知识?就是说$V$与$P$交互之后$K_V(I)$没有变化。那么$V$如何从与$P$的交互中学习新的知识 呢?$V$与$P$交互和不交互的区别,只是多了一份通讯记录$H$以及在这份通讯记录中$V$产生但未发送的随机位$R$(发送的随机位算在$H$里了)。$\la ngle H,R \rangle$实际上服从一个分布$D$。如果$V$自己可以在规定时间内得到分布$D$,那么$V$就没有从和$P$的交互中获得额外的知 识(知识是通过消息的分布来传递的)。零知识指的就是没有这些额外的知识。

实际上$D$的计算是由Simulator来做的。注意到Simulator的时间限制不能比$V$更松,因为Simulator要被$V$调用。因为通常我 们都考虑$V$的限制为多项式时间的情况,所以Simulator也被限制为多项式时间。如果满足条件的Simulator存在,那么$V$就可以自己生成$\lan gle H,R \rangle$。$V$只需运行Simulator然后采用其输出即可,因为Simulator就是按照$D$来输出的。

既然Simulator要被$V$调用,为什么Simulator的构造中却可以调用$V$的策略呢?究竟是谁包含谁呢?其实可以把Simulator想象成一个带有 回调函数指针的工具,而$V$是一个人,$V$调用Simulator的时候遇到回调函数指针就用自己的策略作为回调函数代入。这一般都是为了保证Simulator 能顺利计算出$V$发送的消息的分布。

值得一提的是,在computationally indistinguishable的意义下,允许Simulator的输出有小概率出错(即不服从实际$D$的分 布)。Simulator输出的分布反映了$V$原本的知识,实际的$D$反映了$V$从$P$那里获得的知识,这两个分布越相似,说明$V$从$P$那里获得的新知 识越少。Simulator出错的概率足够小,就说明获得的新知识足够少。

最后有一个问题没有解决。考虑CCA-secure的公钥加密系统$(p_k,s_k)$。$P$要向$V$证明自己有私钥$s_k$但不让$V$了解关于$s_k$的知识。交互式证明协议如下:

  1. $V$ to $P$: Uniformly choose $m$, send $c = Enc_{p_k}(m)$
  2. $P$ to $V$: send $Dec_{s_k}(c)$

看起来像是ZK的但是不知道怎么构造Simulator。首先第一步只能调用$V$的策略,但是$V$可以是邪恶的,可以完全不生成$m$而直接随机选取$c$。于是 第二步就不知道怎么回了。猜的话概率是$1/2^{|m|}$指数小,也就是期望猜中的步数是$2^{|m|}$,指数级别,不是多项式了。难道说不是ZK的么?不是 ZK的话还真不知道有什么形式化的证明。构造不出来Simulator这个应该是不能算证明的……