ゼロ知識証明

暗号学において、ゼロ知識証明とは、一方の当事者（証明者）が他方の当事者（検証者）に対して、ある文が真実であるという事実以上の情報を検証者に伝えることなく、その文が真実であると納得させることができるプロトコルである。^[1]ゼロ知識証明の根底にある直感は、関連情報を単に明らかにするだけで、その情報を所有していることを証明するのは簡単であるということであり、難しいのは、この情報（またはそのいかなる側面も）を明らかにせずに、この所有を証明することである。^[2]

ある陳述の証明は、その陳述に関連する特定の秘密情報を所有している場合にのみ生成できるはずであるという事実を考慮すると、検証者は、その陳述が真実であると確信した後でも、第三者に対してその陳述を証明することができないままであるべきである。

ゼロ知識証明は対話型、つまり証明者と検証者が何らかのプロトコルに従ってメッセージを交換するか、非対話型、つまり検証者が単一の証明者メッセージで納得し、他の通信を必要としないものである。標準モデルでは、 BPP問題の簡単な証明を除いて、対話が必要である。 ^[3]一般的なランダム文字列モデルとランダムオラクルモデルでは、非対話型のゼロ知識証明が存在する。フィアット・シャミールのヒューリスティックは、特定の対話型ゼロ知識証明を非対話型証明に変換するために使用できる。^{[4] [5] [6]}

ゼロ知識証明の基本的な考え方を紹介する有名な話があります。これは、1990年にジャン=ジャック・キスカターらが論文「ゼロ知識プロトコルを子供に説明する方法」で初めて発表したものです。^[7]ゼロ知識証明の話の2つの当事者は、ステートメントの証明者であるペギーと、ステートメントの 検証者であるビクターです。

この物語では、ペギーは洞窟の魔法の扉を開けるのに使う秘密の言葉を発見しました。洞窟はリングの形をしており、片側に入り口があり、反対側は魔法の扉で塞がれています。ビクターはペギーが秘密の言葉を知っているかどうか知りたがりますが、ペギーは非常に内向的な性格なので、ビクターに自分の知識 (秘密の言葉) を明かしたり、自分が知っているという事実を世間に公表したりしたくありません。

入り口から左と右の道に A と B のラベルを貼ります。まず、ビクターはペギーが洞窟に入るのを外で待ちます。ペギーは A か B の道を選びます。ビクターはペギーがどちらの道を選ぶかを見ることはできません。次にビクターは洞窟に入り、ペギーが戻るときに使ってほしい道の名前を叫びます。A か B のどちらかで、ランダムに選ばれます。ペギーが本当に魔法の言葉を知っているなら、これは簡単です。ペギーは必要に応じてドアを開け、希望の道に沿って戻ります。

しかし、彼女がその単語を知らなかったとしましょう。その場合、彼女がその名前のついた道を通って戻ることができるのは、ビクターが彼女が入ってきたのと同じ道の名前を言った場合に限られます。ビクターは A か B をランダムに選ぶので、彼女が正しく推測できる確率は 50% です。このトリックを何度も繰り返した場合、たとえば 20 回続けて行った場合、彼女がビクターの要求をすべて予測できる確率は 2 ²⁰分の 1 、つまり 9.56  ×  10 ⁻⁷に減少します。

したがって、ビクターが指定した出口にペギーが繰り返し現れる場合、ペギーが実際に秘密の言葉を知っている可能性が非常に高いとビクターは結論付けることができます。

第三者の観察者に関する補足事項: ビクターがすべてのやり取りを記録する隠しカメラを装着していたとしても、カメラが記録するのは、ビクターが「A!」と叫んでペギーが A に現れるシーン、またはビクターが「B!」と叫んでペギーが B に現れるシーンだけです。このような記録は、2 人が偽造するのは簡単です (ペギーとビクターが、ビクターが叫ぶ A と B の順序について事前に合意しておくことだけが必要です)。このような記録は、元の参加者以外には絶対に納得のいくものではありません。実際、元の実験に観察者として立ち会っていた人でさえ納得できないでしょう。なぜなら、ビクターとペギーが最初から最後まで「実験」全体を仕組んでいた可能性があるからです。

