概述

时至今日，ZK仍然非常的coooooooooool，但是通过其定义可知，其不仅依赖于于一些问题的难解性，更重要的是，其依赖于参与双方的交互和蕴含在其中的随机性（Verifier的本地掷币）

因此，自1986年起，就有学者在研究对于交互式的ZK而言，到底有多少的互动是必要的，如果可以有一种完全不需要交互的方法就好了，就像广播一样，Prover单方面的向Verifier发送一些消息，就可以使得Verifier相信其断言是真的，且同时又保持着零知识性

非交互证明在某些领域还是有非常多的应用场景，比如在网络上发布证明，或者区块链中的工作量证明之类的

但是有个很可惜，有一个如下断言拦着我们

  • Claim：如果语言$L$有一个ZK证明系统，其中Prover仅向Verifier发送一条单一的消息，则$L\in BPP$

上述断言意味着，这类的非交互式零知识证明是平凡的，只能证明$BPP$中的语言

Non-Interactive Zero-Knowledge

最早由Blum、Feldman、Micali在1988年提出$[BFM88]$，其中的关键思想是提出一种新的概念，称为可信设置（Trusted Setup）

可信设置的典型模型为公共字符串模型（Common Reference String，CRS），$CRS$模型中，在互动开始前，可信的参与方会生成一个公共字符串$CRS$，该串对所有的参与方都是可见的，但是生成之后是不可修改的，从而协议的参与方可以基于该$CRS$完成进一步的交互，更进一步的，可以将$CRS$改进的更好，使其变为公共均匀随机串（Common Uniform Random String，CURS），由一段公共的完全随机的字符串构成

NIZK：定义

和往常一样，由Prover和Verifier构成，其中Prover有额外输入$w$，但和交互式ZK不同的是，加入了上述提到的$CRS$，Prover和Verfier都可以访问这个$CRS$

因此在有CRS的条件下，Prover可以生成一个证明$\pi$，并将其发送给Verifier，V收到$\pi$后，会结合CRS完成一些相关的验证操作并决定是否接受Prover，就像下面这个图一样

和交互式ZK一样，NIZK有三个性质

  • 完备性（Completeness）：若$x \in L\Rightarrow Pr[V\ accepts]=1-negl$
  • 合理性（Soundness）：若$x \notin L,\forall PPT \ P^*, Pr[V\ accepts]=negl$
  • 零知识性（Zero-Knowledge）：无论Verifier看到什么，都可以模拟他的视角，也即$Sim(x)\approx ^c (CRS,\pi)$

一些思考

根据上述的介绍，在有了$CRS$和$\pi$后，似乎Verifier可以再向另一个人证明$x \in L$，而传统的交互式零知识证明是绝对不可能做到这一点的，这看起来很酷

但是这么做的话，Verifier本身确实相信了，但是他又分享给了其他人，这个过程为什么会是零知识的？实际上对于Verifier而言，其知道的内容只是关于这个特定的$CRS$的，而不是直接关于公共输入$x$的，因此NIZK实际上还是非常具有实际意义的协议

一些错误的结果

  • 断言：如果语言L有一个$CRS$模型下的NIZK，则$L \in BPP$

这个断言中，显然NIZK的完备性是成立的，问题出在其合理性，因为引入了$CRS$，因此实际上并不知道模拟器在模拟Verifier的视角的时候会怎么做，更具体来说，合理性要求若$x\notin L$，V会以可忽略的概率接受P，但由于引入了$CRS$，合理性在对正确分布的$CRS$是完全正确的，而对于运行在$x\notin L$上的模拟器而言，其生成的$CRS$和协议实际执行中的$CRS$有非常显著的统计差别，故原命题证伪

一些NIZK的应用

  • CCA 安全加密$[NY90]$
  • 唯一签名$[BG89]$
  • 低轮复杂度的MPC$[AJJTVW12]$
  • CS证明$[Micali94]$
  • Mechanism Design$[LMPS04]$
  • 加密货币zk-SNARGS、zk-STARKS$[BCGGMTV14...]$

