論文「Weak Zero-Knowledge and One-Way Functions」の技術的サマリー

1. 概要と背景

この論文は、**「弱いゼロ知識プロトコル（Weak Zero-Knowledge Protocols）」の存在が、暗号学的な基本構成要素である「一方向性関数（One-Way Functions: OWF）」**の存在をどのように導くかについて研究しています。

従来のゼロ知識証明（ZK）の研究では、完全性（Completeness）、健全性（Soundness）、ゼロ知識性（Zero-Knowledge）の誤り率がすべて「無視できる（negligible）」程度であることが前提とされてきました。しかし、3-Coloring や Graph Non-isomorphism などの自然なプロトコルは、定数レベルの誤り率を持つ「弱い」ZK プロトコルとして知られています。

これまでの研究（Chakraborty et al., CRYPTO 2025 など）では、弱い NIZK（非対話型ゼロ知識）から OWF を導出するための条件として、誤り率の和が $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ であることが必要とされていました。本論文は、この条件をさらに緩和し、より一般的なパラメータ設定において OWF の存在を証明することを目的としています。

2. 問題設定

• 前提: NP 内の言語が最悪ケースで困難である（$NP \not\subseteq ioP/poly$ または $NP \not\subseteq P/poly$）。
• 対象: 完全性誤り $\epsilon_c$、健全性誤り $\epsilon_s$、ゼロ知識誤り $\epsilon_z$ が無視できない（定数レベルなど）可能性のある「弱い」ZK プロトコル。
• 目標: これらの弱いプロトコルの存在から、一方向性関数（OWF）の存在を導出する。特に、誤り率の条件 $\epsilon_c + \epsilon_s + \epsilon_z < 1$ を満たすあらゆる非自明なケースをカバーすること。

3. 主要な貢献と結果

著者らは、以下の 3 つの主要な定理を証明しました。これらは、誤り率の条件を大幅に緩和し、既存の結果を一般化しています。

定理 1: 非対話型ゼロ知識（NIZK）からの OWF

• 条件: NP 内のすべての言語が、$\epsilon_c + \epsilon_s + \epsilon_z < 1$ を満たす NIZK 証明（または議論）を持つ場合。
• 結果: OWF が存在する。
• 意義: 従来の $\epsilon_c + \sqrt{\epsilon_s} + \epsilon_z < 1$ という条件を、$\epsilon_c + \epsilon_s + \epsilon_z < 1$ という最も一般的な条件に改善しました。これにより、$\epsilon_c$ が無視でき、かつ $\epsilon_s + \epsilon_z < 1$ であるような NIZK 証明があれば、誤り率をすべて無視できるレベルに増幅できることが示唆されます。

定理 2: 多対話型公開コイン ZK からの OWF

• 条件: NP 内のすべての言語が、$t$ メッセージ（$t$ 回の通信）の公開コイン ZK プロトコルを持ち、$\epsilon_c + \epsilon_s + (t-1)\epsilon_z < 1$ を満たす場合。
• 結果: OWF が存在する。
• 意義: 従来の手法（Ostrovsky-Wigderson 流）では $\epsilon_c + \epsilon_s + t\epsilon_z < 1$ が必要でしたが、これを $(t-1)\epsilon_z$ に改善しました。

定理 3: 定数ラウンド公開コイン ZK からの無限回 OWF

• 条件: 定数 $k$ に対して、NP 内のすべての言語が $k$ ラウンドの公開コイン ZK プロトコルを持ち、$\epsilon_c + \epsilon_s + k\epsilon_z < 1$ を満たす場合。
• 結果: **無限回（infinitely-often）**一方向性関数（ioOWF）が存在する。
• 意義: 定数ラウンドのプロトコルに対して、より厳しい誤り条件（$k\epsilon_z$）を許容しつつ、OWF の存在を導出しました。ただし、この結果は「無限回」の安全性（任意の多項式時間アルゴリズムに対して、無限に多くの入力長で逆計算が困難）にとどまります。