さらに、ビクターがカメラの前でコインを投げて A と B を選んだ場合、このプロトコルはゼロ知識特性を失います。カメラの前でコインを投げることは、後で録画を見た人にとってはおそらく説得力のあるものになるでしょう。したがって、これはビクターに秘密の言葉を明らかにしませんが、ペギーがその知識を持っているとビクターが一般に世界に納得させることは可能です。これはペギーの表明した希望に反します。ただし、デジタル暗号化では一般に、疑似乱数ジェネレーターに頼って「コインを投げる」ことになります。これは、コインの所有者だけが知っている表と裏の固定パターンを持つコインに似ています。ビクターのコインがこのように動作した場合、ビクターとペギーが実験を偽造することも可能になるため、疑似乱数ジェネレーターを使用しても、コインを投げた場合と同じようにペギーの知識が世界に明らかになることはありません。

ペギーは、魔法の言葉を明かさずに、一度の試行で、自分が魔法の言葉を知っていることをビクターに証明することができます。ビクターとペギーが一緒に洞窟の入り口に行けば、ビクターはペギーが A から入って B から出てくるのを見ることができます。これは、魔法の言葉をビクターに明かさずに、ペギーが魔法の言葉を知っていることを確実に証明します。しかし、そのような証明は第三者によって観察されるか、ビクターによって記録される可能性があり、そのような証明は誰にとっても説得力があります。言い換えれば、ペギーはビクターと共謀したと主張してそのような証明に反論することはできません。したがって、彼女はもはや自分の知識を誰が知っているかを制御できません。

あなたの友人「ビクター」が赤緑色盲（あなたはそう）で、あなたには赤と緑の 2 つのボールがあり、それ以外はまったく同じであると想像してください。ビクターにとって、ボールはまったく同じに見えます。ビクターは、ボールが実際に区別できるかどうか懐疑的です。あなたは、ボールが実際には異なる色であるということをビクターに証明したいだけで、それ以外は何も証明したくありません。特に、どのボールが赤で、どのボールが緑であるかを明らかにしたくはありません。

証明システムは次のとおりです。ビクターに 2 つのボールを渡すと、ビクターはそれを背中に隠します。次に、ビクターはボールの 1 つを取り、背中から取り出して見せます。次に、再び背中に隠してから、2 つのボールのうち 1 つだけを見せることにします。つまり、2 つのボールのうち 1 つを同じ確率でランダムに選びます。ビクターはあなたに「ボールを入れ替えましたか?」と尋ねます。この手順全体を必要な回数だけ繰り返します。

もちろん、ボールの色を見れば、ボールを入れ替えたかどうかを確実に判断できます。一方、ボールが同じ色で区別がつかない場合は、50% 以上の確率で正しく推測することは不可能です。

スイッチ/非スイッチをランダムに識別できる確率は 50% なので、すべてのスイッチ/非スイッチをランダムに識別できる確率はゼロに近づきます (「確実性」)。あなたと友人がこの「証明」を複数回 (たとえば 20 回) 繰り返すと、友人はボールが確かに異なる色であることを確信するはずです (「完全性」)。

上記の証明はゼロ知識です。なぜなら、あなたの友人はどのボールが緑でどれが赤であるかを決して知ることができないからです。実際、彼はボールを区別する方法について何の知識も得ません。^[8]

ゼロ知識証明のよく知られた例としては、「ウォーリーをさがせ！」の例があります。この例では、証明者は検証者にウォーリーの居場所を明かすことなく、「ウォーリーをさがせ！ 」の本のあるページのどこにウォーリーがいるかを知っていることを証明したいのです。^[9]

証明者は、ワルドと同じ大きさの小さな穴が開いた大きな黒板を用意します。黒板は両方向とも本の2倍の大きさなので、検証者は証明者がページのどこに黒板を置いているのかを見ることができません。次に、証明者はワルドが穴の中に入るように黒板をページの上に置きます。^[9]

検証者は穴を通してワルドを見ることができますが、ページの他の部分は見ることができません。したがって、証明者は検証者に対して、ワルドの居場所に関する他の情報を明かすことなく、ワルドの居場所を知っていることを証明したことになります。^[9]

この例は、証明者がワルドの体の位置など、ワルドの居場所に関する情報を明らかにしているため、完全なゼロ知識証明ではありません。ただし、ゼロ知識証明の基本概念をうまく表しています。

