このポストでは「How to Prove False Statements: Practical Attacks on Fiat-Shamir」を和訳します。

GKRプロトコルへの攻撃概要

この論文では、Fiat-Shamir (FS) 変換を適用した GKR (Goldwasser-Kalai-Rothblum) プロトコルが、適応的 (adaptive) な音性を満たさないことを示しています。具体的には、GKRプロトコルを Fiat-Shamir 変換で非対話的証明 (NIZK) に変換した場合、誤ったステートメント (false statement) に対しても検証者が証明を受理してしまう ことが可能であることを証明しました。

攻撃の核心は、Fiat-Shamir のハッシュ関数の決定論的な性質を利用し、検証者のランダムネスを攻撃者が予測できるようにする ことです。

---

攻撃手法の詳細

1. GKRプロトコルの簡単な説明

GKRプロトコルは、有界深さ (bounded-depth) の算術回路 C に対して、その計算が正しく実行されたことを証明するための対話型証明 (IP) です。GKRの基本構造は以下の通り：

1. 証明者 (Prover) は入力 x と証明したい出力 y を持ち、GKRプロトコルに従い、階層構造を持つ回路 C(x,w) の正しさを主張する。
2. 検証者 (Verifier) は回路の出力をランダムな点 r で評価し、順次入力層まで主張を還元 (reduction) する。
3. 最終的に、検証者は入力層の主張が正しいことを確認できれば、計算全体が正しいと結論付ける。

通常、このプロトコルは対話型 (Interactive) だが、Fiat-Shamir変換 を適用することで非対話型 (Non-Interactive) にできる。

---

2. Fiat-Shamir 変換による攻撃の導入

Fiat-Shamir 変換では、検証者のランダムな選択 (ランダムコイン) を、ハッシュ関数の決定論的な出力で置き換える。

具体的には、Fiat-Shamir 変換された GKRプロトコル \text{FSh}(\Pi_{\text{comm}, d})) では、検証者が選ぶランダム値 r は、次のように固定される：

r = h(\langle C \rangle, x, y, \text{comm}(w))

ここで：

• \langle C \rangle は回路 C のハッシュ (ダイジェスト)
• \text{comm}(w) は Prover が送る証拠データのコミットメント
• h は Fiat-Shamir に使われるハッシュ関数

この決定論的なランダムネスを攻撃者が悪用することで、偽のステートメントに対しても正当な証明が生成できることが示される。

---

3. 基本攻撃 (Basic Attack)

著者らは、任意の Fiat-Shamir ハッシュ関数 hh と 多重線形多項式コミットメント (MLPCS) \text{comm} に対して、次のような 「偽の証明を受理させる攻撃」 を示しました。

攻撃の流れ

1. 改ざんされた回路 C^* の構築
   • 任意の回路 C に対して、「どんな入力に対しても偽の出力を証明できる回路」 C^* を作成する。
   • C^* は、Fiat-Shamir ハッシュ関数 h の呼び出しを内部に持ち、検証者が使用するランダム値 r を内部で予測できるように設計される。
2. 改ざんされた証明の生成
   • 証明者は「本来ありえない出力 y^* を持つ 」 C^* に対して証明を生成する。
   • 検証者が計算するランダム値 r を、攻撃者側で事前に生成できるため、通常なら無効となる証明を有効にできる。
3. 検証者の誤認
   • 検証者は Fiat-Shamir ハッシュを基に検証するため、攻撃者が事前に計算した値を「正しい証拠」として認識してしまう。
   • その結果、 C^*(w) \neq y^* であるにもかかわらず、「 C^*(w) = y^* を証明できた」ことになる。

攻撃の要点

• C^* は、Fiat-Shamir のハッシュ関数を内部で使用し、適切な証明データを計算することで、改ざん可能なランダム値を生成する。
• これにより、「証明するべきでないことを証明できる」ようになる。

---

4. 攻撃の拡張 (Extended Attack)

この攻撃は単なる改ざん回路 C^* に留まらず、既存のあらゆる回路 C に対して「見かけ上は同じだが、好きな証明を生成できる回路」 C^* を作成する ことができる。

拡張された攻撃の影響

• どんな計算でも、改ざんされた形で証明可能となる。
• したがって、回路の「機能的な振る舞い (functionality)」ではなく、「どのように設計されたか (implementation details)」によって、証明の正当性が決まってしまう。

---

攻撃の影響

• GKRプロトコルをベースとした zkSNARK や zkVM などのシステムに深刻な影響を与える可能性がある。
• 特に、Fiat-Shamir 変換を使用している zkVM システムでは、この攻撃によって「無効な計算結果を正しく証明したように見せる」ことが可能となる。

---

攻撃の対策

論文では、この攻撃を防ぐために以下のような対策を提案している：

1. ハッシュ関数の計算深度を増やす
   • Fiat-Shamir のハッシュ関数が GKR 証明の深さよりも大きくなるように設計することで、攻撃者が「回路内部でハッシュを計算し、それを予測する」ことを困難にする。
2. 回路の制約を強化する
   • 証明回路に Fiat-Shamir のハッシュ関数を埋め込めないように、計算リソース (深さ、次数など) に制約を加える。
3. 非決定論的な要素を導入する
   • Fiat-Shamir のランダム値に、予測不可能な追加エントロピー (例: 乱数) を含めることで、攻撃者がそれを事前計算できないようにする。

---

結論

この攻撃は、zkSNARKs や zkVM における Fiat-Shamir 変換の安全性に根本的な疑問を投げかける ものであり、GKRプロトコルのセキュリティに対する新たな脅威を示しています。