NIZK变体

  • 对于多个不同的公共输入$x$而言，可以在不同的交互中复用一些$CRS$，比如两个证明之间不同的$x$可以使用相同的$CRS$
  • 适应性合理性：即便是Prover在生成$CRS$后再选择$x\notin L$，合理性仍然成立
  • 适应性零知识性：零知识区分器可以在生成$CRS$后再选择$x\in L$
  • 统计合理性：对于无界的Prover，合理性仍然成立
  • 统计零知识性：对于无界的零知识区分器，零知识性仍然成立

可行性结果

$[Circa2018]$，一个比较教科书式的构建NIZK的方法

在$[FLS90]$中，对于所有的陷门置换（假设其存在），可以构建一个关于NP的NIZK系统

事实上，NIZK是基于整数分解的困难性，基于这个问题，可以构建陷门置换，然后再根据$[FLS90]$的结果构建关于NP的NIZK系统（相关结论：双线性映射$[GOS06]$，随机预言模型，混淆$[SW13,BP15]$，最佳困难假设$[CCRR18,CCHLRR18]$）

一些新的结果：LWE+循环安全$[CLW19]$，LWE$[PS19]$

目前仍未解决的问题：是否可以基于离散对数困难性构建NIZK，就像构建DHKE一样，或者从一些比较常规的假设构建NIZK，比如单向函数之类的

FLS范式

构建NIZK分两步，先构建一个隐藏比特的模型，然后再将其编译（转换）为标准的NIZK模型

隐藏比特模型

一种和CRS类似的模型，但是又有比较明显的区别

和CRS一样，有一个字符串，称为隐藏比特（Hidden Bits，HB），只有Prover可以看到HB的内容，对于这些HB，P生成一个证明$\pi$，同时向Verifier发送一个集合$S$，$S$包含着Verifier可以看到的隐藏比特的中Prover希望其看到的比特，就像下面这样

区别于CRS模型，CRS模型中CRS是P和V都可以看到的，但是HB模型中，P可以看到HB所有的比特，但是V只能看到P希望其看到的比特，换句话说，Verifier可以看到的内容完全取决于Prover

打个比方，HB模型就好像天上的乌云，乌云背后有隐藏的比特，而Prover手上有一副超级眼眼镜和一只激光笔，超级眼镜可以看到乌云后所有的比特，而激光笔可以照射乌云看到后面特定的比特，因此Prover可以使用超级眼镜可以看到所有的比特，也可以利用激光笔照射特殊的位置，使得Verifier只看到某些特殊的比特

对于HB模型中的NIZK，依然采用图的哈密顿性（$HAM$）判定问题构建，也即给定一个图G，判定其是否存在哈密顿回路（$HAM\in NPC$，故所有的NP语言均有一个HB模型的NIZK系统）

对于HB模型下构建NIZK，其构建是基于信息论的，其中Prover是多项式时间的，但是有这个公共图的一条哈密顿回路，此外证明系统可以做到完美完备性和对无界Prover的完美合理性（对于$CRS$或$CURS$模型中，可能只能做到对无界Prover的统计合理性，做不到完美）

构建方式如下

  • 公共输入：图$G=(V,E)$
  • Prover的额外输入：一条哈密顿回路$H⊆ E$
  • HB：一个由点集V构成的随机的环路图$C=(V_C,E_C)$（以邻接矩阵的形式表示），也就是一个随机的经过点集$V$中所有顶点的图，图$C$除环路外没有别的边

就像下面这个图这样

此时Prover首先找到一个单向映射$\pi:V→ V_C$，也即将V上的点随机映射到$V_C$上的点（根据单向映射的性质，不会破坏原图上环路的结构，因为$G$上有环路，$C$上也有，因此可以找到这样的单射满足这个条件）

然后Prover令集合$S$为映射后的点构成的邻接矩阵（仅包含非边），也即$S⊆ V_C\times V_C$，且满足$S=\pi(V^2 $$ E)$，之后Prover将pi和S发送给Verifier

之后Verifier检查

  1. $\pi$确实是单射
  2. 通过S，对$\forall e \notin E$，其查看Hidden Bits，并检查边$\pi(e)$被正确的标记为非边