あるステートメントのゼロ知識証明は、次の 3 つのプロパティを満たす必要があります。

1. 完全性: ステートメントが真実である場合、正直な検証者 (つまり、プロトコルに適切に従う検証者) は、正直な証明者によってこの事実を確信します。
2. 健全性: ステートメントが偽である場合、わずかな確率を除いて、不正な証明者は正直な検証者にそれが真実であると納得させることはできません。
3. ゼロ知識: ステートメントが真実である場合、検証者はステートメントが真実であるという事実以外何も知りません。言い換えると、ステートメント (秘密ではなく) を知っているだけで、証明者が秘密を知っていることを示すシナリオを想像するのに十分です。これは、すべての検証者が、証明するステートメントのみ (証明者にアクセスできない) を与えられた場合に、正直な証明者と問題の検証者との間のやり取りのように見えるトランスクリプトを作成できるシミュレータを持っていることを示すことによって形式化されます。

最初の2つは、より一般的な対話型証明システムの特性です。3つ目は、証明をゼロ知識にするものです。^[10]

ゼロ知識証明は、数学的な意味での証明ではありません。なぜなら、不正な証明者が検証者に偽りの陳述を納得させることができる可能性(健全性誤差) がわずかにあるからです。言い換えると、ゼロ知識証明は、決定論的証明ではなく、確率的「証明」です。ただし、健全性誤差を無視できるほど小さな値に減らす手法があります (たとえば、100 または 1,000 のバイナリ決定を正しく推測すると、健全性誤差はそれぞれ 1/2 ¹⁰⁰または 1/2 ¹⁰⁰⁰になります。ビット数が増えると、健全性誤差はゼロに近づきます)。

ゼロ知識の正式な定義には何らかの計算モデルを使用する必要がありますが、最も一般的なのはチューリングマシンです。P、V、Sをチューリングマシンとします。言語Lの( P、V )を使用した対話型証明システムは、任意の確率多項式時間(PPT) 検証者V̂に対して、次のようなPPT シミュレータSが存在する場合、ゼロ知識です。

${\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),}$

ここで、ビュー_V̂ [ P ( x )↔ V̂ ( x , z )] は、 P ( x )とV ( x , z )の間の対話の記録です。証明者P は、無制限の計算能力を持つようにモデル化されています (実際には、P は通常、確率的チューリングマシンです)。直感的には、定義は、任意の検証者V̂に対して、任意の入力に対してPとV̂の間の会話を再現できる効率的なシミュレータS ( V̂に依存)が存在する場合、対話型証明システム( P、V )はゼロ知識であると述べています。定義の補助文字列z は、「事前知識」の役割を果たします ( V̂のランダムコインを含む)。定義は、V̂ が事前知識文字列z を使用してPとの会話から情報をマイニングできないことを意味します。なぜなら、 S にもこの事前知識が与えられている場合、 Sは以前と同じようにV̂とP の間の会話を再現できるからです。^{[引用が必要]}

与えられた定義は完全なゼロ知識の定義である。計算上のゼロ知識は、補助文字列が与えられた場合、検証者V̂とシミュレータのビューが計算上のみ区別できないことを要求することによって得られる。^{[引用が必要]}

これらのアイデアは、より現実的な暗号化アプリケーションに適用することができます。ペギーは、与えられたグループ内の与えられた値の離散対数を知っていることをビクターに証明したいと考えています。^[11]

たとえば、値y、大きな素数 p、およびジェネレータが与えられた場合、ペギーは、 x を明かすことなく、g ^x ≡ y (mod p )となる値xを知っていることを証明したいと考えています。実際、xの知識は、身元の証明として使用できます。ペギーがそのような知識を持っているのは、誰にも明かしていないランダムな値x を選択し、 y = g ^x mod pを計算し、 yの値をすべての潜在的な検証者に配布したためであり、後になって、xを知っていることを証明することは、ペギーとしての身元を証明することと同等になります。 ${\displaystyle g}$