4. 技術的アプローチと手法

4.1 既存手法の限界と改善

従来の Ostrovsky-Wigderson (OW93) 手法では、シミュレータの逆関数（インバータ）を用いて言語の所属を判定する識別子（Distinguisher）を構成します。この際、ゼロ知識誤り $\epsilon_z$ を 2 回分（シミュレータからの分布と実際のプロトコルからの分布の比較など）考慮する必要があり、条件が $\epsilon_s + 2\epsilon_z < 1$ 程度に制限されていました。

4.2 検証プロセスの統合（Key Idea）

著者らの主要な技術的革新は、候補となる一方向性関数の中に検証プロセス（Verification）を明示的に組み込むことです。

• 新しい一方向性関数の定義:
  従来の $f_x(\rho) = (r, \pi)$ （シミュレータの出力）に対し、
  $$f_x(\rho) = (r, a)$$
  と定義します。ここで、$(r, \pi) \leftarrow Sim(x; \rho)$ として計算し、$a \leftarrow V(x; r, \pi)$ （検証結果）を出力に含めます。
• 効果: インバータ $A$ が $(r, 1)$ の原像を見つけた場合、それは自動的に検証に合格する証明 $\pi$ の存在を意味します。これにより、識別子の構成時に追加のゼロ知識誤りペナルティを課さずに済むようになり、条件を $\epsilon_s + \epsilon_z < 1$ まで緩和できました。

4.3 再帰的アプローチと定数ラウンドの改善

定数ラウンドのプロトコルに対しては、より高度な再帰的構成を用います。

• 各ラウンド $i$ において、その後のラウンドでの成功確率（Acceptance Probability）を推定する関数 $f_{i,x}$ を定義します。
• インバータ $A_i$ は、この推定値が最大になるような証明メッセージを生成する戦略を学習します。
• この再帰的な構造により、ゼロ知識誤りの累積を $k\epsilon_z$ に抑えつつ、定数ラウンドでのより良いパラメータ条件を実現しています。ただし、複数のインバータが同時に成功する必要があるため、結果が「無限回」の OWF にとどまるというトレードオフがあります。

4.4 確率的検証への対応

検証アルゴリズム $V$ が確率的である場合（ランダムな検証）についても、期待値を出力に含めることで同様の条件を導出可能であることを示しています。

5. 結論と意義

結論

本論文は、ゼロ知識プロトコルの「弱さ」（誤り率が無視できないこと）が、暗号学的な硬さ（OWF の存在）を導くための障壁ではないことを示しました。特に、$\epsilon_c + \epsilon_s + \epsilon_z < 1$ という直感的な条件の下で、NP 最悪ケースの困難性から OWF が導出されることを証明しました。

学術的意義

1. パラメータの一般化: 既存の研究が扱っていた制限的な誤り条件を、理論的に可能な限り広い範囲（非自明なすべての値）に拡張しました。
2. 技術的革新: 検証プロセスを関数定義に統合する手法により、ゼロ知識誤りのペナルティを最小化し、より効率的な帰着を可能にしました。
3. 相互作用プロトコルの理解: 対話型プロトコル（特に公開コイン）のラウンド数と誤り率の関係について、定数ラウンドの場合のより良い境界値を提示しました。

今後の課題（Open Problems）

• 秘密コイン（Private-coin）プロトコル: 現在の結果は公開コインプロトコルに限定されています。秘密コインの弱い ZK についても同様の結果が得られるかが課題です。
• 標準 OWF への強化: 定数ラウンドの結果は「無限回」の OWF にとどまっています。これを標準的な OWF（すべての入力長で困難）に強化できるかが今後の課題です。
• 他の暗号プリミティブ: 弱い ZK が、OWF 以外のより強力な暗号プリミティブ（例：暗号化、デジタル署名など）を導くかどうかの検討が必要です。

総じて、この論文はゼロ知識証明の理論的基盤を強化し、弱いプロトコルであっても暗号学的な有用性を有することを示す重要な進展です。