ゼロ知識証明

暗号学において、ゼロ知識証明（ぜろちしきしょうめい、zero-knowledge proof）とは、ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。ゼロ知識対話証明（ZKIP）とも呼ばれる。
概要.
ゼロ知識証明の研究は、ある人が，秘密の知識（パスワードなど）を所持していることをもって，本人であることを他の人に示したいが，この秘密自体は誰にも開示しなくてよい認証方式を実現することが動機である。もっとも、パスワード認証というのはゼロ知識証明で扱う一般的な例ではない。ゼロ知識証明によるパスワード認証は特殊な応用例である。
ゼロ知識証明で証明される命題には、巨大な合成数の素因子（素因数分解の解）を知っている、離散対数問題（DLP）の解を知っているなどの公開鍵暗号でよく利用されるものがある。また、任意のNP完全問題の証拠を持っていることをゼロ知識証明で示せることが知られている。
ゼロ知識証明の応用例には、公開鍵暗号、デジタル署名、ユーザ認証などがある。その他、マルチパーティ計算への適用など多くの応用がある。例えば、個人情報を用いてユーザ認証を行う場合、ユーザはゼロ知識証明のプロトコルに従い、個人情報を入力する。健全性があるので、ユーザは真正な入力でないと正しさを証明できず、そしてゼロ知識性があるため、個人情報そのものは漏れることはないことになる。
ゼロ知識証明は数学上の証明とは厳密には異なる。なぜなら非常に低い確率ではあるが、偽の命題を持っているのにそれが真であると示せてしまうことがあるからである（健全性のエラーと呼ばれる）。言い換えれば、ゼロ知識証明は確定的証明ではなく、確率的証明であると言える。そして、後述する健全性とは、このエラーの起こる確率を実用的に十分小さくできることを意味する。また、ゼロ知識性や対話証明の研究から確率的検査可能証明（Probabilisticaly Checkable Proof、PCP）が生まれた。
このようなゼロ知識対話証明は、1985年の Goldwasser, Micali, Rackoff たちの論文によって最初に定式化された。以来、多くの研究がなされ、ゼロ知識証明は暗号理論にとって重要な概念の一つとなった。
条件.
ゼロ知識証明は次の3条件を満たしていないといけない。
前二者の性質は、ゼロ知識証明に限らず対話型証明システムに共通のものである。最後の性質があってはじめてゼロ知識証明となる。
なお健全性よりも強い知識健全性（knowledge soundness）とよばれる性質が用いられる場合もあり、この性質は「検証者が証明を受理したならば、証明者にオラクルアクセスすることで高確率で命題に対応する証拠を抽出できる（つまり証明者の秘密を取り出せる）効率的なアルゴリズムが存在する」ことを保証する。健全性を知識健全性に置き換えた場合は知識のゼロ知識証明（zero-knowledge proof of knowledge）と呼ばれる。
洞窟の問題.
ジャン＝ジャック・キスケータらの論文「我が子にゼロ知識証明をどう教えるか(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さんが確かに合言葉を知っていると納得できる。
この例だと、そんな複雑な手続きをせずにVさんがPさんに「片方の道から入って反対の道から戻ってこい」とリクエストするだけで証明ができるようにも思えるが、そうすると、Pさんの合言葉がVさんに盗まれる可能性がある。つまり、VさんがPさんの跡をつけて合言葉を盗み聞きすることができる。VさんがPさんを追跡できないようにすることが、露出する情報を最小限にするために重要な点である。
具体例.
ここで紹介する具体例では、Pさん（証明者）はある巨大なグラフ"G"のハミルトン閉路を知っているとする。Pさんは、ハミルトン閉路そのものは示すことなく、自分がハミルトン閉路を知っていることをVさん(検証者)に納得させたい。ここで、ハミルトン閉路とはグラフのすべての点を通って出発点に戻ることができる経路のことである。ある巨大なグラフにハミルトン閉路が存在するか、存在するならそれがどういうものかを現実的な計算時間で求めるのは非常に難しく、NP完全問題に分類される。ここで紹介する手法ではハミルトン閉路問題を応用しているが、NP完全問題ならどんな問題でもゼロ知識証明に応用することが可能である。
さて、PさんはVさんにハミルトン閉路も含めてどんな情報も与えたくはない。"G"のハミルトン閉路は、Vさんはお金を払ってでも知りたいが正しい答えを知っていることを先に知りたい、というケースもあり得るし、"G"のハミルトン閉路を知っていること自体がPさんがPさんであることの証明となっているという状況でもよい。PさんがVさんに、知っていることそのものを証明するには、次のような問答を何回か繰り返せばよい。
各問答で、PさんはVさんがどちらの質問をしてくるかあらかじめ知ることはできない。そのため、"G"のハミルトン閉路を知ることなく両方の質問どちらにも答えるのは無理である。"G"のハミルトン閉路を知るもののみがいずれの質問にも必ず答えられるので、この問答を繰り返すことでVさんはPさんが答えを知っていることを確信できるのである。
一方で、Pさんの回答から答え自体が漏れてしまうことはない。どの問答でも、Vさんがわかるのは"H"が"G"とどう対応しているか、または"H"のハミルトン閉路がどういう経路かだけである。ある問答の"H"について同時に両方の答えを聞くことができれば"G"のハミルトン閉路も求まるのだが、各問答の都度、どちらかしか教えてもらうことができない。同型グラフとハミルトン閉路問題の性質により、Vさんは個々の問答の"Hのグラフの型かHのハミルトン閉路について知ることはできるが、それを積み重ねてもG"のハミルトン閉路についてなんの情報も得られない。
Pさんがもし本当は答えを知らないとすると、どちらか片方の質問には答えることができる。とりあえず"G"と同型な"H"を生成して示すか、勝手に作った閉路に枝を追加して作った"H"を示しておいて、そのハミルトン閉路として最初に用意した閉路を示すかである。しかし、両方の質問に答えることはできない。問答を"n"回繰り返すとき、Vさんの質問にすべて答えきれる確率はformula_1となる。ゼロ知識証明は、実用的な回数の繰り返しだけで破られる確率をほぼなくすことができるのである。
非対話ゼロ知識証明.
GoldreichとOrenの研究により、ゼロ知識証明を対話をせずに実行すること、すなわち、証明したい人が「証明」を作成して一方的に送りつけるだけで完了するような証明は作れないことが示されている。 しかし特殊な条件下では、対話が不要なゼロ知識証明が作れることが知られており、非対話ゼロ知識証明（non-interactive zero-knowledge proof; NIZK) と呼ばれている。NIZKの実用的な応用としては、デジタル署名や、プライバシーに配慮した暗号通貨がある。後者では、コインの取引者のアドレスや取引量などを隠したまま、取引が正当であることを証明するのにNIZKが利用できる。