完全ゼロ知識 vs 計算論的ゼロ知識：この区別が実際に意味すること

クリプト業界で「ゼロ知識証明」と言えば、ほぼ決まって一つのものを指します。入力を明かすことなく、ある計算が正しく実行されたことを証明する SNARK または STARK です。このメンタルモデルはほとんどのエンジニアリング議論には十分です。しかしそれは、セキュリティが実際に何を保証するかを厳密に考えようとした瞬間に重要になる区別を隠しています。

ゼロ知識証明には、形式的に三つの種類があります。完全ゼロ知識、統計的ゼロ知識、計算論的ゼロ知識の三つであり、これらは無制限のリソースを持つ検証者が何を知り得るかという点で異なります。あなたが実際に出荷するシステムは、ほぼ間違いなく計算論的です。その理由と、それが何をもたらすかを理解する価値があります。

ゼロ知識証明の構造

古典的な設定は次のとおりです。証明者は、検証者にある命題が真であることを確信させたい。しかも検証者はそれ以上のことを知るべきではない。「真」とは、「H(x) = y を満たす x を知っている」「このグラフ内の経路を知っている」「このプログラムを秘密の入力に対して正しく実行した」といった意味です。

証明システムがゼロ知識であるとは、非形式的に言えば、検証者は秘密を使わずに自分でその証明を生成できるはずであるということです。形式的には、シミュレータの存在によって定義されます。シミュレータとは、公開された命題のみ（証人なし）を入力として、実際の証明トランスクリプトと見分けがつかない出力を生成する多項式時間アルゴリズムです。

ゼロ知識の三種類の違いは、「見分けがつかない」の意味にあります。

完全ゼロ知識

シミュレータの出力は、実際の証明と同一の分布を持ちます。統計的検定も、量子コンピュータによる検定も、10^100 年かけて行う検定も、シミュレータと実際の証明者を区別できません。数学的に、二つの分布は同じです。

これは最高水準です。無制限の計算能力を持つ敵対者でも、時間制限なしでも、計算論的な仮定なしでも、証明から何も学べないことを意味します。

統計的ゼロ知識

シミュレータの出力は、実際の証明と統計的に近い分布を持ちます。二つの分布の全変動距離は無視できる程度です。無制限の計算能力を持つ敵対者は原理的に何かを学べるかもしれませんが、学び得る量はセキュリティパラメータに対して指数的に減衰します。

実用上、統計的 ZK は完全 ZK と同等です。シミュレータが実際の分布に完全に一致する必要はなく、どれだけ計算しても差を拡大できないほど十分に近ければよいのです。

計算論的ゼロ知識

シミュレータの出力は、実際の証明と計算論的に区別不可能です。つまり、多項式時間アルゴリズムではそれらを区別できません。ただし、無制限の計算能力を持つ敵対者——基礎となるハッシュ関数を総当たりで破ったり、基礎となる困難な問題を解いたりできる者——は、両者を区別でき、証人を知ることができるかもしれません。

これは形式的には三つのうち最も弱いものですが、現代のほぼすべてのシステムが実際に提供しているのはこれです。

ほぼすべての本番 ZK システムが計算論的である理由

この背景には定理があります。NP 完全言語に対して、完全ゼロ知識は多項式階層が崩壊しない限りほぼ存在し得ないというものです（Goldreich and Krawczyk, 1996）。言い換えると、「このプログラムを正しく実行した」のような任意の命題をゼロ知識で証明したい場合、証明自体が未証明の計算量的仮定に依存することなしに完全ゼロ知識を達成することはできません。

任意の NP 命題に対して得られるもの：

• 計算論的ゼロ知識証明：一方向関数が存在するならば存在します（Goldreich, Micali, Wigderson 1991）。
• 限定的な命題クラスに対する統計的ゼロ知識：自己還元可能なランダム問題、グラフ同型問題などは対象ですが、一般的な NP には対応しません。

したがって、実際のシステム——Groth16、PLONK、Halo2、STARK、Bulletproofs——が「ゼロ知識」と言う場合、それはほぼ常に計算論的ゼロ知識を意味します。楕円曲線、ハッシュ関数、その他の暗号プリミティブに関する仮定を条件として、証明は多項式時間の検証者に何も明かしません。

それらの仮定が破られた場合——たとえば、あるスキームが依存している曲線上の離散対数問題を破るアルゴリズムが将来発見された場合——ゼロ知識の論証は遡及的に弱体化する可能性があります。何が可能になるかは構成に依存します。攻撃者は実際のトランスクリプトとシミュレートされたものを区別できるようになるかもしれず、証明を偽造したり、以前は保護されていた情報を抽出したりできるかもしれません。基礎となる仮定が失敗した後も、古い計算論的 ZK トランスクリプトが同じプライバシーマージンを保持すると仮定すべきではありません。

具体例：コミットメントスキーム

コミットメントスキームは、この区別を具体的に示します。

コミットメントとは、おおよそ「封筒 c に値 v を封じて渡し、後で v を公開する。あなたは私が元の値を公開したことを確認できるが、公開前に v を覗くことはできない」というものです。

