洞窟の問題

ウィキペディア小見出し辞書

洞窟の問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/18 21:39 UTC 版)

「ゼロ知識証明」の記事における「洞窟の問題」の解説

ジャン＝ジャック・キスケータらの論文「我が子にゼロ知識証明をどう教えるか(How to Explain Zero-Knowledge Protocols to Your Children)」で紹介されているのが、この洞窟の問題の例である。ここで、証明者はP(Prover)、検証者はV(Verifier)と略すのが一般的なのでこれを用いて説明する。 Pさんが、魔法の扉を開くための合言葉を手に入れたとする。その魔法の扉は、ある洞窟の一番奥にあり、そこへ至る経路はAとBの2つがあって、合言葉で魔法の扉を開くとAからB、或いはその反対へ移動できる。 Vさんはお金を払ってでも合言葉が知りたいが、Pさんが本当の合言葉を知っていると確認できるまでは払いたくない。Pさんは教えてもいいが、お金をもらうまでは教えたくない。そこで2人は、合言葉そのものは教えることなく、正しい合言葉を知っていることだけ証明するために以下の手順を取る。 まず、Vさんは洞窟の外で待ち、Pさんだけ入る。PさんはAかBどちらかの分かれ道をランダムに選んで奥に入る。次にVさんは分かれ道の入り口まで行き、どちらかの道をランダムに選ぶ。そしてPさんに、ランダムに選んだその道から出てきてほしいと大声で伝える。ここで、VさんはPさんがどちらから入ったのかは知らないという点に留意する。 もし、Pさんが合言葉を知っている場合 Vさんの選んだ道から出てくるのは簡単である。自分が入った道を選ばれたら、そのまま戻ってくれば良い。もし反対側を選ばれたなら、合言葉で魔法の扉を開けて反対の道から出てくれば良い。 もし、Pさんが合言葉を知らない場合 Pさんは入った道から出てくることしかできない。Vさんがランダムに出てくるべき道を選ぶので、Pさんがリクエストに応えられるのは50％の確率である。2人がこの試行を何度も繰り返せば、Pさんがすべてのリクエストに応えるのはほとんど不可能である。例えば20回繰り返したら、全てに応えられる可能性は約0.0001％となる。 よって、Pさんが複数回のリクエストに全て応えられたなら、VさんはPさんが確かに合言葉を知っていると納得できる。 この例だと、そんな複雑な手続きをせずにVさんがPさんに「片方の道から入って反対の道から戻ってこい」とリクエストするだけで証明ができるようにも思えるが、そうすると、Pさんの合言葉がVさんに盗まれる可能性がある。つまり、VさんがPさんの跡をつけて合言葉を盗み聞きすることができる。VさんがPさんを追跡できないようにすることが、露出する情報を最小限にするために重要な点である。