前言

之前在番外篇的故事里面，提到了这样一个方法

以色列的一些研究人员观察到，通过使用几个秘密并同时进行测试，可以减少录像磁带中场景的数量

那么以色列研究人员的方法是，同时执行很多个测试，比如同时执行四十个测试，如果说对方不知道秘密，那他同时通过四十个测试的概率是极小的（$\frac{1}{2^{40}}$），这四十个测试中只要有任何一个测试没有通过，那Verifier就可以直接拒绝Prover，只有当全部通过时，Verifier才接受Prover

这其实是一个空间换时间的做法，同时执行多个测试，意味着Prover和Verifier之间的通信量会增加到原来的数倍，本来Prover和Verifier只是传输协议执行一次的信息量

也就是P只需要承诺置换图中的哈密顿回路、置换与置换后的图，而Verifier只需要返回其随机选择的一个比特（V^*^(c)可以视为Verifier对承诺值c作用的一个函数，其输出一个随即比特）

然后Prover对Verifier返回的比特，其揭示其中一个承诺即可

但是按照零知识协议，每轮的错误概率为1/2，那么如果验证者需要将错误概率降低到一个可忽略小的量，则需要连续执行很多次零知识协议（在故事里执行了40次），接下来介绍一个同时执行多次的方法

并行运行协议

根据上述的说法，并行可以减少交互的次数，但是代价是每次发送的信息量会成倍的增加

不过暂时不考虑通信的问题，接下来先看看如何实现

假设并行执行k个协议，那么首先Verifier承诺一个长度为k的串b

$$ b\in_R\{0,1\}^k $$

意思就是，这个k比特长的串，每一个比特都对应一个协议中的单比特承诺

之后Prover需要随机选择k个图G的置换，并对这k个置换做承诺，也就是

$$ G_0=\pi_1(w),...,\pi_k(w) \\ G_1=\pi_1,\pi_1(G),...,\pi_k,\pi_k(G)\\ c=Com(G_0,G_1) $$

相同的下标代表相同的协议

之后Verifier和Prover分别解开自己的承诺，总的来说就是下面这个图

分析一下这个过程中零知识性质，显然协议是完备性的

接下来看可靠性，这个协议的可靠性依赖于承诺的隐藏性，且如果Prover不知道哈密顿回路，则$G_{b_1},...,G_{b_k}$全部都是合法的概率为$2^{-k}$

对于零知识性，显然对于给定的b~i~而言，可以确保$G_{b_i}$是合法的

但是这个协议存在个问题，对于这个协议的可靠性，如果说承诺是计算隐藏的，而不是统计隐藏的，则协议会受到中间人攻击（可靠性需要要求对于任意恶意的Verifier，都要求其不能攻破可靠性，包括计算无界的）（~~而且这个基于计算隐藏的协议在受到中间人攻击的时候，不会攻破完备性，只会攻破可靠性）

并行协议中的模拟

和单次协议执行其实差不多，具体来说就是下面这个图

首先Verifier发送一个长度为k的串$b\in_R\{0,1\}^k$，之后到Prover进行承诺，由于Simulator不知道知识，因此只能承诺一个全零的串garbage（这里和之前模拟那篇文章中介绍rewind是一样的，Zlice不知道图的三染色方案，只能将图全部涂成灰色，这里的Simulator不知道哈密顿回路，因此只能承诺一个全零的串）

当Verifier解开他的承诺后，Simulator进行rewind操作，根据V解开的承诺b，来重新生成正确的承诺，也就是下面这样

由于承诺是计算绑定性的，因此Simulator进行rewind之后，Verifier不会将d揭示为另一个b'，使得b'≠b（V不能赢得绑定游戏）

但是如果Verifier不打算解开承诺呢？比如说Verifier在收到Prover（Simulator）的承诺后，他不想解开承诺，或者他bug了，或者其他什么原因，总之就是没有揭开承诺，那咋办呢

这里我们假设$V^*$会以某个概率p$(0\leq p \leq 1)$不打开承诺，简单记为$V^*$终止（Abort），但是为了达到之前提到的不可区分，Simulator在这种情况下仍然需要生成与真实执行相同的分布，下面来看一下怎么做

Verifier终止的情况

这里结合教授的图来讲

还是和之前一样，Simulator不知道秘密，只能承诺garbage，如果说承诺garbage后Verifier直接终止了$(V^*(c)=ABORT)$，那就结束了，因为这是个终止的Verifier，不能输出正确的分布，也没必要继续模拟了

如果Simulator承诺garbage后，Verifier没有终止$(V^*(c)\neq ABORT)$，那就和之前一样，执行下面三个步骤

  • a) Simulator进行rewind操作，利用Verifier解开的承诺，将原来的garbage修改为合法的承诺串
  • b) 获得Verifier的承诺串
  • c) 之前提到了，因为$V^*$会有概率p终止，因此步骤a和b中$V^*$也可能会终止，所以Simulator需要反复窒息你个步骤a和b，直到$V^*$不再终止，则结束