プロトコルは次のように進行します。各ラウンドで、ペギーは乱数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 ) ⁻¹ 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 を知らないシミュレータ、たとえばサイモンは、次の手順でペギーとビクターの間の交換をシミュレートできます。まず、サイモンは公平なコインをランダムに投げます。結果が「表」の場合、彼はランダムな値rを選び、C = g ^r mod pを計算し、C をペギーからビクターへのメッセージであるかのように公開します。次に、サイモンは「rの値を要求」というメッセージも、ビクターからペギーに送信されたかのように出力し、すぐにrの値をペギーからビクターに送信されたかのように出力します。これで 1 ラウンドが完了します。一方、コイン投げの結果が「表」の場合、Simon は乱数r ′ を選び、 C ′ = g ^{r ′} · y ⁻¹ mod pを計算し、C ′ をPeggy から Victor へのメッセージであるかのように公開します。次に、Simon は Victor から Peggy へのメッセージであるかのように、「( x + r ) mod ( p − 1)の値を要求」を出力します。最後に、Simon はr ′の値を Peggyから Victor への応答であるかのように出力します。これで 1 ラウンドが完了します。完全性と健全性を証明する際の前の議論により、Simon によってシミュレートされた対話型通信は、Peggy と Victor 間の実際の通信と区別がつきません。したがって、ゼロ知識プロパティが保証されます。

Peggy はxの値(たとえば、自分のパスワード) を知っていることを証明します。

1. ペギーとビクターは素数pと体ℤ _pの乗法群の生成元について合意します。${\displaystyle g}$
2. ペギーはy = g ^x mod pの値を計算し、その値をビクターに転送します。
3. 次の 2 つのステップが (多数) 回繰り返されます。
   1. ペギーはランダムな値r∈U [0, p −2]を繰り返し選択し、C = g ^r mod pを計算します。彼女は値Cをビクターに転送します。
   2. ビクターはペギーに、値( x + r ) mod ( p − 1)または値rのいずれかを計算して転送するように依頼します。前者の場合、ビクターはC · y ≡ g ^{( x + r ) mod ( p − 1)} mod p であることを確認します。後者の場合、ビクターはC = g ^r mod p であることを確認します。

( x + r ) mod ( p − 1)の値は、 x mod ( p − 1)の暗号化された値と見ることができます。 r が本当にランダムで、ゼロからp − 2 の間で均一に分布している場合、 xに関する情報は漏洩しません（ワンタイムパッドを参照）。

以下の図はマヌエル・ブルムによるものです。^[12]

このシナリオでは、ペギーは大きなグラフGのハミルトン閉路を知っています。ビクターはG を知っていますが、閉路は知りません (たとえば、ペギーはG を生成し、それをビクターに公開しました)。大きなグラフが与えられた場合のハミルトン閉路を見つけることは、対応する決定バージョンがNP 完全であることがわかっているため、計算上不可能であると考えられています。ペギーは、単に公開することなく、閉路を知っていることを証明します (おそらくビクターはそれを購入することに興味があるが、まず検証を望んでいるか、またはペギーだけがこの情報を知っていて、ビクターに自分の身元を証明しているのかもしれません)。

ペギーがこのハミルトンサイクルを知っていることを示すために、彼女とビクターはゲームを数回プレイします。

• 各ラウンドの開始時に、ペギーはGと同型のグラフH を作成します(つまり、H はすべての頂点の名前が異なることを除いてG と同じです)。同型性がわかっている同型グラフ間でハミルトン閉路を変換するのは簡単なので、ペギーがGのハミルトン閉路を知っている場合は、 Hのハミルトン閉路も知っている必要があります。
• ペギーはHにコミットします。これは、暗号化コミットメント スキームを使用して行うことができます。あるいは、 Hの頂点に番号を付けることもできます。次に、 Hの各辺について、その辺が接続する 2 つの頂点を小さな紙に書きます。次に、これらの紙をすべて裏向きにしてテーブルの上に置きます。このコミットメントの目的は、ペギーがH を変更できないようにし、同時にビクターがHに関する情報を持たないようにすることです。
• 次に、ビクターは 2 つの質問のうち 1 つをランダムに選択してペギーに尋ねます。ビクターは、ペギーにHとGの同型性を示すように求めることも(グラフ同型性の問題を参照)、 Hのハミルトン閉路を示すように求めることもできます。
• ペギーが 2 つのグラフが同型であることを示すように求められた場合、彼女はまずHのすべてを明らかにし (たとえば、テーブルに置いたすべての紙を裏返す)、次にGをHにマッピングする頂点の変換を提供します。ビクターはそれらが実際に同型であることを確認できます。
• ペギーがHのハミルトン閉路を知っていることを証明するように求められた場合、彼女はGのハミルトン閉路をHに翻訳し、ハミルトン閉路のエッジのみを明らかにします。つまり、ペギーはハミルトン閉路のエッジに対応する紙片| V ( G ) |のみを裏返し、残りは裏向きのままにします。これは、ビクターがH に確かにハミルトン閉路が含まれていることを確認するのに十分です。

