ゼロ知識証明

暗号学において、ゼロ知識証明（ぜろちしきしょうめい、zero-knowledge proof、略称：ZKP）とは、ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。ゼロ知識対話証明（ZKIP）とも呼ばれる。

概要

ゼロ知識証明で証明される命題には、巨大な合成数の素因子（素因数分解の解）を知っている、離散対数問題（DLP）の解を知っているといった、公開鍵暗号でよく利用されるものがある。また、任意のNP完全問題の証拠を持っていることをゼロ知識証明で示せることが知られている。

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

ゼロ知識証明における「証明」は数学上の証明とは異なり、確定的証明ではなく、確率的証明である。すなわち、証明者が持つ命題が偽であるのに検証者が真であると誤って判定してしまうこともある（健全性のエラー）が、このエラーが起きる確率を実用的に十分小さくできることを意味する。

ゼロ知識性や対話証明の研究から確率的検査可能証明（Probabilisticaly Checkable Proof、PCP）が生まれた。

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

条件

実用的なゼロ知識証明は次の3条件を満たしていなければならない。

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

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

なお健全性よりも強い知識健全性（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人は合言葉そのものを教えることなく、Pさんが正しい合言葉を知っていることを証明したい。そこで、2人は以下の手順を取る。

まず、Vさんは洞窟の外で待ち、Pさんだけ入る。PさんはAかBどちらかの分かれ道をランダムに選んで奥に入る。次にVさんは分かれ道の入り口まで行き、どちらかの道をランダムに選ぶ。そしてPさんに、ランダムに選んだその道から出てきてほしいと大声で伝える。ここで、VさんはPさんがどちらから入ったのかは知らないという点に留意する。

• もし、Pさんが合言葉を知っている場合

Vさんの選んだ道から出てくるのは簡単である。自分が入った道を選ばれたら、そのまま戻ってくれば良い。もし反対側を選ばれたなら、合言葉で魔法の扉を開けて反対の道から出てくれば良い。

• もし、Pさんが合言葉を知らない場合

Pさんは入った道から出てくることしかできない。Vさんがランダムに出てくるべき道を選ぶので、Pさんがリクエストに応えられるのは50％の確率である。2人がこの試行を何度も繰り返せば、Pさんがすべてのリクエストに応えるのはほとんど不可能である。例えば20回繰り返したら、全てに応えられる可能性は約0.000001％となる。

よって、Pさんが複数回のリクエストに全て応えられたなら、VさんはPさんが確かに合言葉を知っていると納得できる。

なお、この例では、VさんがPさんに「片方の道から入って反対の道から戻ってこい」とリクエストで証明できるようにも思えるが、その方法ではVさんがPさんの跡をつけて合言葉を盗み聞きすることができる。この例ではVさんが洞窟の入り口に待機しPさんを追跡できない（情報を露出しない）まま証明できることが重要である。

具体例

以下、具体例を示す。

・Webサービスにログインする時：パワードを入力する代わりに、パスワードを知っているという証拠を送る。

・本人確認する時：第三者に母親の旧姓を送る代わりに、自分が確実に本人であることの証拠を送る。（デジタル署名）

・ブロックチェーンにトランザクションを送る時：パブリックブロックチェーンに、トランザクションを送るとの違って、自分の過去のトランザクションを明かすことなく、二重払いしていないことの証拠を送る。（ZCash）

また有名なウォーリーをさがせという本がある。この本は絵の中からウォーリーを探すゲームである。この本をaとbが楽しんでいる。

aがウォーリーを見つけた。それをaはbに自慢したい。その一方でaはbに自分で見つけてみて欲しいと思っている。このときにaはウォーリーの場所をbに知らせずにウォーリーを見つけたことのみ教えたい。

aは自分が見つけたことを証明するため、２つの方法を考え出した。

証明１ aは絵からウォーリーだけを切り抜いて、bに見せる。念のため、aが単にウォーリーの絵を、新しくコピーしただけでないことを証明するには、絵全体の裏面に透かしを入れておく。

証明2 aはオリジナルの絵全体に、カードボードを被せて、ウォーリーの箇所だけ切り抜く。こうするとウォーリーだけが見える。ウォーリーの位置情報はbには一切開示していない。aはカードボードを、絵に被せるだけでいつでも、ウォーリーを見つけたことを証明できる。

次は対話証明（二人が通信する）ゼロ知識証明の例である。この例でaは色盲で、bは色を識別できると仮定する。ところが、aはbに色が見えるということが信じられない。

そこでaがこのような提案をする。

a>私は今、赤と青のボールを持っている。ボールを持ったまま、両手を後ろに隠す。その時に、ボールを入れ替えるかもしれない。入れ替えないかもしれない、どちらにしろ、ボールは再度bに見せる。

色が見える人だけが、aが交換したか、常に当てることができる。

