電波系美少女バーチャルインターネッツアイドル文野純がメッタメタ遊んでメッタメタ考えて勉強するゲヲログ姉妹サイト...

メニュー⇒ ソフトウェア 思想評論 数学 書評 歴史 統計 雑感 馬鹿企画

ゼロ知識証明の定義と簡単な説明―「洞窟の問題」

ゼロ知識証明の定義と簡単な説明―「洞窟の問題」

ゼロ知識証明(zero-knowledge proof)は簡単に洞窟の問題として語り継がれている。子供にゼロ知識証明を教えるにあたって、ハミルトン路とかそういうことを言うと分からないことが多い。数式での証明も難しい。だが、洞窟の問題によってゼロ知識証明についてはかなり簡潔に教えることができる。ゼロ知識証明のはじめの一歩として理論の説明から入ろう。

証明認証に当たってこのような定義を持ち出すことが多い(証明者P=prover:検証者V=verifierとする)。
・完全性:Vは高い確率でPの証明を受け入れる。
・健全性:VはPの不正記述をフィルタリングできる。
・ゼロ知識性:Vが得られる情報は自分で得られるものか、または正・不正どちらかの情報に限られる。

さらに定義において予備としてこういうものがあっていい。
・計算容易性:Vが検証するにあたって簡単な計算処理で可能になる。

これらゼロ知識証明のアルゴリズムはシャフィ(https://en.wikipedia.org/wiki/Shafi_Goldwasser)などによってつくられた。簡単にこの証明を洞窟の問題に例えて説明しよう(https://en.wikipedia.org/wiki/Zero-knowledge_proofより画像引用)。

・上図のようなハミルトン路(数学的なNP問題やグラフ理論と関係がある)のような洞窟がある。
・洞窟はA・Bのルートがありそのつながる部分があって、つながる二つの通気口のような構図である。
・そのA・Bの合わさるところの壁は魔法の言葉でどちらからでも開けられる扉になっている。

・合言葉はP(証明者)しか知らない。Pは合言葉でこの仕切られた洞窟を貫通する扉を開けられる。
・はじめどっちから入るかはP自身で決められる(このときVは洞窟の外にいるので漏洩はない)。
・どちらから出てくるかをVが指図してその通りにPが出てくる(同様にVは追跡して盗み聞きできない)。

さて、VはPの合言葉をお金を払って知りたい。だがPはまだ信用できない。これが洞窟の活用法だ。
・Pが何回もVの指図通りにどちらから出てくれれば信用するに値する。
・これを何回も繰り返すと、50:50の確率なので、問題を深く検証できる。

これを数式で表すと簡単にわかる、例えばn回繰り返すと…

(1/2)^n

となり20、30繰り返すだけで(1/2^20もしくは1/2^30あるいはそれ以上と)相当高い確率でどの条件も含めて検証できることとなる。検証が済めば正しい対価を支払ってまで証明者が証明できたこととなる。冒頭に書いたようにゼロ知識証明のありかたがしっかりと定まりこの例でしっかりと説明できている。代数的にこの手法を誰にでも簡単に説明できる例がこの通りである。要するに…

・完全性・・・高い確率でPはVに証明できる。
・健全性・・・フィルタリングされてPはVに健全な情報を持ち込める。
・ゼロ知識性・・・相手(V)に不都合な情報は盗み聞き(合言葉の漏洩)できない。

どれも満たすこととなる。ほかにも有名な事例であるフィアット・シャミア方式などがあるが、これは難しい数式が提示されるので簡単には教えられない…が、アルゴリズムはほぼ同等であるから、定義だけは押さえておこう。以下が乱数と余剰を使っての説明である。同様にP:証明者、V:検証者として…

・Pが乱数r生成。
・さらにx=r^2(mod n)をVに送信。
・Vはeとしてランダムに0or1の信号を送る。
・Pはy=rs^e(mod n)をVに送る。
・Vはy≠xv^e(mod n)ならばk回のこれまでの試行を中断する。

※参考書―フィアット・シャミア方式の定義は「暗号理論入門」岡本にならった。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする