概述

时至今日,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