ゼロ知識証明のソースを表示

[[暗号学]]において、'''ゼロ知識証明'''（ぜろちしきしょうめい、zero-knowledge proof、略称：ZKP<ref>{{Cite web|和書|url=https://www.sophia-it.com/content/ZKP|title=ゼロ知識証明|website=[[IT用語辞典バイナリ]]|publisher=GRASグループ|accessdate=2023-8-26}}</ref>）とは、ある人が他の人に、自分の持っている（通常、数学的な）[[命題]]が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。'''ゼロ知識対話証明'''（ZKIP）とも呼ばれる。

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

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

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

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

ゼロ知識対話証明は、[[1985年]]の [[シャフィ・ゴールドワッサー|Goldwasser]], Micali, Rackoff たちの論文によって最初に定式化された。以来、多くの研究がなされ、ゼロ知識証明は[[暗号理論]]にとって重要な概念の一つとなった。<!-- ゼロ知識対話証明の弱いバージョンである[[シグマプロトコル]]から安全なデジタル署名方式を構成するテクニック（[[Fiat-Shamirヒューリスティック]]など）の研究、ある種のゼロ知識対話証明が存在すれば[[一方向性関数]]の存在を示せるとか；もっと調べてから加筆 -->

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

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

なお健全性よりも強い'''知識健全性（knowledge soundness）'''とよばれる性質が用いられる場合もあり、この性質は「検証者が証明を受理したならば、証明者にオラクルアクセスすることで高確率で命題に対応する証拠を抽出できる（つまり証明者の秘密を取り出せる）効率的なアルゴリズムが存在する」ことを保証する。健全性を知識健全性に置き換えた場合は'''知識のゼロ知識証明（zero-knowledge proof of knowledge）'''と呼ばれる。

==洞窟の問題==
<div class="thumb tright">
{|
|[[Image:Zkip alibaba1.png|250px]]
|-
|[[Image:Zkip alibaba2.png|250px]]
|-
|[[Image:Zkip alibaba3.png|250px]]
|}
</div>
ジャン＝ジャック・キスケータ<!-- クイズケータとカナ書きされたこともあるけど -->らの論文「我が子にゼロ知識証明をどう教えるか([http://www.thehackademy.net/madchat/crypto/papers/alibaba.pdf 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さんを追跡できない（情報を露出しない）まま証明できることが重要である。

==具体例==
以下、具体例<ref name="blum86">{{cite paper |first=Manuel |last=Blum |title=How to Prove a Theorem So No One Else Can Claim It |work=ICM Proceedings |pages=1444-1451 |year=1986 }}</ref>を示す。

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さんの質問にすべて答えきれる確率は<math>\frac{1}{2^n}</math>となる。ゼロ知識証明は、実用的な回数の繰り返しだけで破られる確率をほぼなくすことができるのである。

==非対話ゼロ知識証明==
[[w:Oded Goldreich|Goldreich]]とOrenの研究により、ゼロ知識証明を対話をせずに実行すること、すなわち、証明したい人が「証明」を作成して一方的に送りつけるだけで完了するような証明は作れないことが示されている。<ref>Oded Goldreich and Yair Oren. Definitions and Properties of Zero-Knowledge Proof Systems. Journal of Cryptology. Vol 7(1). 1–32. 1994 [http://www.wisdom.weizmann.ac.il/~oded/PS/oren.ps (PS)]</ref> しかし特殊な条件下<ref group="注釈">典型的には[[ランダムオラクル]]の存在を仮定したり、信頼のおける第三者によって生成され、誰もが参照できるCommon Reference String (CRS)の存在を仮定するといった設定が用いられる。</ref>では、対話が不要なゼロ知識証明が作れることが知られており、'''非対話ゼロ知識証明（non-interactive zero-knowledge proof; NIZK)''' と呼ばれている。NIZKの実用的な応用としては、[[デジタル署名]]や、プライバシーに配慮した[[暗号通貨]]がある。後者では、コインの取引者のアドレスや取引量などを隠したまま、取引が正当であることを証明するのにNIZKが利用できる。<ref>{{Cite news|url=https://www.technologyreview.com/s/609448/a-mind-bending-cryptographic-trick-promises-to-take-blockchains-mainstream|title=A mind-bending cryptographic trick promises to take blockchains mainstream|last=Orcutt|first=Mike|date=|work=MIT Technology Review|access-date=2017-12-18|archive-url=|archive-date=|dead-url=|language=en}}</ref>

==脚注==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{reflist}}

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

==関連項目==
* [[暗号理論]]

{{Cryptography navbox}}

{{DEFAULTSORT:せろちしきしようめい}}
[[Category:暗号技術]]
[[Category:数学に関する記事]]