零知识证明

“零知识证明”－zero-knowledge proof，是由Goldwasser等人在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息，但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用。如果能够将零知识证明用于验证，将可以有效解决许多问题。

顾名思义，零知识证明就是既能充分证明自己是某种权益的合法拥有者，又不把有关的信息泄露出去——即给外界的“知识”为“零”。其实，零知识证明并不是什么新东西，早在16世纪的文艺复兴时期，意大利有两位数学家为竞争一元三次方程求根公式发现者的桂冠，就采用了零知识证明的方法。当时，数学家塔尔塔里雅和菲奥都宣称自己掌握了这个求根公式，为了证明自己没有说谎，又不把公式的具体内容公布出来(可能在当时数学公式也是一种技术秘密)，他们摆开了擂台：双方各出30个一元三次方程给对方解，谁能全部解出，就说明谁掌握了这个公式。比赛结果显示，塔尔塔里雅解出了菲奥出的全部30个方程，而菲奥一个也解不出。于是人们相信塔尔塔里雅是一元三次方程求根公式的真正发现者，虽然当时除了塔尔塔里雅外，谁也不知道这个公式到底是个什么样子。从这个故事，我们可以初步了解零知识证明的概念。

在有必要证明一个命题是否正确，又不需要提示与这个命题相关的任何信息时，零知识证明系统(也叫做最小泄露证明系统)是不可或缺的。零知识证明系统包括两部分：宣称某一命题为真的示证者(prover)和确认该命题确实为真的验证者(verifier)。证明是通过这两部分之间的交互来执行的。在零知识协议的结尾，验证者只有当命题为真时才会确认。但是，如果示证者宣称一个错误的命题，那么验证者完全可能发现这个错误。这种思想源自交互式证明系统。交互式系统在计算复杂度理论方面已经获得异常独立的地位。

零知识证明(Zero—Knowledge Proof)起源于最小泄露证明。设P表示掌握某些信息，并希望证实这一事实的实体，设V是证明这一事实的实体。假如某个协议向V证明P的确掌握某些信息，但V无法推断出这些信息是什么，我们称P实现了最小泄露证明。不仅如此，如果V除了知道P能够证明某一事实外，不能够得到其他任何知识，我们称P实现了零知识证明，相应的协议称作零知识协议。

在最小泄露协议中零知识证明需要满足下述两个性质。

(1)正确性。P无法欺骗V。换言之，若P不知道一个定理的证明方法，则P使V相信他会证明定理的概率很低。

(2)完备性。V无法欺骗P。若P知道一个定理的证明方法，则P使V以绝对优势的概率相信他能证明。

在零知识协议中，除满足上述两个条件以外，还满足下述的第三个性质。

(3)零知识性。V无法获取任何额外的知识。

我们把性质(1)和(2)称为零知识证明的正确性和完备性，而性质(3)称为零知识性。

零知识证明需要满足三个属性。

1、如果语句为真，诚实的验证者（即：正确遵循协议的验证者）将由诚实的证明者确信这一事实。

2、如果语句为假，不排除有概率欺骗者可以说服诚实的验证者它是真的。

3、如果语句为真，证明者的目的就是向验证者证明并使验证者相信自己知道或拥有某一消息，而在证明过程中不可向验证者泄漏任何有关被证明消息的内容。

零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗者有可能通过虚假陈述骗过证明者。换句话来说，零知识证明是概率证明而不是确定性证明。但是也存在有技术能将误差降低到可以忽略的值。

零知识的形式定义必须使用一些计算模型，最常见的是图灵机的计算模型。

零知识证明不是证明在条款的数学感觉因为有一个固定的可能性p在任一零知识证明Peggy能提供对挑战的正确反应即使她不知道钥匙。但是如果测试被重覆n计时欺诈被减少Peggy的可能性pn,和由增加测试胜者的数字可能使Peggy的可能性降低欺诈到一个任意水平。

Peggy的公开密钥是一张大图表，我们将称G。Peggy被组建的G某时从前，和广泛然后出版它。由于她特别地制造了它为目的,Peggy知道一个汉密尔顿的周期在G。Peggy将证明她的身份对胜者由证明，她知道一个汉密尔顿的周期在G。即使G是公开信息，没人可能做这，因为没人知道G的一个汉密尔顿的周期，并且发现汉密尔顿的周期在图表是一个困难的问题。

