ゼロ知識証明

出典: フリー百科事典『ウィキペディア（Wikipedia）』

暗号学において、ゼロ知識証明とは、ある人が他の人に、自分の持っている（通常、数学的な）知識が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。ゼロ知識対話証明（ZKIP）とも呼ばれる。

[編集] 概要

ゼロ知識証明の研究は、ある人が秘密の知識（パスワードなど）を所持していることをもって本人であることを他の人に示したいがこの秘密自体は誰にも開示しなくてよい認証方式を実現することが動機である。もっとも、パスワードというのはゼロ知識証明で扱う一般的な例ではなく、ゼロ知識証明によるパスワード認証は特殊な応用例である。

ゼロ知識証明で使われる知識には、巨大な合成数の素因子(素因数分解の解)を知っている、離散対数問題の解を知っているなどの公開鍵暗号でよく利用されるトラップがあり、その他、任意のNP完全問題をもとにゼロ知識対話証明を構成できることが知られている。

ゼロ知識証明の応用例には、公開鍵暗号、デジタル署名、ユーザ認証などがある。その他、マルチパーティプロトコルへの適用など多くの応用がある。例えば、個人情報を用いてユーザ認証を行う場合、ユーザはゼロ知識証明のプロトコルに従い、個人情報を入力する。健全性があるので、ユーザは真正な入力でないと正しさを証明できず、そしてゼロ知識性があるため、個人情報そのものは漏れることはないことになる。

ゼロ知識証明は数学上の証明とは厳密には異なる。なぜなら非常に低い確率ではあるが、偽の知識を持っているのにそれが真であると示せてしまうことがあるからである（健全性のエラーと呼ばれる）。言い換えれば、ゼロ知識証明は確定的証明ではなく、確率的証明であると言える。そして、後述する健全性とは、このエラーの起こる確率を実用的に十分小さくできることを意味する。また、ゼロ知識性や対話証明の研究から確率的検査可能証明（Probabilisticalyy Checkable Proof、PCP）が生まれた。

このようなゼロ知識対話証明は、1985年の Goldwasser, Micali, Rackoff たちの論文によって最初に定式化された。以来、多くの研究がなされ、ゼロ知識証明は暗号理論にとって重要な概念の一つとなった。

[編集] 条件

ゼロ知識証明は次の3条件を満たしていないといけない。

完全性: 真であることを確認する側（検証者）は、証明する側（証明者）の持っている知識が真であるならば、真であることが必ずわかること。
健全性: 証明者の持つ知識が偽であるなら、検証者は高い確率でそれが偽であると見抜けること。
ゼロ知識性: 証明者の持つ知識が真であるなら、検証者が不正して証明者から知識を盗もうとしても「知識が真である」以外のなんの情報も得られないこと。このゼロ知識性は、どんな検証者（知識を持たない）であっても、正しい証明者と対話したかのような対話記録を生成できることだと記述することもできる。

前二者の性質は、ゼロ知識証明に限らず対話型証明システムに共通のものである。最後の性質があってはじめてゼロ知識証明となる。

[編集] 洞窟の問題

ジャン＝ジャック・キスケータらの論文「我が子にゼロ知識証明をどう教えるか(How to Explain Zero-Knowledge Protocols to Your Children)」で紹介されているのが、この洞窟の問題の例である。ここで、証明者はP(Prover)、検証者はV(Verifier)と略すのが一般的なのでこれを用いて説明する。

Pさんが、魔法の扉を開くための合い言葉を手に入れたとする。その魔法の扉は、ある洞窟の一番奥にあり、洞窟は途中で分かれて奥でつながっていて魔法の扉で仕切られているとする。

Vさんはお金を払ってでも合い言葉が知りたいが、Pさんが本当の合い言葉を知っていると確認できるまでは払いたくない。Pさんは教えてもいいが、お金をもらうまでは教えたくない。そこで二人は、合い言葉そのものは教えることなく、正しい合い言葉を知っていることだけ証明する方法を使うことになる。

まず、Vさんは洞窟の外で待ち、Pさんだけ入る。左右の分かれ道をそれぞれA,Bと呼ぶことにすると、PさんはAかBどちらかの分かれ道をランダムに選んで奥に入ることになる。次にVさんは分かれ道の入り口まで行き、どちらの道かをランダムに選んで、そこから出てきてほしいと大声で伝える。Pさんが合い言葉を知っているならそれに答えるのは簡単である。もし反対側なら魔法の扉を開けて通るだけでよい。VさんはPさんがどちらから入ったのかは知らないという点に留意。

もちろん、実はPさんが合い言葉を知らないという場合もあり得る。この場合、入った道から出てくることしかできない。Vさんがランダムに出てくるべき道を選ぶので、Pさんがリクエストに応えられるのは50％の確率である。もしこの二人がこの試みを何度も繰り返せば、Vさんがすべてのリクエストに応えるのはほとんど不可能になる（20回繰り返したら、約0.0001％となる）。これなら、複数回のリクエストに応えられたならVさんはPさんが確かに合い言葉を知っていると納得できる。

この例だと、そんな複雑な手続きをせずにPさんがVさんに「片方の道から入って反対の道から戻ってこい」と言うだけで証明ができるようにも思えるかもしれない。しかしこの方法だと、確かに証明はできるものの、合い言葉を盗めてしまう可能性が残ってしまうのだ。Pさんが入る道はランダムに決め、それをVさんがわからないようになっていてこそ、VさんがPさんの跡をつけて合い言葉を盗み聞きするのを防ぐことができる。これは、露出する情報を最小限にするために重要な点である。

[編集] 応用例

ゼロ知識証明の考え方は暗号アプリケーションに実用できる。ここで紹介する応用例では、Pさん（証明者）はある巨大なグラフGのハミルトン閉路を知っているとする。Pさんは、ハミルトン閉路そのものは示すことなく、ハミルトン閉路を知っていることを他人に納得させたい。ここで、ハミルトン閉路とはグラフのすべての点を通って出発点に戻ることができる経路のことである。ある巨大なグラフにハミルトン閉路が存在するか、存在するならそれがどういうものかを現実的な計算時間で求めるのは非常に難しく、NP完全問題に分類される。ここで紹介する手法ではハミルトン閉路問題を応用しているが、実はNP完全問題ならどんな問題でもゼロ知識証明に応用することが可能だ。

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

各問答に先立って、PさんはGと同型なグラフHを用意する。これは短時間でできるし、GからHへの点の対応がわかっている以上、Hのハミルトン閉路がわかるようならGのハミルトン閉路も知っていることになる。
PさんはVさんにHだけ示す。Vさんはここで、次の2つの質問のうちどちらかをランダムに選んでPさんに回答を求める。質問とは「GとHの対応表を示せ」または「Hのハミルトン閉路を示せ」のどちらかである。
Pさんは、対応表を示せといわれたらそれを示す。Vさんは、Hが本当にGと同型であったことを確認できる。
Pさんは、Hのハミルトン閉路を示せといわれたら、Gのハミルトン閉路を対応表に従って変換して示す。Vさんは、確かにPさんがHのハミルトン閉路を知っていることを確認できる。

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

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

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

[編集] 参考文献

Shafi Goldwasser, Silvio Micali, Charles Rackoff, "The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract)", STOC, pp.291-304, 1985. (ゼロ知識対話証明を最初に定式化した論文)