零知识证明协议及其应用

零知识证明协议是一种交互式证明系统。交互式证明系统由两方参与，分别为示证者P和验证者V，P和V可以交换信息，这些信息依赖于保密的随机数。示证者P的目的是让验证者相信一个断言是真的，验证者接受或拒绝证明。

1.交互式证明系统

在交互式证明系统中，首先示证者P知道某一秘密，P希望使V相信自己的确掌握了这一秘密。交互式证明是一种挑战应答协议，证明由若干轮组成，在每一轮里包含验证者的挑战和示证者的应答。他们轮流执行如下操作：

1）从对方接收一个消息。

2）执行一个私人计算。

3）送一个消息给对方。

所有轮执行完后，V根据P是否在每一轮对自己发出的询问都能正确应答来决定是否接受P的证明。

交互证明和数学证明的区别是：数学证明的证明者可自己独立地完成证明，而交互证明是由P产生证明、V验证证明的有效性来实现的，因此双方之间通过某种信道的通信是必需的。

交互证明系统须满足以下要求：

●完全性：如果P知道某一秘密，V将接受P的证明。

●合理性：如果P能以一定的概率使V相信P的证明，则P知道相应的秘密。

2.零知识证明协议(https://www.xing528.com)

在交互证明系统中，设P知道某一秘密，并向V证明自己掌握了这一秘密，但又不向V泄露这一秘密，这就是最小泄露证明。进一步，如果V除了知道P能证明某一事实外，不能得到其他任何信息，则称P实现了零知识证明，相应的协议称为零知识证明协议。

在1989年美国的密码学会议上《如何向你的小孩解释零知识证明》一文，对零知识证明做了形象、直观的解释。图8-1是一个洞穴，C与D之间有一道门，需要知道秘密咒语才能将其打开。P向V证明自己能打开这道门，但又不愿向V泄露秘密咒语。证明过程如下：

1）开始时V停留在位置A。

2）P进入洞穴，一直走到洞穴深处，随机选择位置C或位置D。

3）V看到P进入洞穴后，从A走到B点。

4）V大声叫喊，要求P从左边或右边出来回到位置B。

5）P服从V的命令，必要时利用秘密咒语打开C与D之间的门。

6）P和V重复以上过程n次。

图8-1 洞穴示意图

如果P不知道秘密咒语，就只能从来路返回B，而不能走另外一条路。如果P的确知道打开C与D之间门的秘密咒语，则P每次都能按V要求的方向走出洞穴。因此每一轮中P能够欺骗V的概率是1/2，P欺骗成功n次的概率只有1/2ⁿ。假定n取16，则执行16轮后，P成功欺骗V的概率是1/2¹⁶=1/65536。于是，如果P 16次都能按V的要求返回，即能证明P确实知道秘密咒语。还可以看出，V无法从上述证明过程中获取丝毫关于P的秘密咒语的信息，所以这是一个零知识证明协议。