この証明では、aが納得するまで何度も繰り返す。20回もゲームを繰り返すと、bが偶然正解を当てる確率は、1,048,576/1回であることがわかった。bには色が見えていることがわかり、aは納得できた。（bはボールの色情報を伝えることなく、色が違うことをaに納得させた。）

また、少し長い説明になるが次のようなものもある。Pさん（証明者）はある巨大なグラフGのハミルトン閉路を知っているとする。Pさんは、ハミルトン閉路そのものは示すことなく、自分がハミルトン閉路を知っていることをVさん(検証者)に納得させたい。ここで、ハミルトン閉路とはグラフのすべての点を通って出発点に戻ることができる経路のことである。ある巨大なグラフにハミルトン閉路が存在するか、存在するならそれがどういうものかを現実的な計算時間で求めるのは非常に難しく、NP完全問題に分類される。ここで紹介する手法ではハミルトン閉路問題を応用しているが、NP完全問題ならどんな問題でもゼロ知識証明に応用することが可能である。

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

• 各問答に先立って、PさんはGと同型なグラフHを用意する。これは短時間でできるし、GからHへの点の対応がわかっている以上、Hのハミルトン閉路がわかるようならGのハミルトン閉路も知っていることになる。
• PさんはVさんにHをコミットする。これにはコミットメント方式を使うか、物理的に行う場合は、グラフの枝の数だけ小さな紙と鍵のかかる箱を用意し、グラフHの各枝の両端の節点番号を小さな紙に書いて、それぞれを箱に入れて鍵をかけてVさんに渡せばよい。ここでは鍵を渡さない。
• Vさんは、次の2つの質問のうちどちらかをランダムに選んでPさんに回答を求める。質問とは「GとHの対応表を示せ」または「Hのハミルトン閉路を示せ」のどちらかである。
• Pさんは、対応表を示せといわれたら、Hのコミットメントを明かす。或いはすべての箱の鍵を渡し、同時に対応表も明かす。Vさんは、コミットされていたHが本当にGと同型であったことを確認できる。
• Pさんは、Hのハミルトン閉路を示せといわれたら、まずGのハミルトン閉路を対応表に従って変換して、Hのハミルトン閉路を求め、その閉路に含まれる部分のコミットメントのみを明かす。あるいは閉路に含まれる枝を記した紙の入った箱の鍵のみを渡す。Vさんは、確かにPさんがHのハミルトン閉路を知っていることを確認できる。

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

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

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

非対話ゼロ知識証明

GoldreichとOrenの研究により、ゼロ知識証明を対話をせずに実行すること、すなわち、証明したい人が「証明」を作成して一方的に送りつけるだけで完了するような証明は作れないことが示されている。 しかし特殊な条件下では、対話が不要なゼロ知識証明が作れることが知られており、非対話ゼロ知識証明（non-interactive zero-knowledge proof; NIZK) と呼ばれている。NIZKの実用的な応用としては、デジタル署名や、プライバシーに配慮した暗号通貨がある。後者では、コインの取引者のアドレスや取引量などを隠したまま、取引が正当であることを証明するのにNIZKが利用できる。

以下に例を示す。

aとbの間にやり取りは発生しない。この例では、aは証明できたことの証拠を事前に作り上げ、bは事後に確認を行う。この非対話型の方法は、bのみならず、不特定多数の誰でもaの証明を確認できることが特徴である。

数独パズルを解く証明

aは、誰も解けなかった数独パズルを解いたことを証明したいとする。数独パズルは、行、列、3x3マスの全てが1-9の数字で構成される必要がある。aは、不正できないシステムを組み上げ、bとその仲間に証明する。aのシステムは誰が見ても明確であり、誰でも確認できるプロトコルで証明する。

1. パズルの生成とカードの配置:

   aは、まだ解けていないパズルを生成し、すでに判明している数字の上に、同じ数字の3枚のカードを置く。例えば、C3のセルには9のカードが3枚置かれる。

2. 答えの伏せたカードの配置:

   次に、aは解答を伏せたカードで、同じように3枚ずつ置いていく。この時点でbはカードを見てはいけない。

3. カードの内容の確認手順:

   まず行から始めて、列、3x3のマスのカードを確認していく。行1のカードだけを集め、9枚のカードの束を伏せたまま集めていく。この手順を行、列、3x3のマスごとに繰り返し、合計27束（行9束、列9束、3x3のマス9束）を作る。

4. 各束をシャッフルしてbに渡す:

   各束をシャッフルしてbに渡す。

5. カードの確認:

   bはカードを裏返し、1~9の数字が漏れなく重複なく含まれているか確認する。シャッフルされたカードなので、初期順には並んでいない。

この確認作業の後、bとその仲間たちは、aが数独パズルを確かに解いたことを確認する。27束全てが1-9の数字のみで構成されていれば、数独パズルを解いたことになる。

非対話証明の例では、aが証明したことをシステム（コード）を使って誰もが確認できる。手順が明確なため、直接aに問い合わせずとも、証明の結果だけで確認することができる。

参考文献

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

関連項目

• 暗号理論