2 番目のケースでは、Victor がサイクルが実際にHからのエッジで構成されていることを検証できるようなグラフへのコミットメントが重要です。これは、たとえば、すべてのエッジ (またはその欠如) を個別にコミットすることによって実行できます。

ペギーがGのハミルトン閉路を知っている場合、彼女は、 GからH を生成するグラフ同型性(最初のステップで彼女がコミットしたもの) またはHのハミルトン閉路 (彼女は同型性をGの閉路に適用することで構築できる) に対するビクターの要求を簡単に満たすことができます。

ペギーの答えでは、 Gの元のハミルトン閉路は明らかにされません。各ラウンドで、ビクターはHのGへの同型性、またはHのハミルトン閉路のみを学びます。 Gの閉路を発見するには、単一のHの両方の答えが必要になるため、ペギーが各ラウンドで異なるH を生成できる限り、情報は不明のままです。ペギーがGのハミルトン閉路を知らないが、ビクターが各ラウンドで何を要求するかを事前に知っていた場合、彼女は不正行為を行うことができます。たとえば、ビクターがHのハミルトン閉路を要求することをペギーが事前に知っていた場合、彼女は無関係なグラフのハミルトン閉路を生成できます。同様に、ビクターが同型性を要求することをペギーが事前に知っていた場合、彼女は単に同型グラフHを生成できます（このグラフのハミルトン閉路も知りません）。ビクターは自分が何を要求するかを知っているため、ペギーなしでプロトコルをシミュレートできます。したがって、ビクターは各ラウンドで明らかにされた情報から Gのハミルトンサイクルに関する情報を得ることはできません。

ペギーが情報を知らない場合、ビクターがどの質問をするかを推測して、Gと同型のグラフか無関係なグラフのハミルトン閉路のいずれかを生成することができますが、 Gのハミルトン閉路を知らないため、両方を行うことはできません。この推測では、ビクターを騙せる可能性は2 ^{− n}です。ここで、nはラウンド数です。現実的には、この方法で妥当なラウンド数でゼロ知識証明を破ることは不可能に近いほど困難です。

シミュレータの出力が実際の証明プロトコルの実行に「似ている」ということの直感的な概念を次のように形式化することで、ゼロ知識のさまざまなバリエーションを定義できます。

• シミュレータと証明プロトコルによって生成された分布がまったく同じに分布している場合、完全なゼロ知識であると言えます。これは、たとえば上記の最初の例の場合です。
• 統計的ゼロ知識^[13]とは、分布が必ずしも完全に同じではないが、統計的に近いことを意味し、統計的な差は無視できる関数であることを意味します。
• 効率的なアルゴリズムで 2 つの分布を区別できない場合は、計算ゼロ知識と呼ばれます。

ゼロ知識証明にはさまざまな種類があります。

• 知識の証明: 上記の例のように、知識は指数の中に隠されています。
• 証人が区別できない証明: 検証者は、どの証人が証明の作成に使用されたかを知ることができません。

ゼロ知識証明方式は、ハッシュベース暗号化、ペアリングベース暗号化、マルチパーティ計算、格子ベース暗号化など、さまざまな暗号化プリミティブから構築できます。

ゼロ知識証明の研究は、ある当事者が秘密情報 (パスワードなど) を介して別の当事者に自分の身元を証明したいが、その秘密について別の当事者に何も知られたくないという認証システムによって動機づけられてきました。これは「ゼロ知識証明」と呼ばれます。しかし、パスワードは通常、ゼロ知識証明の多くのスキームで使用するには小さすぎたり、ランダム性が不十分であったりします。ゼロ知識パスワード証明は、パスワードのサイズ制限に対処する特別な種類のゼロ知識証明です。^{[引用が必要]}