但是,Peggy不能简单地显露汉密尔顿的周期对胜者，胜者(或偷听者)从那以后能在将来扮演Peggy。Peggy不能显露任何信息在所有周期，因为偷听者也许收集信息关于几个不同的场合和装配它入足够的信息能扮演Peggy。

证明她的身份,Peggy和胜者扮演以下比赛的几个圆:

Peggy标记G端点以随机号。边缘可能然后代表作为一对这些数字。她列出G边缘，和编成密码各个边缘以一个另外密钥。她然后寄发被编成密码的边缘到胜者。

胜者翻转硬币。

*如果硬币过来头,Peggy向随机号投降密钥和测绘从端点。胜者解码边缘和然后核实，被编成密码的边缘被派在步骤1实际上做graph.g和没有某一其它图表。

*如果硬币过来尾巴,Peggy投降密钥只为实际上形成汉密尔顿的周期的边缘。胜者解码这些边缘和核实，他们的确形成正确长度的周期。

冒名顶替者('Pamela')能设法扮演Peggy,和有成功地唬弄胜者的50%机会在任何尤其圆。有二个可能的扮演战略。Pamela能派Peggy的graph.g的编成密码。在这种情况下，她逃脱侦查如果胜者投掷头；她显露编成密码，并且胜者核实图表的确是G。但如果胜者投掷尾巴,Pamela被捉住。她被要求显露的一套的钥匙组成一个汉密尔顿的周期G边缘，并且她无法做那，因为她不认识一。

Pamela能跟随的另一战略是准备某一其它图表她知道一个汉密尔顿的周期的H编成密码。她在这种情况下是安全的如果胜者投掷尾巴；她显露周期，并且，因为胜者从未看边缘的剩余，他从未获悉图表是H和不是G。但如果胜者投掷头,Pamela被要求显露整个图表，并且胜者看见这不是G。

由扮演这场游戏二十回合，胜者能使由Pamela被唬弄的可能性降低到一仅仅为1/2。由扮演更多圆，胜者能减少可能性就渴望。

信息由Peggy显露提供胜者任何信息在所有不G的汉密尔顿的周期。看这，注意胜者能制造比赛的抄本没有谈话与Peggy根本。他能选择序列头和尾巴，和然后准备假定回复从Peggy,没有曾经知道汉密尔顿的周期，由从事适当的冒名顶替者战略在每个圆。抄本，和它不遏制，有线索关于Peggy的身份合法的信息。Peggy证明她的身份不是因为她能基于正确的答复，但因为她能基于正确的答复没有知道将是什么问题。

所谓零知识证明，指的是示证者在证明自己身份时不泄露任何信息，验证者得不到示证者的任何私有信息，但又能有效证明对方身份的一种方法。看起来有点别扭，我给2个例子，也许好明白一些。

A要向B证明自己拥有某个房间的钥匙，假设该房间只能用钥匙打开锁，而其他任何方法都打不开。这时有2个方法：A把钥匙出示给B，B用这把钥匙打开该房间的锁，从而证明A拥有该房间的正确的钥匙。B确定该房间内有某一物体，A用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给B，从而证明自己确实拥有该房间的钥匙。后面这个方法属于零知识证明。好处在于在整个证明的过程中，B始终不能看到钥匙的样子，从而避免了钥匙的泄露。

A拥有B的公钥，A没有见过B，而B见过A的照片，偶然一天2人见面了，B认出了A，但A不能确定面前的人是否是B，这时B要向A证明自己是B，也有2个方法。B把自己的私钥给A，A用这个私钥对某个数据加密，然后用B的公钥解密，如果正确，则证明对方确实是B。A给出一个随机值，B用自己的私钥对其加密，然后把加密后的数据交给A，A用B的公钥解密，如果能够得到原来的随机值，则证明对方是B。后面的方法属于零知识证明。

3）有一个缺口环形的长廊，出口和入口距离非常近（在目距之内），但走廊中间某处有一道只能用钥匙打开的门，A要向B证明自己拥有该门的钥匙。采用零知识证明，则B看着A从入口进入走廊，然后又从出口走出走廊，这时B没有得到任何关于这个钥匙的信息，但是完全可以证明A拥有钥匙。^[1]