ゼロ知識対話証明ＺＫＩＰを高校生程度でも理解できるように説明しているページまたは解説をお願いします。

ん～、難しいですかね・・・

『暗号理論』 - 絵と文章でわかりやすい！ - 図解雑学」という本があります（下のほう）。

レスポンス・ゼロ知識対話証明などの認証技術、電子署名や電子透かしなどを解説しています。

参考にしてみてください。

上記URLに詳しく図解で解説されていますので、時間をある程度かけて丁寧に整理していけば十分に理解可能だと思われます。

まず対話証明を説明してから、ゼロ知識証明の概説という風に話を進めます。

Web上に日本語で読める資料が無いので、英語の資料としてO. Goldreichが書いたサーベイをURLに入れておきます。このサーベイは「Foundations of Cryptography」の4章のZero-Knowledgeの簡略版になっています（どちらもpsファイルがあります）。

以下、私が書く説明はGoldreichのサーベイを簡単に直したものです。日本語の本としては、岡本・太田「暗号・ゼロ知識証明・数論」をお勧めしておきます。

以下、長文ですがお付き合いを。

0. 前提知識

・計算が簡単

現実的な時間で計算できることです。今のPCで処理できる程度と思ってください。

・計算が困難

現実的な時間で計算できないということです。

・答えと証拠（または知識）

対話証明やゼロ知識証明では答えは「Yes」「No」の二択です。

一方、証拠は二択ではありません。答えと証拠は別物として扱います。

1. 対話証明

ゼロ知識証明は対話証明の部分集合なので、対話証明から説明します。

登場人物は二人、証明者P（Prover）と検証者V（Verifier）です。

証明者Pは無限の能力を持っています。一方、検証者Vは今のPC程度の能力+コインを振ることしか出来ません。

さて、この二人に問題が与えられます。この問題は必ず「Yes」か「No」で答えられるようになっています。例えば、「与えられた地図は3色で塗り分けられる」という問題は「Yes」「No」で答えられます。

その問題に対話証明が存在するというのを、

　a.（完全性）答えが「Yes」であれば、検証者Vは納得できる

　b.（健全性）答えが「No」であれば、検証者Vはそれなりに高い確率で納得しない

と定義します。

また対話の回数も問題になる場合があるので、(P→V),(V→P)と書いて明示しておきます。

では、具体例を見ます。

地図の3彩色問題に関する対話証明です。

　a.（P→V) 証明者Pは塗り分けられた地図wを検証者Vに見せる

　b. 検証者Vはもらった地図wを見て、塗り分けられているかどうか確認する

証拠wが存在すれば検証者Vは納得できます。また答えが「No」である場合には、塗り分けられた地図wは存在しないので、検証者Vは必ず納得しません。どんな地図を与えられても、上のように対話すれば良い訳です。

2. ゼロ知識証明の具体例

さて、上の例では塗り分けられた地図wを検証者Vに見せていました。

塗り分けられた地図wを見せることなく、

・（関係）地図が塗り分けられることを検証者Vに納得させたい

・（知識）塗り分けられた地図wを持っていることを検証者Vに納得させたい

と云う動機から出来た概念がゼロ知識証明です。

実際に、地図の3彩色問題に関する対話証明を構成します。

　a. 証明者Pは地図を塗り分け、塗りわけ方をwとする。例えば赤青黄で塗り分けておく。

　b. 証明者Pは国の上に箱を置く。次に白黒灰をランダムに並び替える。

　c. 白黒灰を対応する色（赤or青or黄）の国の箱に入れ、鍵を掛ける。

　d.（P→V）証明者Pは検証者Vに箱ごと地図を見せる（検証者Vは箱と地図しか見ていないので塗りわけ方は分からない）。

　e.（V→P）検証者Vはランダムに”接している国を二つ”指定する。

　f.（P→V）証明者Pはその国の上に乗っている箱の鍵を開き、中の色（白or黒or灰）を見せる

　g. 検証者Vが納得するまでaから繰り返す

この対話では、答えが「Yes」なら検証者は必ず納得します。

一方、答えが「No」であれば、必ず塗り分けられていない場所が存在します。従って、検証者Vは1/（境界線の個数）よりは高い確率で塗り分けられていない場所を指定するので、納得しません。

さてこれで対話証明になっていることは分かりました。

次に、この対話証明がゼロ知識証明になっていることを説明します。

直感的に言えば、Vは毎回、二国しか見ていません。更にその塗りわけ方は本来の塗り方ではなく、毎回ランダムに入れ替えられています。

上の対話でVが得られた知識というのは、

・検証者Vはランダムに接している国を二つ選び、それを適当な色で塗り分ける

と自分で計算して得られる知識と同じです。よって対話後に増えた知識の量はゼロです。これをゼロ知識性と呼ぶ訳です。

3. ゼロ知識証明について

具体例を拡張して、ある対話証明がゼロ知識証明であることを定式化しておきます。

　a.（完全性と健全性）証明者Pと検証者Vの間には対話証明がある

　b.（ゼロ知識）任意の検証者V’と対話するシミュレータSが存在して、シミュレータSはV’とPの対話を再現できる。

大雑把に言うと上のような定義になります。

証明者Pと違って、シミュレータSは知識wを持っていません。

直感的には

・検証者Vはどれだけズルをしても証明者Pから知識wを引き出せない

と云うことです。

4. ゼロ知識証明の応用

PとVの間の対話を盗聴していてもPが持っている知識が漏れないので、今までの回答者が答えているように、認証技術に利用することができます。

また対話が(P→V),(V→P),(P→V)と3回の場合には、ハッシュ関数を利用して、(P→V)と対話の回数を減らすことが出来ます。この場合、ゼロ知識証明を電子署名に利用することが出来ます。

5. ゼロ知識証明についての知識

上の説明では多項式時間や指数的時間といった概念を説明していません。また、対話証明は完全性においても誤りを許します（ゼロ知識証明の場合は誤りを許しません）。ゼロ知識は「関係のゼロ知識」と「知識のゼロ知識」と分類する場合もあります。

今回の説明では、こういった細かいところを意図的に削除しています。

蛇足。

そもそもゼロ知識証明の初出は82年なんですが、重要性が無いと思われたらしく学会で発表出来なかったという経緯があります。その後、対話証明やゼロ知識証明に関する結果が出揃ってきたことで日の目を浴びたそうです。