二つのセキュリティ特性があります。

• 隠蔽性（Hiding）：封筒は v について何も明かさない。
• 束縛性（Binding）：私は最初にコミットした値とは別の値で封筒を開けない。

両方を完全に満たすことはできません。完全な隠蔽性を持つコミットメントは計算論的な束縛性しか持ちません（十分な計算量があれば、攻撃者は別の開封方法を見つけられる）。完全な束縛性を持つコミットメントは計算論的な隠蔽性しか持ちません（十分な計算量があれば、攻撃者はコミットされた値を抽出できる）。

Pedersen コミットメントは完全隠蔽かつ計算論的束縛です——無制限の攻撃者に対してもコミットされた値について何も明かしませんが、離散対数が将来破られると束縛性を欺けるようになります。ハッシュベースのコミットメント（c = H(v || r)）は計算論的隠蔽であり、（ハッシュが衝突耐性を持つ場合）計算論的束縛です。

どちらの種類を選ぶかは、どちらの特性が時間とともに弱体化することを許容できるかによります。投票や入札の長期的なプライバシーのためには、たとえ束縛性が計算論的であっても、通常は完全な隠蔽性を望むべきです——なぜなら、離散対数の仮定が破られる前に束縛性を再証明できますが、漏洩した投票を遡及的に非公開に戻すことはできないからです。

ZK ロールアップと L2 システムへの影響

ほとんどの ZK ロールアップは計算論的ゼロ知識を持つ SNARK を使用します。実際的な意味は次のとおりです。

• 現時点では、証明はどんな現実的な攻撃者にも何も明かしません。プライバシー保証は強固です。
• 長期的には、証明が明かすものは基礎となる仮定が保護する範囲に依存します。ロールアップが BN254 の離散対数を前提とした SNARK を使っており、2050 年に BN254 が破られた場合、それ以前に公開されたすべての証明が潜在的にアンブラインド可能になります。
• ポスト量子の考慮事項は重要です。離散対数ベースの SNARK（Groth16、標準ペアリング曲線上の PLONK）はポスト量子セキュリティを持ちません。ハッシュの衝突耐性のみに依存する STARK はポスト量子セキュアです（StarkWare——STARK の頭字語を確立した論文）。
• 統計的または完全 ZK は制限された設定（たとえば特定の代数的関係の証明）では可能であり、長期的なプライバシー予算が表現力よりも重要な場合に使用されることがあります。

匿名投票、内部告発チャネル、その他のシステム——トランスクリプトが数十年にわたってアーカイブされる可能性があるもの——においては、計算論的 ZK と統計的 ZK の選択は形而上学的な議論ではありません。それは、明日の敵対者に対して保持されるプライバシーと、あらゆる敵対者に対して保持されるプライバシーの違いです。

シンプルな意思決定ツリー

本番用の ZK システムを選ぶ場合：

• 検証者のプライバシーのみ、短命なデータ、パフォーマンスが最優先： 実績ある SNARK または STARK による計算論的 ZK で十分です。これはほとんどのロールアップ、ほとんどの ZK-KYC、ほとんどの ZK ログインに当てはまります。
• 長期的なプライバシー、監査・法的感応性： ハッシュベースのシステム（STARK）または基底に Pedersen スタイルのコミットメントを持つものを優先してください。仮定を文書化してください。
• 計算量的仮定に依らない証明可能なプライバシー： 制限された命題クラス上の完全または統計的 ZK を探すことになります。ある程度の表現力またはインタラクティビティを犠牲にすることを覚悟してください。

フリーランチはありません。ZK の種類はそれぞれ相互にトレードオフし、また効率性ともトレードオフします。問題は、どのトレードオフを意識的に行うかです。

Namefi のアプローチ

ドメイン所有権フローにおける ZK の最も興味深い用途は、どのドメイン名かを明かすことなく名前を所有していることを証明することです。オンチェーンのレジストリに対する所有権証明は、非常に成熟したツール（Groth16、PLONK）を使って計算論的 ZK で実現できます。それが今日の本番システムが採用しているものです。より機密性の高いフロー——たとえば、どのドメインかを明かすことなく信頼されたエンティティの集合にドメインが属することを証明する——においては、制限された命題に対する統計的または完全 ZK スキームが関連性を持つようになるかもしれません。本記事の目的は、このトレードオフを明確にすることです。本当に必要なものを選び、受け入れている仮定を書き留めてください。

ソースと参考文献

• Goldreich, Micali, Wigderson — Proofs that yield nothing but their validity (J. ACM 1991)
• Goldreich and Krawczyk — On the composition of zero-knowledge proof systems (1996)
• Pedersen — Non-interactive and information-theoretic secure verifiable secret sharing (1991)
• Ben-Sasson, Bentov, Horesh, Riabzev — Scalable, transparent, and post-quantum secure computational integrity (STARK paper, 2018)
• a16z crypto — Justin Thaler's "Proofs, Arguments, and Zero-Knowledge"（現代の標準的な教科書）