【非交互式零知识证明】（上）_非交互式零知识证明 都有哪些

在了解非交互式零知识证明之前首先需要了解非交互式证明系统的概念。那么交互式证明系统和非交互式证明系统有什么区别呢下面将给出介绍。

1.交互式证明系统

交互式证明系统的定义

对于语言L∈{0,1}^*以及一对交互图灵机<P,V>其中p拥有无限的计算能力称为证明者V为概率多项式时间的验证者。如果满足以下条件称<P,V>为语言L的交互证明系统

1.完备性Completeness)对于任何公共输入x∈L
$$Pr[(P,V)(x)=1|x\in L]\le 1-negl(|x|)$$
2.可靠性Soundness对于任何公共输入x∈L和任何无限计算能力的证明者P^*
$$Pr[(P\ast ,V)(x)=1|x\notin L]\ge 1-negl(|x|)$$
其中negl(|x|)为一个可忽略函数。

通俗解释

这里我理解的完备性就是对于正确的声明验证者"总是因为是1减去一个可忽略函数"接受。也就是说一个诚实的验证者是能够被一个诚实的证明者用一个真声明来说服。而可靠性指的是对于错误的声明验证者"总是"拒绝。也就是说任何欺骗的证明者都不能够让诚实的验证者相信一个错误的声明。

在计算机复杂性理论中交互证明系统Interactive proof system是一种抽象机器其将计算建模为两个参与方证明者和验证者之间的消息交换。通过交换信息参与方证明某个声明x∈L成立。其中

证明者Prover拥有无穷的计算能力且不可信

验证者Verifier拥有受限的计算能力概率多项式时间且诚实。

而交互式就是证明者与验证者之间采用交互的形式来完成证明过程。

交互式证明系统的过程如下

相比之下传统的数学证明系统是这样的

相比而言传统数学证明存在两个特点

1.证明是短而简洁的。因为验证者没有很多精力去读很长的证明。

2.验证者可能获取一些知识。比如证明者所采用的定理、证明的方式等等一旦验证者获取了证明那么它也可以向其他人证明。

交互证明系统可以改变上述两个特点使其能够满足密码学的需求。

2.零知识证明

知道了非交互式证明系统离我们的非交互式零知识证明又进了一步下面介绍零知识证明

零知识证明的定义

对于语言L∈{0,1}^*以及一对交互图灵机<P,V>其中p拥有无限的计算能力称为证明者V为概率多项式时间的验证者。如果满足以下条件称<P,V>为语言L的零知识交互证明系统

1.完备性Completeness)对于任何公共输入x∈L
$$Pr[(P,V)(x)=1|x\in L]\le 1-negl(|x|)$$
2.可靠性Soundness对于任何公共输入x∈L和任何无限计算能力的证明者P^*
$$Pr[(P\ast ,V)(x)=1|x\notin L]\ge 1-negl(|x|)$$
3.零知识性Zero-knowledge)对任意概率多项式时间验证者V^*都存在一个概率多项式时间的模拟器S使得任意的x∈L
$$<P,V\ast >(x)\approx cS(x)$$
其中negl(|x|)为一个可忽略函数≈_c表示计算不可区分。

通俗解释

简单来说零知识证明就是证明者prover能够在不向验证者verifier提供任何有用的信息的情况下使验证者verifier相信某个论断是正确的。所谓零知识通俗的来讲就是既证明了自己想证明的事情同时透露给验证者的信息为“零”。零知识证明可以分为交互式和非交互式两种。

上述三个性质可以这样理解

完备性若断言为真则验证者总是接受证明

可靠性若断言为假则验证者总是拒绝证明

零知识即验证者无法从该证明过程中获取额外的信息。

3.交互式零知识证明典型应用

知道了零知识证明和交互式证明系统之后我们来看看交互式零知识证明的两个典型应用然后将与非交互式作出比较。
首先来看一下NP问题中的零知识证明

一图同构问题

图同构Graph Isomorphism定义

公共输入两个同构的图G₀V,E₀和G₁V,E₁。

假设存在一个映射φ使得G₁=φG₀那么证明者要向验证者证明这一点而不会透露φ的信息具体的零知识交互证明过程如下

1.首先证明者随机产生一个置换π并计算图H=πG₁然后证明者将H发送给验证者

2.然后验证者随机生成一个比特值α∈_R{0,1}并将α发送给证明者

3.随后证明者根据α做出不同的相应

· 如果α=1证明者发送β=π给验证者

· 如果α=0证明者发送β=πφ给验证者

4.最后验证者这边计算

· 如果α=0那么βG_α=πφG₀=πG₁=H验证通过

· 如果α=1那么βG_α=πG₁=H验证通过。

我们可以看到泄露的信息只有π或者πφ由于π是随机产生的模拟器可以模拟证明者和验证者之间的交互并且交互信息和真是交互是计算不可区分的。

二哈密顿回路问题

密顿回路的定义

哈密顿难题给定一个图G找出该图的一个哈密顿回路。

公共输入一个无向图G定点数量为n。

具体的零知识交互证明过程如下图所示

1.首先证明者随机加密n个定点即产生一个随机置换将N₁,N₂,…,N_n映射成为B₁,B₂,…B_n然后设置B_ij的值如果(Bi,Bj)是一条边则B_ij=1否则B_ij=0。证明者将B_i和*B_j放入n+Cⁿ₂*个黑盒中并发送给验证者

2.验证者随机生成一个比特值α∈_R{0,1}并将α发送给证明者

3.证明者根据α做出不同的响应

· 如果α=0证明者把打开所有黑盒的钥匙和置换都发送给验证者

· 如果α=1证明者把打开一个HC回路*(B_ij,B_jk,B_kl,…,B_ti)*的钥匙发送给验证者

4.验证者根据α做出不同的验证

· 如果α=0验证者打开所有的黑盒并验证其中一个是否是G的同构上面已经介绍过同构的概念如果不是则拒绝

· 如果α=1验证者打开指定的黑盒验证是否所有打开的*B_ij*都是1,。如果不全是则拒绝。如果未拒绝进行下一轮证明。

我们可以看到当α=0时验证者获取的仅仅是一个G的同构当α=1时验证者确实得到了对应图的哈密顿回路但其中的映射并未透露所以验证者仍然无法获取G的哈密顿回路这就是零知识证明。

现在已经get了交互式零知识证明距离非交互式零知识证明越来越近啦我们下期再见敬请期待

ps本人也是小菜鸡一枚有什么不对的地方欢迎批评指正(｀・ω・´)