零知识证明协议是一种交互式证明系统。交互式证明系统由示证者P与验证者V参与,他们两方可交换信息,这些信息依靠保密的随机数。示证者P是想让验证者相信断言为真的,验证者接受或拒绝证明。
1.交互式证明系统
在交互式证明系统中,首先示证者P了解某一秘密,P想让V信任自己真的掌握了此秘密。交互式证明是一种挑战应答协议,证明由若干轮组成,在每轮中都有验证者的挑战与示证者的应答。他们轮流执行如下操作:
1)从对方接收一个消息。
2)执行一个私人计算。
3)送一个消息给对方。
全部轮执行完后,V由P是否在每轮对自己的询问都可无误应答来确定要不要接受P的证明。
交互证明和数学证明的不同之处是:数学证明的证明者能独立地实现证明,而交互证明是通过P产生证明、V验证其有效性实现的,因此双方通过某种信道的通信是一定要的。
2.零知识证明协议
在交互证明系统中,假设P清楚某秘密,并给V证明自己确实知道,却不泄露该秘密给V,这即为最小泄露证明。进一步,若V除了了解P可以证明某事实外,不会得到其他任何信息,则即P实现了零知识证明,相应的协议叫零知识证明协议。在1989年美国的密码学会议上《如何向你的小孩解释零知识证明》一文,对零知识证明做了形象、直观的解释。