Verifier检查的第一步很好理解，第二步的意思是，对于原图G中的所有的非边，其经过$\pi$映射后，映射到$E_C$中仍然是一个非边，若这两步检查均通过，则接受Prover，否则拒绝

这里非常有必要插个题外话，讲一下图的一个知识点

  • 如果图$C$是图$G$的子图（$C\subseteq G$），且$C$仅包含环路，则说明$G$是哈密顿图
  • 上述这句话等价于另一句话：若一个图G是哈密顿图，则$G$的补图$\overline G$是环路子图$C$的补图$\overline C$的子图，也即若$G$为哈密顿图，则有$\overline G\subseteq \overline C$,

然后针对上述协议，讨论NIZK的三个特性

  • 完备性：若上述检查均通过，则Verifier接受Prover的概率为$1-negl$
  • 合理性：先不考虑$x$是否在语言$L$中，先假设V接受了P，此时意味着两点：1)$\pi$确实是一个单射，2)所有$E$中的非边都被正确的揭示了，根据上面提到的图的知识点，有$\overline G \subseteq \overline C$，因此V可以得出结论，$G$是哈密顿图
  • 零知识性：显然Verifier只看到了映射$\pi:V\rightarrow V_C$和$G$中所有的非边，并没有看到$G$中的环路

问题来了，针对这个协议，模拟器如何模拟V的视角

  • 首先选择一个随机单射函数$\pi→[n]$（从1到n的映射）
  • 然后输出$(\pi,S,CRS_S)$，其中$S=\pi(V^2\backslash E)$，$CRS_S=000...00$

那么为什么这个模拟器可以模拟V的视角，首先，对于任何固定的$\pi$而言，在Verifier看来都是对原图的一个映射，且原图中所有的非边都被揭示了，其次，真实协议执行是的映射是一个随机的映射函数，也即这个随机函数$\pi$的分布和真实协议中的映射具有相同的分布，从而模拟器的输出和真是协议执行的输出是一样的

将HB-NIZK编译为标准NIZK

实际上HB模型稍微有些抽象，因为实际协议执行时不存在这么花里胡哨的所谓的乌云和超级眼镜，因此整个编译的过程需要利用密码学工具来将HB模型编译为标准的CRS模型（或者说利用密码学来实现之前提到的乌云、超级眼镜和激光笔），这里主要利用的是陷门置换（Trapdoor Permutation，TDP），但是实际编译的时候使用的陷门置换太过于理想化，目前已知的算法都不满足陷门置换的定义，如果硬用的话可能会导致隐藏比特不再隐藏（但是有一些比较好的关于陷门置换的工作来支持）

理想的陷门置换

  • 定义：一个可以高效计算的置换的集合

$$ \{p_{α}:\{0,1\}^{\lambda}→ \{0,1\}^{\lambda}\}_{{α}\in\{0,1\}^\lambda} $$

其中$α$表示下标，这些置换存在一个PPT算法和给定的$α$和陷门$\tau$满足

  1. 对于随机选择的$α$和$x$，$p_α(x)\nrightarrow x$（计算上困难）
  2. 对于随机选择的$\alpha$和$x$，在给定对应的$\tau$时，$α,p_α(x)\rightarrow x$（有陷门时可以高效地从$p_α(x)$恢复出$x$）

实际编译的时候使用的陷门置换太过于理想化，目前已知的算法都不满足陷门置换的定义，如果硬用的话可能会导致隐藏比特不再隐藏（但是有一些比较好的关于陷门置换的工作来支持）

此类陷门置换的例子不多，RSA和Rabin是大家比较熟知的陷门置换，但是实际上他们并不满足上述这种及其理想的定义，因此不足以应用在标准NIZK的编译中

另一个概念是陷门置换的核心比特，可以高效计算$h:\{0,1\}^\lambda→ \{0,1\},s.t.\ α,p_α(x)↛ h(x)$

编译

CRS包含$l$个长度为$\lambda$的串$y_1,...,y_l\in\{0,1\}^\lambda$，这些串都是$x_1,...,x_l$的置换，然后Prover选择一个陷门置换$TDP(α,\tau)$，然后定义核心比特$b_i=h(y_i)$ ，如果需要揭示某个比特，则Prover只需要发送该比特对应的$y_i$的原像$x_i$


