1990年，J.Quisquater和L.Guillon列举了一个形象的基本零知识协议的例子——零知识洞穴，如图5.1所示。设P知道咒语，可打开C和D之间的秘密门，不知道者则走向死胡同。现在来看P如何向V出示证明使其相信他知道这个秘密，但又不告诉V有关咒语。

协议1：洞穴协议

（1）V站在A点；

（2）P进入任一点C或D；

（3）当P进洞之后，V走向B点；

（4）V叫P①从左边出来，或②从右边出来；

（5）P按照要求实现（有咒语）；

（6）P和V重复执行（1）～（5）共n次。

若P不知道咒语，则在B点，只有50%的机会猜中V的要求，协议执行n次，则只有2-n次机会完全猜中。此洞穴问题可以转化为数学问题，P知道解决某个难题的秘密信息，而V通过与P交互作用验证其真伪。

图5.1　零知识洞穴

以下协议又称作分割选择协议，是公平分享东西时的经典协议。

协议2：分割选择协议

（1）P将东西切成两半；(www.daowen.com)

（2）V选其中之一；

（3）P拿走剩下的一半。

显然，P为了自己的利益在（1）中要公平分割，否则（2）中V先于他的选择将对其不利。这个协议为交互零知识证明的雏形。

协议3：一般的协议

（1）P用其信息和某种随机数将难题转换成另一种难题，且与原来的同构，P可采用其信息和随机数解新的难题；

（2）P想出新的难题的解，采用比特承诺方案；

（3）P将新的难题出示给V，但V不能由此新难题得到有关原问题或其解；

（4）V向P提出下述问题之一：

①向V证明老的和新的问题是同构的；

②公开（2）的解，并证明它是新难题的解；

（5）P按V的要求执行；

（6）P和V重复执行（1）～（5）共n次。