80年代初,Goldwasser等人提出了零知识证明这一概念.从本质上讲,零知识证明是一种协议.所谓协议(Protocol),就是两个或两个以上的参与者为完成某项特定的任务而采取的一系列步骤,包括以下三个特征：
1.协议自始至终是有序的过程,每一步骤必须依次执行,在前一步骤没有执行完之前,后面的步骤不可能执行.
2.协议至少需要两个参与者,一个人可以通过执行一系列的步骤来完成某项任务,但它不构成协议.
3.通过执行协议必须能够完成某项任务.
零知识证明必须包括两个方面,一方为证明者,另一方为验证者.证明者试
图向验证者证明某个论断是正确的,或者证明者拥有某个知识,却不向验证者透露任何有用的消息.零知识证明目前在密码学中得到了广泛的应用,尤其是在认证协议、数字签名方面,人们利用数字签名设计出了大量优良的算法.
用一个关于洞穴的故事来解释零知识.洞穴中有一个秘密,知道咒语的人能打开 C 和D之间的密门,对其它人来说,两条通道都是死胡同.Peggy 知道这个洞穴的秘密.她想对 Victor 证明这一点,但也不想泄露咒语.
下面是她如何使 Victor 相信的过程：
(1) Victor 站在A点.
(2) Peggy 一直走进洞穴,到达C点或者D点.
(3) 在 Peggy 消失在洞穴中后,Victor 走到B点.
(4) Victor 向 Peggy 喊叫,要她：从左通道出来,或者从右通道出来.
(5) Peggy 答应了,如果有必要她就用咒语打开密门.
Peggy 和 Victor 重复第(1)至第(5)步 n 次.
假设 Victor 有一个摄像机能记录下他所看到的一切.他记录下 Peggy 消失在洞中情景,记录下他喊叫 Peggy 从他选择的地方出来的时间,记录下 Peggy 走出来.他记录下所有的 n 次试验.如果他把这些记录给 Carol 看,她会相信 Peggy知道打开密门的咒语吗?在不知道咒语的情况下,如果Peggy和Victor事先商定好 Victor 喊叫什么,那将如何呢?Peggy 会确信也走进 Victor 叫她出来那条路,然后她就可以在不知道咒语的情况下在 Victor 每次要她出来的那条路上出来.或许他们不那么做,Peggy 走进其中一条通道,Victor 发出一条随机的要求.如果 Victor 猜对了,好极了.如果他猜错了,他们会从录像中删除这个试验.总之,Victor 能获得一个记录,它准确显示与实际证明 Peggy 知道咒语的相同的事件顺序.
这说明了两件事.其一是 Victor 不可能使第三方相信这个证明的有效性；其二,它证明了这个协议是零知识的.在 Peggy 不知道咒语的情况下,Victor 显然是不能从记录中获悉任何信息.但是,因为无法区分一个真实的记录和一个伪造的记录,所以 Victor 不能从实际证明中了解任何信息－它必是零知识.也就是说,Peggy 在向 Victor 证明的过程中没有泄露任何有关秘密的知识,称为零知识.