根据上图，Prover具体的过程如下

  1. Prover选择陷门置换$TDP(\alpha,\tau)$
  2. 观察CRS，并定义$x_i=p_\alpha^{-1}(y_i)$
  3. 计算隐藏比特$b_i=h(x_i)$
  4. 使用$(x,w,(b_1,...,b_l))$执行HB-NIZK，并得到置换$\pi$和集合$S\subseteq [l]$
  5. 然后Prover向Verifier发送$\alpha,\pi,\{x_i\}_{i\in S}$

这里说明一下，$S⊆[l]$为$1\sim l$上的某些数字的集合，表示需要揭示哪一个CRS中的$y_i$，也就是HB模型中Prover用激光笔照射的那些期望让Verifier看到的比特

Verifier过程如下

  1. 检查$\alpha$在置换集合中（$\alpha$合法）
  2. 对于$\forall i\in S$，检查$p_\alpha (x_i)=y_i$
  3. 计算$b_i=h(x_i)$
  4. 利用$(x,\pi,\{b_i\}_{i\in S})$，执行HB-NIZK的Verifier，若HB-NIZK输出接受，则原Verifier接受，否则拒绝

然后讨论一下NIZK的三个性质

  • 完备性：根据上述协议，完备性显然成立
  • 合理性：对于合理性，假设$\alpha$是固定的，则隐藏比特也就固定了$b_i=h(p^{-1}_\alpha(y_i))$，其中y_i是从CRS中得到的，这意味着对于任何特定选择的$\alpha$，则隐藏比特是完全确定的，因此此时的合理性与HB模型的合理性相同

但是如果Prover可以灵活的选择$α$，则其会得到不同的隐藏比特的序列，因为如果他选择欺骗Verifier，他将会得到$2^\lambda$个隐藏比特序列而不是一个，然后对于隐藏比特串中的每一个比特而言，其都是来自于不同的$α$，不过我们可以简单的将HB模型执行足够多次，此时的合理性界会降低至$2^{-2\lambda}$（每次运行HB模型，其合理性界都会以指数速度下降）

经过足够多次的执行后，此时Prover找到一个$α$，使其能够欺骗Verifier的概率小于等于每一次执行中Prover使用那次协议执行时的$α$来完成欺骗的概率之和，也即

$$ Pr[∃α on \ which \ P \ can \ cheat ]\leq \sum_α Pr[P \ can \ cheat \ on\ α]\leq 2^\lambda \cdot2^{-2\lambda}=2^{-\lambda} $$

对于足够大的$\lambda$而言，$2^{-\lambda}$可以达到不可忽略

  • 零知识性：显然对于所有的$\{b_i\}_{i\in S}$而言，在协议中这些比特所对应的$y_i$都被正确的揭示了，而对于$\{b_i\}_{i\notin S}$，这些比特仍然保持隐藏，也即这些比特对应的y_i也保持隐藏

其次是模拟器$Sim(x)$的构建，具体如下（不难证明该模拟器$Sim(x) ≈ ^c Real$）

  • 运行HB模型的模拟器$Sim_{HB}(x)$，得到$(\pi,S,\{b_i\}_{i\in S})$
  • 生成$(\alpha,\tau)$
  • 对于所有的$i\in S$，求$x_i$，满足$b_i=h(x_i)$（不断找$x_i$，直到满足这个条件为止），然后令$y_i=p_\alpha(x_i)$
  • 对于所有的$i\notin S$，生成一个随机的串$y_i\in \{0,1\}^\lambda$
  • 模拟器输出$((\alpha,\pi,S),(y_1,...,y_l))$

总结

综上所述，NIZK的构建流程大概是这样

  • 定理：若分解是困难的，则存在一个对所有NP语言的NIZK系统

参考文献

$[1]$ 云中「秘密」：构建非交互式零知识证明——探索零知识证明系列（五）

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

$[3]$ Zero-Knowledge Proof-Wiki

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