那么分析一下这个过程，假设Verifier收到garbage的承诺串后不终止的概率为$s(n)$，收到valid的承诺串后不终止的概率为$t(n)$，也就是下面这样

$$ s(n)=Pr[\ V^* \neq ABORT \ |\ garbage \ ] \\ t(n)=Pr[\ V^* \neq ABORT \ |\ valid \ ] $$

那么在这种情况下，思考一下Simulator需要重复步骤a和b多少次

假设$s(n)$=1，也就是Verifier收到garbage的承诺之后不会终止，那么重复的次数只和$t(n)$​有关，此时重复的次数的期望应该是

$$ E[步骤(a),(b)重复的次数]=\frac{1}{t(n)} \tag1 $$

此时若$s(n)\neq 1$，再带到上面这个式子，就可以得到重复的次数

$$ E[步骤(a),(b)重复的次数]=\frac{s(n)}{t(n)} \tag2 $$

之前提到Simulator（Prover）的承诺是隐藏性的，因此实际上Verifier看到garbage承诺和valid承诺时，两者的区别是可忽略的，那Verifier对两者做出的行为也是可忽略的，也就是$s(n)$和$t(n)$是可忽略的

比如说对于一个很大的n而言，$s(n)=2^{-n}$，以及$t(n)=2^{-2n}$，显然s和t之间是可忽略的，但是此时再带到上面的式(2)，则会得到需要重复$2^n$次

为了解决模拟器可能会重复很多次的问题，Oded Goldreich和Ariel Kahan给出了一个方案$[6]$，可以通过估计$t(n)$的大小来减少重复的次数，具体如下

首先，Simulator执行rewind多次，得到一个关于t(n)的估计$\tilde t(n)$

然后使用合法的承诺值rewind若干次（如$poly(n)$次）

之后在步骤c中，只需要重复步骤(a)和(b)$\frac{poly(n)}{\tilde t(n)}$次，除非Verifier再次不终止

另一种解决方案

如果我们能避免对garbage的承诺呢，这样理论上来说可以再减少一次交互，Alon Rosen教授在04年提出了另一种解决方案$[7]$，简单来说就是Verifier在完成第一阶段的承诺后，Prover在发送自己的承诺前，就可以从Verifier的承诺中得到b

接下来看一下具体的操作过程

第一阶段：

  • 首先，Verifier和之前一样，对$b\in_R\{0,1\}^k$进行承诺
  • 然后Verifier选择n对长度为k的串（一共2n个串）

$$ \left [ \begin{matrix} b^0_1 , b^0_2 , ... , b^0_n \\ b^1_1 , b^1_2 , ... , b^1_n \end{matrix} \right ] $$

且满足：对于$\forall i \in [n]，b^0_i\oplus b^1_i = b$

  • Prover向Verifier发送一个长度为n的随机比特串$r_1,...r_n \in \{0,1\}^n$
  • Verifier根据Prover提交的串，解开承诺$b^{r_1}_1,b^{r_2}_2,...,b^{r_n}_n$

第二阶段：

  • Verifier解开第一阶段剩余的承诺$b^{1-r_1}_1,b^{1-r_2}_2,...,b^{1-r_n}_n$，同时Prover验证这些承诺是否都满足第一阶段中的条件：$\forall i \in [n]，b^0_i\oplus b^1_i = b$，如果任意一对承诺串不满足，则Prover终止
  • 若验证通过，则P和V根据第一阶段中承诺的串$b$完成三轮哈密顿零知识证明（并行版本）

也就是下面这个图

（可以思考一下第一阶段中满足$b^0_i\oplus b^1_i = b$的串一共有多少对）

然后看一下模拟器在这个方案中怎么操作的

和之前一样，Simulator需要进行rewind操作，在rewind之前，Simulator发送的随即比特串只能知道每一对承诺串中的其中一部分，也就是这样

对于独立的随机比特串，Simulator不可能同时知道$b^0_i和b^1_i$

但是rewind之后，Simulator可以发送另外的比特，就像下面这样

rewind之前，Simulator在第二组承诺串中选择了$b^0_2$（也就是随机的串中第二位为0），对于rewind之后，即便是随机选择的串，Simulator也有很高的概率随机到至少一个满足要求的组（这里示例是随机到了$b^1_2$，也即rewind之后随机串第二位为1），根据之前的条件，对于任意的i，等式$b^0_i\oplus b^1_i = b$均成立，因此Simulator就可以恢复出承诺b，而且Simulator不再需要对garbage承诺，也不再需要将garbage修改为valid

