ゼロ知識証明
Gのハミルトン閉路を知るもののみがいずれの質問にも必ず答えられるので、この問答を繰り返すことでVさんはPさんが答えを知っていることを確信できるのである。
一方で、Pさんの回答から答え自体が漏れてしまうことはない。どの問答でも、VさんがわかるのはHがGとどう対応しているか、またはHのハミルトン閉路がどういう経路かだけである。ある問答のHについて同時に両方の答えを聞くことができればGのハミルトン閉路も求まるのだが、各問答の都度、どちらかしか教えてもらうことができない。同型グラフとハミルトン閉路問題の性質により、Vさんは個々の問答のHのグラフの型かHのハミルトン閉路について知ることはできるが、それを積み重ねてもGのハミルトン閉路についてなんの情報も得られない。
Pさんがもし本当は答えを知らないとすると、どちらか片方の質問には答えることができる。とりあえずGと同型なHを生成して示すか、勝手に作った閉路に枝を追加して作ったHを示しておいて、そのハミルトン閉路として最初に用意した閉路を示すかである。しかし、両方の質問に答えることはできない。問答をn回繰り返すとき、Vさんの質問にすべて答えきれる確率は 1 2 n {\displaystyle {\frac {1}{2^{n}}}} となる。ゼロ知識証明は、実用的な回数の繰り返しだけで破られる確率をほぼなくすことができるのである。