ゼロ知識証明

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/25 15:15 UTC 版)

具体例

ここで紹介する具体例^[2]では、Pさん（証明者）はある巨大なグラフGのハミルトン閉路を知っているとする。Pさんは、ハミルトン閉路そのものは示すことなく、自分がハミルトン閉路を知っていることをVさん(検証者)に納得させたい。ここで、ハミルトン閉路とはグラフのすべての点を通って出発点に戻ることができる経路のことである。ある巨大なグラフにハミルトン閉路が存在するか、存在するならそれがどういうものかを現実的な計算時間で求めるのは非常に難しく、NP完全問題に分類される。ここで紹介する手法ではハミルトン閉路問題を応用しているが、NP完全問題ならどんな問題でもゼロ知識証明に応用することが可能である。

さて、PさんはVさんにハミルトン閉路も含めてどんな情報も与えたくはない。Gのハミルトン閉路は、Vさんはお金を払ってでも知りたいが正しい答えを知っていることを先に知りたい、というケースもあり得るし、Gのハミルトン閉路を知っていること自体がPさんがPさんであることの証明となっているという状況でもよい。PさんがVさんに、知っていることそのものを証明するには、次のような問答を何回か繰り返せばよい。

各問答に先立って、PさんはGと同型なグラフHを用意する。これは短時間でできるし、GからHへの点の対応がわかっている以上、Hのハミルトン閉路がわかるようならGのハミルトン閉路も知っていることになる。
PさんはVさんにHをコミットする。これにはコミットメント方式を使うか、物理的に行う場合は、グラフの枝の数だけ小さな紙と鍵のかかる箱を用意し、グラフHの各枝の両端の節点番号を小さな紙に書いて、それぞれを箱に入れて鍵をかけてVさんに渡せばよい。ここでは鍵を渡さない。
Vさんは、次の2つの質問のうちどちらかをランダムに選んでPさんに回答を求める。質問とは「GとHの対応表を示せ」または「Hのハミルトン閉路を示せ」のどちらかである。
Pさんは、対応表を示せといわれたら、Hのコミットメントを明かす。或いはすべての箱の鍵を渡し、同時に対応表も明かす。Vさんは、コミットされていたHが本当にGと同型であったことを確認できる。
Pさんは、Hのハミルトン閉路を示せといわれたら、まずGのハミルトン閉路を対応表に従って変換して、Hのハミルトン閉路を求め、その閉路に含まれる部分のコミットメントのみを明かす。あるいは閉路に含まれる枝を記した紙の入った箱の鍵のみを渡す。Vさんは、確かにPさんがHのハミルトン閉路を知っていることを確認できる。

各問答で、PさんはVさんがどちらの質問をしてくるかあらかじめ知ることはできない。そのため、Gのハミルトン閉路を知ることなく両方の質問どちらにも答えるのは無理である。Gのハミルトン閉路を知るもののみがいずれの質問にも必ず答えられるので、この問答を繰り返すことでVさんはPさんが答えを知っていることを確信できるのである。

一方で、Pさんの回答から答え自体が漏れてしまうことはない。どの問答でも、VさんがわかるのはHがGとどう対応しているか、またはHのハミルトン閉路がどういう経路かだけである。ある問答のHについて同時に両方の答えを聞くことができればGのハミルトン閉路も求まるのだが、各問答の都度、どちらかしか教えてもらうことができない。同型グラフとハミルトン閉路問題の性質により、Vさんは個々の問答のHのグラフの型かHのハミルトン閉路について知ることはできるが、それを積み重ねてもGのハミルトン閉路についてなんの情報も得られない。

Pさんがもし本当は答えを知らないとすると、どちらか片方の質問には答えることができる。とりあえずGと同型なHを生成して示すか、勝手に作った閉路に枝を追加して作ったHを示しておいて、そのハミルトン閉路として最初に用意した閉路を示すかである。しかし、両方の質問に答えることはできない。問答をn回繰り返すとき、Vさんの質問にすべて答えきれる確率は ${\frac {1}{2^{n}}}$ となる。ゼロ知識証明は、実用的な回数の繰り返しだけで破られる確率をほぼなくすことができるのである。