2015年4月には、一対一証明プロトコル（シグマプロトコル）が導入されました。^[14] 2021年8月、アメリカのウェブインフラおよびセキュリティ企業であるCloudflareは、ベンダーのハードウェアを使用したプライベートウェブ検証に一対一証明メカニズムを使用することを決定しました。^[15]

暗号プロトコルにおけるゼロ知識証明の用途の 1 つは、プライバシーを維持しながら正直な行動を強制することです。大まかに言えば、ゼロ知識証明を使用して、ユーザーにプロトコルに従って行動が正しいことを証明させるという考え方です。^{[16] [17]}健全性により、有効な証明を提供するにはユーザーが本当に正直に行動しなければならないことがわかります。ゼロ知識により、ユーザーが証明を提供する過程で秘密のプライバシーを侵害しないことがわかっています。^[要出典]

2016年、プリンストンプラズマ物理学研究所とプリンストン大学は、将来の核軍縮交渉に応用できる可能性のある技術を実証した。この技術により、査​​察官は、秘密にされている可能性のある内部構造を記録、共有、または公開することなく、物体が実際に核兵器であるかどうかを確認できるようになる。^[18]

ゼロ知識証明は、 ZerocoinとZerocashのプロトコルに適用され、その結果、 2016年にZcoin ^[19]（後に2020年にFiroにブランド変更）^[20]とZcash暗号通貨が誕生しました。Zerocoinには、匿名性を確保するためにピアや中央集権型ミキシングプロバイダーを信頼しない組み込みのミキシングモデルがあります。^[19]ユーザーは基本通貨で取引し、その通貨をZerocoinに出入りさせることができます。^{[21] Zerocashプロトコルは同様のモデル（}非対話型ゼロ知識証明と呼ばれる変種）^[22]を使用していますが、Zerocoinでは取引金額を隠すことができますが、Zerocashではできません。Zerocashネットワーク上の取引データには大きな制限があるため、ZerocashはZerocoinと比較してプライバシータイミング攻撃を受けにくくなっています。ただし、この追加のプライバシーレイヤーにより、不正なコインを追跡できないため、Zerocash供給の潜在的に検出されないハイパーインフレが発生する可能性があります。^{[19] [23]}

2018年にBulletproofsが導入されました。Bulletproofsは、信頼されたセットアップが不要な非対話型ゼロ知識証明の改良版です。^[24]これは後にMimblewimbleプロトコル（GrinとBeamの暗号通貨のベース）とMonero暗号通貨に実装されました。^[25] 2019年にFiroは、信頼されたセットアップのないZerocoinプロトコルの改良版であるSigmaプロトコルを実装しました。^{[26] [14]}同じ年にFiroは、トランザクションの起源と金額を隠すSigmaプロトコルの改良版であるLelantusプロトコルを導入しました。^[27]

ゼロ知識証明は、その性質上、データ漏洩や個人情報盗難に対して脆弱なID共有システムにおけるプライバシーを強化することができます。分散型識別子システムに統合されると、ZKPはDID文書に暗号化の追加レイヤーを追加します。^[28]  

ゼロ知識証明は、1985年にシャフィ・ゴールドワッサー、シルビオ・ミカリ、チャールズ・ラックオフの論文「対話型証明システムの知識複雑性」で初めて考案されました。^[16]この論文では、対話型証明システムのIP階層（対話型証明システムを参照）が導入され、証明者から検証者に転送される証明に関する知識の量を測る尺度である知識複雑性の概念が考案されました。彼らはまた、具体的な問題であるmを法とする二次非剰余を決定するという問題に対する最初のゼロ知識証明も示しました。ラースロー・ババイとシュロモ・モランの論文とともに、この画期的な論文は対話型証明システムを発明し、5人の著者全員が1993年に第1回ゲーデル賞を受賞しました。

ゴールドワッサー、ミカリ、ラックオフは、自らの言葉でこう述べています。

