预计阅读本页时间：-
零知识证明
假设证明者Patti想让验证者Victor确认她的身份，而他们的通信信道是不安全的。假设分析者Albert在监听通信，并且试图将自己伪装成Patti。如果Patti和Victor知道某个密码："Rosebud"，如果Patti通过发送这个密码来确认自己的身份，那么之后Albert也就能够以同样的密码向Victor声明自己就是Patti。所以Patti想要建立一个更加安全的协议。下面这个协议假设：对于大图来说同构图和Hamiltonian回路问题的复杂程度非常大，几乎无法解决。
Hamiltonian回路
给定一个图，是否存在这样一个回路：经过所有的点，且经过每个点仅一次，最后返回到起点。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
同构图
给定两个图：G1=(V1,E1)和G2=(V2,E2)，是否存在节点集合V1和V2间的某种映射，使得两张图完全一致。
图10-6给出了两张同构图及其映射关系的示例。
对于大型实例来说这两个问题都不太可能找到有效的解决方法。我们利用了这些问题的难度开发了一种适合在不安全信道上的确认协议，同时保证Albert无法伪装成Patti。在开始确认前，Patti先建一张存在Hamiltonian回路的大图，具体可以这样来做：先从一条回路开始，而这条回路会通过每一个节点，然后再不断地加边，直到对于其他人来说很难找出这个Hamiltonian回路的程度。然后Patti就可以在她名下的一个公开目录公布这个图Gpatti。Victor和Albert都可以读取这张图，但只有Patti能够找出图Gpatti中的Hamiltonian回路。
她可以通过像Victor发送这个Hamiltonian回路的节点顺序来确认自己的身份，但是，之后Albert或者Victor就都可以伪装成她（她的证明不是零知识证明）。她想要让Victor确认她知道这个秘密回路，而同时Victor或是Albert又不会知道她的知识。例10-4中描述了Patti的协议。
例10-4：不会泄露任何信息的协议
无论Victor问Patti的是什么（无论掷硬币结果如何），Patti都能轻松应答，而Victor也能轻松验证。如果Albert想要伪装成Patti，就有两种可能性：他能够构造并传送自己的图H和图Gpatti或多或少有些类似（比如可能含有相同数量的边和节点），并且他知道其中的Hamiltonian回路。但是如果作为验证者的Victor说"ShowIsomorphism"的话，他便答不出来。又或者Albert重新标记并传送了图Gpatti的节点。但是如果作为验证者的Victor说"ShowHamiltonianCycle"，他也答不出来。因此Albert只能伪造协议的一半。为了增加更多的可信度，Victor可以将协议进行100次（毕竟效率很高），Patti可以轻松成功，但是Albert可以成功伪造100次协议的概率则是0.788*10-30。而且，即使Albert观察100次也无济于事。
