Loading article…
暗号学において、ゼロ知識証明（ ZK証明またはZKPとも呼ばれる）とは、ある当事者（証明者）が、検証者に対して、ある命題が真であるという事実以外の情報を一切伝えずに、その命題が真であることを納得させることができるプロトコルである。[ 1 ]ゼロ知識証明が自明でない理由の直感は、関連情報を開示するだけでその情報の所有を証明することは容易であるのに対し、その情報（またはそのいかなる側面も）を開示せずにその所有を証明することは難しいということである。[ 2 ]
ある主張の証明は、その主張に関連する特定の秘密情報を持っている場合にのみ生成できるという事実に鑑みると、検証者は、ゼロ知識証明によってその主張の真実性を確信した後でも、その主張を他の第三者に証明することはできないはずである。
ゼロ知識証明は、証明者と検証者が何らかのプロトコルに従ってメッセージを交換する対話型、または検証者が単一の証明者メッセージで納得し、他の通信が不要となる非対話型のいずれかになります。標準モデルでは、 BPP問題の自明な証明を除いて、対話が必要です。[ 3 ]一般的なランダム文字列モデルとランダムオラクルモデルでは、非対話型のゼロ知識証明が存在します。Fiat –Shamirヒューリスティックを使用すると、特定の対話型ゼロ知識証明を非対話型に変換できます。[ 4 ] [ 5 ] [ 6 ]
数学を使わないゼロ知識証明の一例として、ペギーがビクターに、自分が52枚の標準的なトランプのデッキから赤いカードを引いたことを証明したい場合を考えてみましょう。ただし、どの赤いカードを引いたかはビクターには明かしません。ビクターはペギーがシャッフルされたデッキからランダムにカードを引くのを観察しますが、ペギーはカードを裏向きにしたままにしておくので、ビクターには見えません。
ペギーは自分のカードが赤であることを証明するために、残りの51枚のカードをデッキから取り出し、26枚の黒いカード（スペード13枚とクラブ13枚）を1枚ずつ表向きにしてビクターに見せます。標準的なトランプのデッキには赤のカードが26枚、黒のカードが26枚入っており、ペギーはすべての黒のカードがデッキに残っていることを証明したため、ビクターはペギーが隠したカードが赤であると確信できます。
この証明はゼロ知識証明である。なぜなら、ビクターはペギーのカードが赤であることしか知らず、それがハートかダイヤか、あるいは彼女がどの赤いカードを持っているかといった情報は得られないからである。ペギーがハートのエースを持っていた場合でも、ダイヤの2を持っていた場合でも、この証明は同様に説得力を持つ。さらに、たとえやり取りが録画されたとしても、録画によってペギーの具体的なカードが将来の観察者に知られることはないため、ゼロ知識証明の性質は維持される。
ペギーが嘘をついていて、実際に黒いカードを持っていたとしても、残りのデッキから26枚の黒いカードすべてを取り出すことはできないため、欺瞞は不可能となる。これは証明システムの健全性を示している。標準的なトランプを使ったこの種の物理的なゼロ知識証明は、参加者が日常的な物体を使って安全な計算を実行できるようにする、より広範なカードベースの暗号プロトコルのクラスに属する。[ 7 ]
ゼロ知識証明のもう1つのよく知られた例は、「ウォーリーを探せ」の例です。この例では、証明者は「ウォーリーを探せ」の子供向け絵本から1ページを持っており、そこには何百もの漫画のキャラクターが描かれていますが、そのうちの1人だけが視覚的に特徴的なキャラクターであるウォーリーです。証明者は、検証者にウォーリーの位置を明かすことなく、自分がページ上のウォーリーの位置を知っていることを検証者に証明したいのです。[ 8 ]
証明者は、ウォルドの大きさの小さな穴が開いた大きな黒いボードを用意することから始める。ボードは本の縦横2倍の大きさなので、検証者は証明者がボードをページのどこに置くのかを見ることができない。次に証明者は、ウォルドが穴に入るようにボードをページの上に置く。[ 8 ]
検証者は穴を通してウォルドを見ることができるが、ページの他の部分は見ることができない。したがって、証明者はウォルドの位置に関する他の情報を一切明らかにすることなく、ウォルドがどこにいるかを知っていることを検証者に証明したことになる。[ 8 ]
この例は、証明者がウォルドーの位置、例えば体の位置などの情報を開示しているため、完全なゼロ知識証明とは言えません。しかし、ゼロ知識証明の基本的な概念を理解する上で、適切な例と言えるでしょう。
ゼロ知識証明の基本概念を紹介する有名な物語があり、1990 年にJean-Jacques Quisquaterらが論文「How to Explain Zero-Knowledge Protocols to Your Children」で初めて発表しました。[ 9 ]ゼロ知識証明の物語に登場する 2 つの当事者は、ステートメントの証明者であるPeggyと、ステートメントの検証者であるVictorです。
この物語では、ペギーは洞窟にある魔法の扉を開けるための秘密の言葉を発見します。洞窟はリング状になっており、片側に入り口があり、反対側には魔法の扉が閉ざされています。ビクターはペギーが秘密の言葉を知っているかどうかを知りたがりますが、ペギーは非常に内向的な性格なので、ビクターにその知識（秘密の言葉）を明かしたくないし、世間にもその事実を知られたくないと思っています。
彼らは入口から続く道をAとBと名付ける。まず、ペギーが洞窟に入る間、ビクターは洞窟の外で待つ。ペギーはAかBのどちらかの道を進むが、ビクターはどちらの道を選んだかを見ることは許されない。次に、ビクターは洞窟に入り、ペギーに帰ってくる際に使ってほしい道の名前（AかBのどちらか、ランダムに選ばれたもの）を叫ぶ。ペギーが本当に魔法の言葉を知っていれば、これは簡単だ。必要であれば扉を開け、指定された道をたどって戻る。
しかし、仮に彼女がその単語を知らなかったとしましょう。その場合、ビクターが彼女が入ってきたのと同じ道の名前を教えてくれれば、彼女はその名前のついた道を通って戻ることができます。ビクターはAかBをランダムに選ぶので、彼女が正しく推測できる確率は50%です。このトリックを何度も、例えば20回連続で繰り返すと、彼女がビクターのすべての要求をうまく予測できる確率は2分の1 、つまり9.54×10⁻⁷にまで 減少 します。
したがって、ペギーがビクターが指定した出口に繰り返し現れる場合、ビクターはペギーが実際に秘密の言葉を知っている可能性が極めて高いと結論づけることができる。
第三者の観察者に関して言えば、たとえビクターが取引全体を記録する隠しカメラを装着していたとしても、カメラが記録するのは、ビクターが「A！」と叫び、ペギーがAに現れる場面か、ビクターが「B！」と叫び、ペギーがBに現れる場面のどちらか一方だけです。このような記録は、2人であれば簡単に偽造できます（ビクターが叫ぶAとBの順番をペギーとビクターが事前に合意するだけで済みます）。このような記録は、元の参加者以外には決して説得力を持つものではありません。実際、元の実験に観察者として立ち会っていた人でさえ、納得しないはずです。なぜなら、ビクターとペギーは最初から最後まで「実験」全体を仕組むことができた可能性があるからです。
さらに、ビクターがカメラの前でコインを投げてAとBを選んだ場合、このプロトコルはゼロ知識性を失います。カメラの前でのコイン投げは、後で録画を見た人にとっては説得力があるでしょう。したがって、これはビクターに秘密の言葉を明かすものではありませんが、ペギーがその知識を持っているとビクターが世間に信じ込ませることを可能にしてしまいます。これはペギーの表明した希望に反します。しかし、デジタル暗号は一般的に、擬似乱数発生器に依存して「コインを投げる」ことを行います。これは、コインの所有者だけが知っている固定の表と裏のパターンを持つコインに似ています。ビクターのコインがこのように振る舞った場合、ビクターとペギーが実験を偽装することも可能になるため、擬似乱数発生器を使用しても、コインを投げた場合と同じようにペギーの知識が世間に知られることはありません。
ペギーは、魔法の言葉を明かすことなく、たった一度の試みでビクターに自分が魔法の言葉を知っていることを証明できる。ビクターとペギーが一緒に洞窟の入り口に行けば、ビクターはペギーがAから入り、Bから出てくるのを目撃できる。こうすれば、魔法の言葉をビクターに明かすことなく、ペギーが魔法の言葉を知っていることを確実に証明できる。しかし、このような証明は第三者が目撃したり、ビクターが記録したりする可能性があり、誰にとっても説得力のある証拠となるだろう。つまり、ペギーはビクターと共謀したと主張してこの証明を否定することはできず、したがって、誰が自分の知識を知っているかをコントロールできなくなってしまうのだ。
ビクターは赤緑色覚異常（ペギーはそうではない）で、ペギーは赤と緑の2つのボールを持っているが、それ以外は全く同じだと想像してください。ビクターには、ボールは全く同じに見えます。ビクターは、ボールが実際に区別できるのかどうか疑っています。ペギーは、ボールの色が実際には違うことをビクターに証明したいのですが、それ以外のことは何も証明したくありません。特に、ペギーはどちらが赤いボールでどちらが緑のボールなのかを明かしたくないのです。
証明システムは次のとおりです。ペギーは2つのボールをビクターに渡し、ビクターはそれらを背中に隠します。次に、ビクターはボールの1つを背中から取り出して見せます。そして、それを再び背中に隠し、2つのボールのうち1つだけをランダムに、等しい確率で選び出して見せます。ビクターはペギーに「ボールを入れ替えましたか？」と尋ねます。この手順は必要に応じて何度でも繰り返されます。
ボールの色を見れば、ペギーは当然、ボールを入れ替えたかどうかを確実に判断できる。一方、ボールの色が同じで区別がつかない場合、ペギーがボールを入れ替えたかどうかを判断する能力は、当てずっぽうと変わらない。ペギーがそれぞれのボールの入れ替え／入れ替えなしをランダムに正しく識別できる確率は50%なので、すべてのボールの入れ替え／入れ替えなしをランダムに正しく識別できる確率はゼロに近づく。
複数回の試行を重ねると、成功率は統計的に50%に収束し、ペギーは偶然よりも有意に優れた成績を収めることはできないだろう。ペギーとビクターがこの「証明」を複数回（例えば20回）繰り返せば、ビクターはボールの色が実際に異なると確信するはずだ。
上記の証明はゼロ知識証明である。なぜなら、ビクターはどのボールが緑でどのボールが赤かを決して知ることができないからである。実際、彼はボールを区別する方法について何の知識も得ない。[ 10 ]
ある命題のゼロ知識証明は、次の3つの性質を満たさなければならない。
これらのうち最初の2つは、より一般的な対話型証明システムの特性です。3つ目は、証明をゼロ知識にするものです。[ 11 ]
ゼロ知識証明は、数学的な意味での証明ではありません。なぜなら、不正な証明者が検証者を誤った主張に納得させてしまう可能性がわずかに存在するからです（これを健全性エラーと呼びます）。言い換えれば、ゼロ知識証明は決定論的な証明ではなく、確率的な「証明」です。しかし、健全性エラーを無視できるほど小さな値にまで減らす技術は存在します（例えば、100または1000の二値決定で正しく推測した場合の健全性エラーは、それぞれ1/2 100または1/2 1000です。ビット数が増えるにつれて、健全性エラーはゼロに近づきます）。
ゼロ知識の正式な定義には、何らかの計算モデルを用いる必要があり、最も一般的なのはチューリングマシンである。P 、V、Sをチューリングマシンとする。言語Lに対する( P , V )を用いた対話型証明システムは、任意の確率的多項式時間(PPT)検証器に対して、が成り立つ場合にゼロ知識である。次のようなPPTシミュレータSが存在する。
ビュー[ P ( x ) ↔( x , z )]は、 P ( x )とV ( x , z )の間の相互作用の記録です。証明者Pは、無制限の計算能力を持つものとしてモデル化されています (実際には、Pは通常、確率的チューリング マシンです)。直感的に、定義は、対話型証明システム( P , V )がゼロ知識であるとは、任意の検証者に対して、効率的なシミュレータSが存在する（Pと任意の入力に対して。定義中の補助文字列zは「事前知識」（ランダムなコインを含む）の役割を果たします。)定義は、S は、 Pとの会話から情報を抽出するのに、事前知識文字列zを使用することはできません。なぜなら、Sにもこの事前知識が与えられれば、S は P との会話を再現できてしまうからです。そしてPは以前と同じだった。
与えられた定義は完全なゼロ知識の定義である。計算上のゼロ知識は、検証者の見解が補助文字列が与えられた場合、シミュレータは計算上のみ区別がつかない。 [ 12 ]
これらのアイデアは、より現実的な暗号化アプリケーションに適用できます。ペギーは、特定のグループ内の特定の値の離散対数を知っていることをビクターに証明したいと考えています。[ 13 ]
例えば、値y、大きな素数p、および生成元が与えられた場合彼女は、 xを明かさずに、g x ≡ y (mod p )となるような値xを知っていることを証明したいと考えている。実際、xの知識は身元証明として使用できる。なぜなら、ペギーは誰にも明かさないランダムな値xを選択し、 y = g x mod pを計算し、 yの値をすべての潜在的な検証者に配布したため、後日、xの知識を証明することは、ペギーとしての身元を証明することと同等になるからである。
プロトコルは次のように進行します。各ラウンドで、ペギーは乱数rを生成し、C = g r mod pを計算して、これをビクターに開示します。C を受け取った後、ビクターは次の 2 つの要求のいずれかをランダムに発行します。ペギーにrの値または( x + r ) mod ( p − 1)の値の開示を要求します。
ビクターはどちらの答えも検証できます。もし彼がr を要求したなら、g r mod pを計算して、それがCと一致することを検証できます。もし彼が( x + r ) mod ( p − 1)を要求したなら、 g ( x + r ) mod ( p − 1) mod pを計算して、それが( C · y ) mod pと一致することを検証することで、 Cがこれと矛盾しないことを検証できます。ペギーが実際にxの値を知っているなら、ビクターのどちらの質問にも答えることができます。
ペギーがビクターがどのチャレンジを出すかを知っているか、推測できる場合、彼女は簡単に騙して、実際には知らないのにxを知っているとビクターを納得させることができる。ビクターがrを要求すると知っている場合、彼女は通常通り、rを選び、C = g r mod pを計算し、Cをビクターに開示する。彼女はビクターのチャレンジに答えることができる。一方、ビクターが( x + r ) mod ( p − 1)を要求すると知っている場合、彼女はランダムな値r ′を選び、C ′ ≡ g r ′ · ( g x ) − 1 mod pを計算し、C ′をビクターが期待しているCの値として開示する。ビクターが彼女に( x + r ) mod ( p − 1)を明らかにするように要求すると、彼女はr ′を明らかにします。ビクターはこれに対して一貫性を検証します。なぜなら、彼は次にg r ′ mod pを計算し、それがC ′ · yと一致するからです。これは、ペギーがyのモジュラー乗法逆数を掛けたためです。
しかし、上記のシナリオのいずれにおいても、ビクターが彼女が予想していたものとは異なる、彼女が結果を捏造したものではない課題を発した場合、彼女はこのグループの離散対数を解くことが不可能であるという前提の下では、その課題に応答することができません。彼女がr を選択し、 C = g r mod pを開示した場合、彼女はx を知らないため、ビクターの検証を通過する有効な( x + r ) mod ( p − 1)を生成することができません。また、彼女が( x + r ) mod ( p − 1)として現れる値r ′ を選択した場合、彼女は開示した値の離散対数で応答する必要がありますが、ペギーは、開示した値Cが既知の値を用いた算術によって得られたものであり、既知の指数を用いたべき乗の計算によって得られたものではないため、この離散対数を知りません。
したがって、不正行為を行う証明者が1回のラウンドで不正行為に成功する確率は0.5である。十分な数のラウンドを実行することで、不正行為を行う証明者が成功する確率を任意に低くすることができる。
上記の対話型証明が、ペギーがx を知っているという事実以外には何も知識を与えないことを示すには、上記の完全性と健全性の証明で使用したのと同様の議論を使用できます。具体的には、 x を知らないシミュレーター、例えば Simon は、次の手順でペギーと Victor の間のやり取りをシミュレートできます。まず、Simon は公平なコインをランダムに投げます。結果が「表」の場合、ランダムな値rを選択し、C = g r mod pを計算し、C をペギーから Victor へのメッセージであるかのように公開します。次に、Simon は、Victor からペギーに送られたかのように「rの値を要求します」というメッセージを出力し、すぐにrの値をペギーからVictor に送られたかのように出力します。これで 1 ラウンドが完了します。一方、コイン投げの結果が「裏」の場合、サイモンは乱数r ′を選択し、C ′ = g r ′ · y − 1 mod pを計算し、C ′をペギーからビクターへのメッセージであるかのように公開します。次に、サイモンは「 ( x + r ) mod ( p − 1)の値を要求します」をビクターからペギーへのメッセージであるかのように出力します。最後に、サイモンはr ′の値をペギーからビクターへの応答であるかのように出力します。これで 1 ラウンドが完了します。完全性と健全性を証明する際のこれまでの議論により、サイモンによってシミュレートされた対話型通信は、ペギーとビクター間の実際の通信と区別がつきません。したがって、ゼロ知識性が保証されます。
このシナリオでは、ペギーは大きなグラフGのハミルトン閉路を知っています。ビクターはGは知っていますが、閉路は知りません（例えば、ペギーがGを生成してビクターに明かしたなど）。大きなグラフからハミルトン閉路を見つけることは、対応する決定問題がNP完全であることが知られているため、計算上不可能だと考えられています。ペギーは、単に閉路を明かすことなく、自分が閉路を知っていることを証明します（おそらくビクターは閉路の購入に興味があるが、まず検証を求めているか、あるいはペギーだけがこの情報を知っていて、ビクターに自分の正体を証明しているのかもしれません）。
ペギーがこのハミルトン閉路を知っていることを示すために、彼女とビクターは数ラウンドのゲームを行う。
グラフへのコミットメントは、2番目のケースで、サイクルが実際にHのエッジで構成されていることをビクターが検証できるようなものでなければならない。これは、例えば、各エッジ（またはエッジの欠如）に個別にコミットすることによって行うことができる。
ペギーがGにおけるハミルトン閉路を知っている場合、彼女はビクターの要求を容易に満たすことができる。要求されるのは、GからHを生成するグラフ同型性（これは彼女が最初のステップで約束していたもの）か、Hにおけるハミルトン閉路（これはGの閉路に同型性を適用することで構築できる）のどちらかである。
ペギーの回答からは、 Gの元のハミルトン閉路は明らかになりません。各ラウンドで、ビクターは H の G との同型性、または H のハミルトン閉路のいずれかしか知ることができません。Gの閉路を発見するには、単一のHに対して両方の回答が必要となるため、ペギーが各ラウンドで異なるHを生成できる限り、情報は不明のままです。ペギーがGのハミルトン閉路を知らないが、ビクターが各ラウンドで何を見るよう要求するかを事前に知っていた場合、ペギーは不正行為を行うことができます。例えば、ビクターがHのハミルトン閉路を見るよう要求することをペギーが事前に知っていた場合、ペギーは無関係なグラフのハミルトン閉路を生成できます。同様に、ビクターが同型性を見るよう要求することをペギーが事前に知っていた場合、ペギーは単に同型なグラフHを生成できます(このグラフでもペギーはハミルトン閉路を知りません)。ビクターは、何を見るよう要求するかを知っているため、ペギーなしでプロトコルをシミュレートできます。したがって、ビクターは各ラウンドで明らかになる情報から、Gにおけるハミルトン閉路に関する情報を何も得ることができない。
ペギーがその情報を知らない場合、ビクターがどの質問をするかを推測し、Gと同型なグラフ、または無関係なグラフのハミルトン閉路を生成することはできますが、Gのハミルトン閉路を知らないため、両方を行うことはできません。この推測に基づくと、ビクターを騙せる確率は2 − nです。ここでnはラウンド数です。現実的に考えて、この方法で妥当なラウンド数でゼロ知識証明を破ることは、極めて困難です。
ゼロ知識のさまざまなバリアントは、シミュレータの出力が実際の証明プロトコルの実行に「似ている」という直感的な概念を、以下の方法で形式化することによって定義できます。
ゼロ知識証明には様々な種類がある。
ゼロ知識証明方式は、ハッシュベース暗号、ペアリングベース暗号、マルチパーティ計算、格子ベース暗号など、さまざまな暗号プリミティブから構築できます。
一般的に、ゼロ知識証明は、プライバシーを維持しながら正直な行動を強制するためにプロトコル内で使用されます。大まかに言うと、ゼロ知識証明を使用して、ユーザーに自分の行動がプロトコルに従って正しいことを証明させるという考え方です。[ 1 ] [ 16 ]
ゼロ知識証明の研究は、認証システムにおいて、一方の当事者が秘密情報（パスワードなど）を用いて他方の当事者に自身の身元を証明したいが、他方の当事者にはその秘密情報を知られたくないという状況から生まれた。これは「知識のゼロ知識証明」と呼ばれる。しかし、パスワードは通常、小さすぎるか、ランダム性が不十分であるため、多くの知識のゼロ知識証明方式には適さない。パスワードのゼロ知識証明は、パスワードのサイズ制限に対処する特殊な知識のゼロ知識証明である。
2015年4月、多数の中から1つが証明するプロトコル（シグマプロトコル）が導入されました。[ 17 ] 2021年8月、アメリカのウェブインフラストラクチャおよびセキュリティ企業であるCloudflareは、ベンダーのハードウェアを使用してプライベートウェブ検証に多数の中から1つが証明するメカニズムを使用することを決定しました。[ 18 ]
2016年、プリンストン・プラズマ物理研究所とプリンストン大学は、将来の核軍縮交渉に適用できる可能性のある技術を実証した。この技術により、査察官は内部構造（秘密である可能性がある）を記録、共有、または開示することなく、対象物が実際に核兵器であるかどうかを確認できる。[ 19 ]
ゼロ知識証明は、 Zerocoinおよび Zerocash プロトコルに適用され、2016 年にZcoin [ 20 ] (後に2020 年にFiroにブランド変更) [ 21 ]およびZcash暗号通貨の誕生につながりました。Zerocoin には、匿名性を確保するためにピアや中央集権的なミキシング プロバイダーを信頼しない組み込みのミキシング モデルがあります。[ 20 ]ユーザーは基本通貨で取引を行い、その通貨を Zerocoin に出し入れすることができます。[ 22 ] Zerocash プロトコルは、同様のモデル (非対話型ゼロ知識証明として知られるバリアント) [ 23 ]を使用していますが、Zerocoin ではできないのに対し、Zerocash では取引金額を隠すことができます。
2018年にBulletproofsが導入されました。Bulletproofsは、信頼できるセットアップを必要としない非対話型ゼロ知識証明の改良版です。[ 24 ]
パスポートや電子メールなどの文書における非対称署名のため、個人の身元をゼロ知識証明することで、個人に関する情報を非公開で検証できます。たとえば、18歳以上の年齢を示す有効な政府鍵で署名されたパスポートを所有していることをゼロ知識で証明することで、氏名や出身国などの他の詳細を明かすことなく、ウェブサイトに対して自分が18歳以上であることを証明できます。[ 25 ]同様に、電子メールのDKIM署名のゼロ知識証明を行うことで、ドメインやコンサートチケットを注文または譲渡したこと、ソーシャルメディアサービスでハンドルを所有していること、または電子商取引サービスで何かを注文したことを証明できます。[ 26 ]ゼロ知識の特性により、人々は自分の身元と電子メールアドレスを非公開にしたままこれを行うことができます。これらは、非公開で公正な選挙[ 27 ] 、低料金の二次市場[ 28 ] 、および内部告発サービス[ 29 ]を実現するために使用できます。
関連する研究分野として、いわゆるゼロ知識「コプロセッサ」を介してデータベース分析にゼロ知識証明を適用するものがあります。これは、クエリを実行し、結果と、改ざんされていないデータに対して計算が正しく実行されたことの証明の両方を返すオフチェーンシステムです。学術的なプロトタイプでは、入力を隠蔽し、結果の正しさを保証しながら、アドホックな SQL クエリの ZK 証明を生成する方法が示されています (例: ZKSQL)。[ 30 ]
ゼロ知識証明は、1985 年にShafi Goldwasser、Silvio Micali、Charles Rackoffの論文「対話型証明システムの知識複雑性」で初めて考案されました。[ 1 ]この論文では、対話型証明システムの IP 階層 (対話型証明システムを参照) を紹介し、証明者から検証者に伝達される証明に関する知識の量を測る知識複雑性の概念を考案しました。また、 mを法とする二次非剰余を決定するという具体的な問題に対する最初のゼロ知識証明も示しました。この画期的な論文は、 László BabaiとShlomo Moranの論文とともに、対話型証明システムを発明し、5 人の著者全員が 1993 年に第 1 回ゲーデル賞を受賞しました。
ゴールドワッサー、ミカリ、ラコフは、彼ら自身の言葉で次のように述べている。
特に興味深いのは、この追加知識が実質的にゼロである場合で、追加知識をゼロにすることで、ある数が法mで剰余を持たない二次数であることを対話的に証明できることを示します。これは驚くべきことです。なぜなら、 mがゼロの場合、法mで剰余を判定する効率的なアルゴリズムは知られていないからです。の素因数分解は与えられていません。さらに、この問題に関する既知のNP証明はすべて、 mの素因数分解を示しています。これは、証明プロセスに相互作用を加えることで、定理を証明するために伝達する必要のある知識の量を減らすことができる可能性があることを示しています。
二次非剰余問題にはNPアルゴリズムとco-NPアルゴリズムの両方があり、NPとco-NPの交点に位置する。これは、後にゼロ知識証明が発見された他のいくつかの問題にも当てはまり、例えば、2素数の法がBlum整数ではないことを検証するOded Goldreichによる未発表の証明システムなどが挙げられる。[ 31 ]
Oded Goldreich、Silvio Micali、およびAvi Wigderson は、これをさらに一歩進め、解読不可能な暗号化の存在を仮定すれば、3 色の NP 完全グラフ彩色問題に対するゼロ知識証明システムを作成できることを示しました。NP のすべての問題は効率的にこの問題に還元できるため、この仮定の下では、NP のすべての問題にゼロ知識証明が存在することになります。[ 32 ]この仮定の理由は、上記の例のように、彼らのプロトコルには暗号化が必要だからです。解読不可能な暗号化の存在に対するよく引用される十分条件は、一方向関数の存在ですが、物理的な手段によってもそれが実現できる可能性があります。
さらに、彼らはグラフ同型問題の補問題であるグラフ非同型問題にもゼロ知識証明が存在することを示した。この問題はco-NPに属するが、現在NPまたは実用的なクラスに属することは知られていない。より一般的には、Russell ImpagliazzoとMoti Yung、およびBen-Orらは、一方向関数または解読不可能な暗号化を仮定すると、 IP = PSPACEのすべての問題に対してゼロ知識証明が存在すること、言い換えれば、対話型証明システムで証明できるものはすべてゼロ知識で証明できることを示した。[ 33 ] [ 34 ]
不必要な仮定をすることを好まない多くの理論家は、一方通行関数の必要性を排除する方法を模索した。その方法の一つが、マルチプロバー対話型証明システム（対話型証明システムを参照）であり、これは1つのプロバーだけでなく複数の独立したプロバーを持ち、検証者がプロバーを個別に「相互検証」して誤解を避けることができる。このようなシステムでは、いかなる難解性の仮定もなしに、NPのすべての言語がゼロ知識証明を持つことが示される。[ 35 ]
インターネットのような環境では、複数のプロトコルが同時に実行される可能性があるため、ゼロ知識証明の構築はより困難であることが判明しました。同時実行ゼロ知識証明を調査する研究の流れは、Dwork、Naor、およびSahaiの研究によって開始されました。[ 36 ]この流れに沿った特定の開発の1つは、証人不可分証明プロトコルの開発です。証人不可分性の特性はゼロ知識の特性に関連していますが、証人不可分プロトコルは同時実行の同じ問題に悩まされません。[ 37 ]
ゼロ知識証明の別のバリアントとして、非対話型ゼロ知識証明がある。Blum、Feldman、Micaliは、証明者と検証者の間で共有される共通のランダムな文字列があれば、対話を必要とせずに計算的ゼロ知識を達成できることを示した。[ 5 ] [ 6 ]
最も普及している対話型または非対話型のゼロ知識証明(zk-SNARK など) プロトコルは、次の 4 つのカテゴリに大別できます。簡潔な非対話型知識引数 (SNARK)、スケーラブルな透過的知識引数 (STARK)、検証可能な多項式委任 (VPD)、簡潔な非対話型引数 (SNARG)。ゼロ知識証明プロトコルとライブラリのリストは、透明性、普遍性、妥当なポスト量子セキュリティ、プログラミング パラダイムに基づく比較とともに以下に示されています。[ 38 ]透過的なプロトコルとは、信頼できるセットアップを必要とせず、公開乱数を使用するプロトコルです。普遍的なプロトコルとは、各回路に個別の信頼できるセットアップを必要としないプロトコルです。最後に、妥当なポスト量子プロトコルとは、量子アルゴリズムを含む既知の攻撃に対して脆弱でないプロトコルです。
While zero-knowledge proofs offer a secure way to verify information, the arithmetic circuits that implement them must be carefully designed. If these circuits lack sufficient constraints, they may introduce subtle yet critical security vulnerabilities.
One of the most common classes of vulnerabilities in these systems is under-constrained logic, where insufficient constraints allow a malicious prover to produce a proof for an incorrect statement that still passes verification. A 2024 systematization of known attacks found that approximately 96% of documented circuit-layer bugs in SNARK-based systems were due to under-constrained circuits.[59]
These vulnerabilities often arise during the translation of high-level logic into low-level constraint systems, particularly when using domain-specific languages such as Circom or Gnark. Recent research has demonstrated that formally proving determinism – ensuring that a circuit's outputs are uniquely determined by its inputs – can eliminate entire classes of these vulnerabilities.[60]
ゼロ知識仮想マシン（zkVM）は、コードを実行し、プライベートな入力を開示することなく、コードが正しく実行され、主張された結果を生成したことをオフチェーンで検証するゼロ知識証明を生成するように設計された汎用仮想コンピュータです。[ 61 ]証明は、コンパクトで構造化されたバイナリファイルであり、元の計算を再実行することなく、zkVMの検証ツールを使用して誰でも効率的にチェックできます。
zkVMには、開発とセキュリティの両方の利点があります。zkVMを使用すると、開発者は複雑な計算をオフチェーンで実行および検証できるため、オンチェーンでの高額な「ガスコスト」（ブロックチェーン処理手数料）を回避し、コードやデータのプライバシーを維持できます。RISC ZeroやSuccinct Labsなどが開発した、最近開発されたいくつかのzkVMはRISC-V命令セットをサポートしており、プログラマーはCircomなどのドメイン固有の回路言語を使用する代わりに、Rustなどの主流のプログラミング言語でコードを記述できます。 [ 62 ]他のzkVMは、 WebAssembly （WASM）をターゲットにしたり、ゼロ知識性能や特定のブロックチェーン環境との統合に最適化されたカスタム命令セットを実装したりするなど、異なるアプローチを採用しています。
![{\displaystyle \forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dc9f4c672b2807b48a34659dc71e6581baceaa9)
{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク){{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)