因此，Simulator通关rewind操作，到这一步之前（也就是发送自己的承诺之前），就可以知道承诺的内容了

对比之前承诺方案：之前的方案需要先发送对garbage的承诺，然后等Verifier返回，然后再将garbage修改为valid，再发送valid的承诺，Rosen的方案在Simulator发送承诺之前就可以知道承诺$b$的内容了，而知道b之后，Simulator就可以完成第二阶段的零知识证明了

还有需要注意的是，这个方案对现实世界的协议执行者也是可行的，因为现实世界中Prover和Verifier没有rewind的能力（详见模拟那篇文章），因此在Prover提交随机比特串后，Prover只能知晓每一对承诺串中的其中一个，无法同时知道两个，因此不会打破可靠性

但是这个方案中，rewind是非自适应的（non adaptive），非自适应的意思是不能根据之前的串来最优化下一个串，因为Simulator进行rewind操作之前和之后，随机比特串$r_1,...r_n$的选择都是完全随机的，也就是rewind之后不能选择和rewind之前完全相反的比特串，虽然完全随机的，但是随机到和之前完全一样的串的概率比较小

不过这个方案中，Simulator不再需要对garbage承诺了，也不需要修改garbage为valid，此时前面提到的两个概率$s(n)和t(n)$就是常数了，因此这个方案中，如果Simulator再遇到之前Verifier终止的情况，则需要重复的次数就是常数了，不会出现需要重复一个很大的次数的情况

Proof of Knowledge

到目前为止，可靠性都是用模拟器来证明的，因此称为Zero Knowledge，如果说用之前提到的抽取器来证明系统的可靠性，则被称为Proof of Knowledge，不过并不是所有的可靠性都要求存在抽取器算法，所以之前主要讲的都是模拟器

接下来讲一下抽取器怎么证明这个方案的可靠性

对于抽取器，为了抽取出Prover的知识，因为$G_0$包含置换后的图的哈密顿回路，$G_1$包含置换和置换后的图，因此Verifier需要对相同的承诺c，其通过rewind操作，同时获得基于同一个c的$G_0和G_1$

但是没这么简单，因为Verifier（也就是Extractor）在Prover发送承诺c之前先对b进行了承诺（上图中的$d=Com(b)$），而Prover的承诺c很有可能是基于Verifier的承诺d，因此Verifier不能在rewind中完成在不修改c的条件下修改自己的d，也就是说，如果Extractor为了修改b，rewind到了第一步，则会导致Prover也修改了c，这样Extractor得到的就和rewind之前不是同一个c，也就不能完成知识的抽取了

为了解决这个问题，Lindell教授给出了解决方案$[8]$，具体如下

  1. Prover和之前一样对$G_0和G_1$承诺
  2. Verifier承诺一个长度为k的随机串$b_1 \in_R \{0,1\}^k$
  3. Prover承诺一个长度为k的随机串$b_2 \in_R \{0,1\}^k$
  4. Verifier解开对$b_1$的承诺
  5. Prover解开对$b_2$的承诺，同时解开对$G_{c_1},...,G_{c_k}$的承诺，其中$c=b_1\oplus b_2$

上述语言描述画成图就是下面这样

后记

这篇写了好长，四千多字十来张图，一点点啃完，主要是rosen教授口音有点诡异，一段话要反复听好多次，然后再加上理解，所以听得有点久

不过一边看论文一边听这个，结合起来，慢慢的听的也就快了，也摸到点门道了，趁着自己还有兴趣，学完，万一以后做这个方向呢，也不是不行

参考文章

$[1]$ 陈原。计算复杂性理论导引 $[M]$. 西安电子科技大学出版社.

$[2]$ （以）Odeb Gol­dre­ich 著；温巧燕，杨义先译。密码学基础 $[M]$. 北京：人民邮电出版社.2003.

$[3]$ Cyn­thia Dwork, Moni Naor, Amit Sa­hai:Con­cur­rent Zero-Knowl­edge. STOC 1998: 409-418

$[4]$ The 9th BIU Winter School on Cryptography | BIU Cyber Center

$[5]$ 探索零知识证明系列3 - 寻找「知识」 | 登链社区 | 深入浅出区块链技术 (learnblockchain.cn)

$[6]$ Oded Goldreich, Ariel Kahan:How to Construct Constant-Round Zero-Knowledge Proof Systems for NP. J. Cryptol. 9(3): 167-190 (1996)

$[7]$ Alon Rosen:A Note on Constant-Round Zero-Knowledge Proofs for NP. TCC 2004: 191-202

$[8]$ Yehuda Lindell:Constant-Round Zero-Knowledge Proofs of Knowledge. Electron. Colloquium Comput. Complex. 18: 3 (2011)