特に興味深いのは、この追加知識が本質的に 0 である場合であり、数がmを法とする二次非剰余であることを対話的に証明して、 0 の追加知識を解放できることを示しています。 m の因数分解が与えられていない場合、 m を法とする二次剰余を決定する効率的なアルゴリズムは知られていないため、これは驚くべきことです。さらに、この問題に対する既知のNP証明はすべて、 mの素因数分解を示しています。これは、証明プロセスに対話を追加すると、定理を証明するために伝達する必要がある知識の量が減少する可能性があることを示しています。

二次非剰余問題にはNPアルゴリズムとco-NPアルゴリズムの両方があり、NPとco-NPの交差点にあります。これは、2素数法がブルーム整数ではないことを証明するOded Goldreichによる未発表の証明システムなど、その後ゼロ知識証明が発見された他のいくつかの問題にも当てはまります。^[29]

Oded Goldreich、Silvio Micali、Avi Wigdersonはこれをさらに一歩進め、解読不可能な暗号化が存在すると仮定すると、3色のNP完全グラフ彩色問題に対するゼロ知識証明システムを作成できることを示しました。NPのすべての問題は効率的にこの問題に還元できるため、この仮定の下ではNPのすべての問題にゼロ知識証明があることを意味します。^{[30]この仮定の理由は、上記の例のように、それらのプロトコルが暗号化を必要とするためです。解読不可能な暗号化の存在の十分な条件としてよく挙げられるのは}一方向関数の存在ですが、何らかの物理的な手段によってそれが達成される可能性もあります。

これに加えて、彼らはグラフ同型性問題の補問題であるグラフ非同型性問題にもゼロ知識証明があることを示した。この問題はco-NPに属するが、NPにも実用的なクラスにも属さないことは現在知られている。より一般的には、ラッセル・インパグリアッツォとモティ・ヤング、そしてベン・オールらは、一方向性関数や解読不可能な暗号化も仮定すると、IP  =  PSPACEのすべての問題にゼロ知識証明があること、言い換えれば、対話型証明システムで証明できるものはすべてゼロ知識で証明できることを示した。^{[31] [32]}

不必要な仮定を立てることを好まない多くの理論家は、一方向関数の必要性を排除する方法を模索した。これを実現した方法の1つは、マルチ証明者対話型証明システム（対話型証明システムを参照）を使用することであった。これは、1つの証明者だけではなく複数の独立した証明者を持ち、検証者が誤解を避けるために証明者を個別に「反対尋問」することを可能にする。扱いにくい仮定がなければ、 NPのすべての言語はそのようなシステムでゼロ知識証明を持つことが示される。 ^[33]

複数のプロトコルが同時に実行される可能性のあるインターネットのような環境では、ゼロ知識証明を構築することはより困難であることが判明しています。同時ゼロ知識証明を調査する研究の流れは、Dwork、Naor、Sahaiの研究によって開始されました。^{[34]この方向に沿った特定の開発の1つは、}証人区別不可能証明プロトコルの開発です。証人区別不可能性の特性はゼロ知識の特性と関連していますが、証人区別不可能なプロトコルは同時実行と同じ問題に悩まされることはありません。^[35]

ゼロ知識証明のもう一つの変種は非対話型ゼロ知識証明である。ブルーム、フェルドマン、ミカリは、証明者と検証者の間で共有される共通のランダム文字列が、対話を必要とせずに計算ゼロ知識を達成するのに十分であることを示した。^{[5] [6]}

最も人気のある対話型または非対話型のゼロ知識証明（例：zk-SNARK）プロトコルは、簡潔な非対話型知識議論（SNARK）、スケーラブルな透過的知識議論（STARK）、検証可能な多項式委任（VPD）、簡潔な非対話型知識議論（SNARG）の4つのカテゴリに大まかに分類できます。ゼロ知識証明プロトコルとライブラリのリストは、透明性、普遍性、妥当なポスト量子セキュリティ、およびプログラミングパラダイムに基づく比較とともに以下に記載されています。^[36]透過的なプロトコルは、信頼できるセットアップを必要とせず、公開されたランダム性を使用するプロトコルです。普遍的なプロトコルは、各回路に個別の信頼できるセットアップを必要としないプロトコルです。最後に、妥当なポスト量子プロトコルは、量子アルゴリズムを含む既知の攻撃の影響を受けないプロトコルです。

• コンピュータ科学者のアミット・サハイがYouTubeでゼロ知識証明を 5 段階の難易度で解説