ゼロ知識証明

三つの条件

ゼロ知識証明は次の三条件を満たすものとして定義される。ひとつめは完全性で、主張が本当に正しいなら、正直な証明者は検証者を納得させられる。ふたつめは健全性で、主張が偽であれば、どんなにずるい証明者でも検証者を納得させられる確率は無視できるほど小さい。みっつめがゼロ知識性で、検証者が対話を通じて得る情報は、主張が正しいという一事を超えない。

ゼロ知識性の定式化は、素朴に「何も学ばない」と書くわけにはいかない。使われるのは、検証者が対話で見る記録を、証明者と対話せずに検証者が自力で作れることを示す、という形である。対話の記録が自作できるなら、その記録には証明者しか知らない情報は入っていない。この「シミュレータ」による議論が、ゼロ知識という曖昧な直観を数学的に扱える条件に落とし込んでいる。

健全性が確率的にしか成り立たない点は、この方式の性質として重要である。一回の対話でごまかしが通る確率が2分の1なら、独立に20回繰り返せば100万分の1程度まで下がる。証明は「絶対に正しい」ではなく「ごまかせる確率をいくらでも小さくできる」という形で担保される。

アリババの洞窟

直観的な説明としてよく引かれるのが、1989年の CRYPTO で発表された「How to Explain Zero-Knowledge Protocols to Your Children」の洞窟の喩えである^※1。環状の洞窟があり、入口から入ると道が二股に分かれ、奥の突き当たりは魔法の言葉で開く扉でつながっている。証明者は、この言葉を知っていることを、言葉を明かさずに示したい。

手順はこうなる。検証者は入口で待ち、証明者は好きな方の道を選んで奥へ進む。証明者が見えなくなってから、検証者は「右から出てこい」「左から出てこい」のどちらかを叫ぶ。言葉を知っていれば、扉を通ってどちらからでも出られる。知らなければ、最初に選んだ道と指示が一致した場合しか出てこられない。一回なら2分の1で当たるが、何十回も続けて成功することは実質あり得ない。そして検証者が見たのは「指示した側から出てきた」という事実だけで、言葉そのものは最後まで伝わらない。

NP全体への拡張

当初の構成は、平方剰余性や離散対数のような数論的な主張に限られていた。これを一般化したのが、オデッド・ゴールドライヒ、ミカリ、アヴィ・ウィグダーソンによる1986年の発表（論文誌版は1991年の Journal of the ACM 38巻^※2）で、安全な暗号化関数が存在するという仮定の下で、NP に属するすべての言語がゼロ知識証明を持つことを示した。

NP とは、答えが与えられればそれが正しいことを効率よく検証できる問題のクラスである。この結果は、そうした問題であればどれでも「答えを明かさずに答えを持っていることだけを証明する」方式に変換できる、ということを意味する。個別の数学的構造に頼った道具から、広い範囲に適用できる一般技法へと性格が変わった転換点にあたる。ゴールドワッサーとミカリはこの系統の業績で2012年のチューリング⁴賞を受賞し、1985年の論文は第1回ゲーデル賞の対象にもなっている^※3。

非対話化と実用

元の定義は証明者と検証者が何度もやりとりする対話を前提にしており、そのままでは記録として残せない。Fiat-Shamir変換は、検証者が投げる乱数の役割をハッシュ関数の出力で置き換えることで、対話を一通のメッセージ²に畳み込む。ハッシュをランダムな関数として理想化する前提（ランダムオラクルモデル）の上で成り立つ手法である。なお非対話にすると、対話版が持っていた性質のすべては保たれない。たとえば、後から「そんな証明はしていない」と主張できる否認可能性は失われる。

実装面で広く使われるようになったのは、証明の長さと検証時間が元の計算の規模に比べて極端に小さい方式である。zk-SNARK と呼ばれる系統がこれにあたり、暗号通貨 Zcash は Groth16 と呼ばれるプロトコルを用いて、公開台帳の上で支払いの内容を隠す。この系統の弱点は、使用前に秘密のパラメータを生成する「信頼できるセットアップ」が必要な点で、生成時の秘密が漏れていれば偽の証明が作れてしまう。これを不要にしたのが zk-STARK と呼ばれる方式で、透明性（セットアップ不要）と引き換えに証明サイズが大きくなる傾向がある。