这篇博客，是关于第九届BIU密码学冬令营上的内容，这篇博客是第二篇，会持续更新。 01.Introduction to Zero knowledge --Alon Rosen [零知识证明介绍]的链接如下： https://blog.csdn.net/qq_43479839/article/details/112985426 也可以在我之前的这篇博客中，去寻找一些关于其它知识点的博客，下面的博客链接是我整个内容的目录博客，如果有其它内容的需要，可以去翻阅，下面是博客地址。 https://blog.csdn.net/qq_43479839/article/details/112946344 下面正式开始第二部分关于NP问题上的零知识介绍。

Perfect ZK:简单的来说就是，其能拥有一个Simulator，它能模拟出与(x)交互中同分布的对话。其中V是任意概率性且具有多项式时间验证[PPT]的V,【PPT=Probabilistic Poly-time】 P*：不诚实的Prover； V*：不诚实/恶意的Verifier；

我们为什么要关系这个问题，就是因为SAT是因为NPC问题【NP完全问题】，在之前我的博客有说，所有的NP问题都可以规约到一个NPC问题；如果SAT这个NPC在ZK中证明，那么所有L∈NP的问题来说则都是可以使用ZK证明的。 在目前，我们可以想到对于零知识这个定理的俩种可能的实现。但是现在我们要将PZK这个定理中的一些要求放松【可能是为了更贴近现实或者其他的原因】，如下： 这节课主要讲对indistinguishability上的，后面讲对于soundness【这是对不同的attack而设定的】

统计上的不可区分：【下面是完备的perfect不可区分以及统计上的不可区分的对比，如下：】，给出这俩个不可区分 其中完全【perfect indistinguishability】不可区分指的是：第一个分布落在这个子集中的概率和第二个分布落在这个子集中的概率是相同的。但是在perfect indistinguishability这么严格的区分能力的要求下，很多知识不可能实现，所以需要放松要求 Indistinguishability的对比之后,然后给出统计上的ε-Indistinguishability上的一些性质：X和Y在ε的概率上不可区分 1>给出统计上的不可区分上的三角不等式（Triangle inequality）的性质，如下：【其实我感觉是传递性】 2>以及在统计上的不可区分的多重样本的性质： 3>Hybrid Argument 混合式论证： 这个方式在Boneh那本书中的好几个证明都有用到这个思想。 后面使用triangle inequality:给出后面ε+ε+…+ε=q*ε；其实在这里我要指出的是这其中的ε是没两个实验之间对比在统计上上不可区分的概率，比如在下面图中i=0与i=1所对应的所列举的X^(q-i) Y Y^(i-1)=…；

在给出Statistical indistinguishability这个概念之后，我们再就可以很清楚的描述SZK的概念。 即一个SZK可以有一个Simulator可以 虽然在一定条件下放宽了要求，不要求完全不可区分，但是SZK还是用于PZK一样的限制，故之后还要进一步放松要求。

我们放松要求，从统计上的区分到计算上的区分。 ε-Indistinguishability：对于统计不可区分， 在Computational Indistinguishability上多了一个时间t【即上该时间t内可区分】，给出这个定义之后，在和上面一样给出计算上不可区分的一些性质。 (t,ε)-indistinguishability：所以两分布在t上不可区分，如果对于所有大小的测试，在时间t内ε内的区分都是可以被区分的。【我们不 关心不能在一个多项式时间内完成的测试，即超过时间t的】 是什么让我们放松了系统的安全性来对抗其他可行的集合？ 1>Triangle inequality：三角不等式仍然成立，就是除了考虑在ε1或ε2上不可区分外，还要考虑其运行时间是否在所要求的时间 2>mutiple samples: 3>Hybrid argument【不是均匀分布】

在这里有一个定理：如果单向函数存在【这是密码硬度的最基本的概念】，则会有所有的NP都可以用CZK证明。

这是协议中的一个基本工具，承诺方案是两个实体之间的俩个阶段的协议， 1、C把自己的承诺加密然后给R。【给了之后就不能改变】，c=Com(m,r),其中r是随机值 2、之后C把解开这个承诺的要是给R，然后R就会知道这承诺到底是什么。 完备性：C总是产生有用的承诺c 我们也允许互动的承诺，在Commit和Reveal阶段都允许交互 承诺一般都会满足两个性质，是binding和hiding。 在这里我们讨论statistically-binding承诺满足统计上的binding和计算上的hiding。即： computational hiding:即m1和m2的承诺分布在计算上是不可区分的。 statically-binding：其实就是说对于一个m所给出的承诺是由绑定性的，即对m1的承诺c1，即在这次承诺中m1和c1绑定了。即到最后对c1解密之后只会得到m1，而不会得到m2。 一些承诺生成的函数。

在这里需要提醒的是，我们可以从任何一种功能中建立起具有统计约束力的承诺， 下面有俩个定理： Theorem 1：如果统计绑定性承诺存在，则如果NP问题可以用CZK来解决。 Theorem 2：如果统计绑定性承诺存在，则有HAM属于CZK。

对于每一个L∈NP问题都可以规约到HAM ，因为HAM是一个NP完全问题。即存在一个可计算的函数f，使得所有x∈L，都能得到f(x)∈HAM。 现在为了去证明L能在CZK中被证明，只需要去证明HAM问题能够在CZK中被证明即可。 下面的图中P，V之间的交互：是将statement x的witness w --》变为 statement f(x)∈HAM的witness g(w)

下面的描述，关于HAM，我觉得我给的资料可能容易理解一些：

Adjacency Matrix【邻接矩阵】的表示如下： 下面是对于HAM问题的交互式证明： 为了证明知道G∈HAM【但不想让V知道除这个之外过多的信息】， π∈S，其中这个π是对G的一个同构置换【这个是说如果你对这个同构的图能找到一个哈密顿环路，则原本的G也能找到一个环路】。然后将对G置换后的进行一个承诺发送给Verifier V ； 之后，当b=0，那么证明者只需要揭示出一条哈密顿环路即可；然后 当b=1时，证明者需要发送π和H，之后验证者验证对G的置换是否等于H；