論文「拡張体上のレジェンドル擬似乱数関数の暗号解析」の技術的概要

本論文は、マルチパーティ計算（MPC）やゼロ知識証明（ZKP）プロトコルにおいて低乗算複雑性で注目されているレジェンドル擬似乱数関数（Legendre PRF）が、素体 $\mathbb{F}_p$ ではなく拡張体 $\mathbb{F}_{p^r}$ 上で実装された場合の安全性について、包括的な暗号解析を行ったものです。著者は、単一次数（$d=1$）の拡張体版 PRF が、受動的および能動的な脅威モデルの両方において構造的に脆弱であることを証明し、より高い次数の鍵変種（$d \ge 2$）の必要性を提唱しています。

以下に、問題定義、手法、主要な貢献、結果、および意義について詳細にまとめます。

1. 問題定義と背景

• 背景: レジェンドル PRF は、その計算効率の高さから MPC や ZKP 分野で広く研究されています。従来の研究は主に素体 $\mathbb{F}_p$ 上で行われてきましたが、特定のプロトコルでのスループット向上のため、拡張体 $\mathbb{F}_{p^r}$ 上への展開が検討されています。
• 課題: 拡張体上では、整数の加算が係数ごとの多項式加算（キャリーなし）として定義されます。これにより、従来の素体上での「連続した加算的カウンタークエリ」の性質が変化し、古典的なスライドウィンドウ衝突攻撃が機能しなくなるという「キャリー欠如の亀裂（no-carry fracture）」が生じます。
• 核心となる疑問: この「亀裂」が本当に安全性を担保するのか、あるいは新たな構造的脆弱性を生んでいるのか、その実態は不明でした。本論文はこの点に焦点を当て、単一次数（$d=1$）の拡張体版 PRF の安全性を厳密に評価します。

2. 手法と攻撃モデル

著者は、受動的（Passive）と能動的（Active）の 2 つの脅威モデルに対して、異なる攻撃手法を設計・実装しました。

2.1 受動的攻撃モデル（Passive Threat Model）

サーバーが連続する整数カウンターを多項式にエンコードして生成する鍵ストリームを、攻撃者が傍受するモデルです。

• 構造的特性の分析: 拡張体上の多項式エンコーディングでは、整数加算によるキャリーが発生しないため、入力差分 $\Delta_n$ は一定ではなく、$p$ 進評価に依存して $\{x^k + 1\}$ の値をとる「非同期な亀裂」を示すことを証明しました。
• 差分署名（Differential Signature）によるバケット化:
  • 一見ランダムに見えるこの差分の列は、実際には決定論的に周期的であることを発見しました。
  • 攻撃者は、鍵ストリームから得られるウィンドウを、その「差分の形状（構造的特徴）」に基づいてグループ化（バケット化）する「差分署名」手法を提案しました。
  • これにより、亀裂によって分断されたシーケンスを構造的に再結合し、秘密鍵を復元するパスを確立しました。

2.2 能動的攻撃モデル（Active Chosen-Query Model）

攻撃者がサーバーに対して任意の入力をクエリできるモデルです。

• 幾何級数クエリの利用: 攻撃者は、加法群の制限を回避するため、乗法群 $\mathbb{F}_{p^r}^*$ の原始元 $g(x)$ を用いた幾何級数 $g^i$ をクエリとして送信します。
• 乗法的ホモモルフィズムの誘発: レジェンドル記号は乗法的であるため、$L(g^i + K)$ は $L(K) \cdot L(g^{i+j} + 1)$ のように因数分解できます（ここで $j$ は $K^{-1}$ の離散対数）。
• テーブル衝突攻撃の一般化: この因数分解により、秘密鍵 $K$ が単なる「シフト量 $j$」と「符号 $L(K)$」に還元されます。これにより、既存のテーブル衝突攻撃を拡張体の乗法群に直接適用し、鍵を抽出可能にしました。

3. 主要な貢献と結果

3.1 受動的攻撃の結果

• 発見: 「キャリー欠如の亀裂」は古典的な衝突攻撃を防ぐように見えますが、差分の周期性を利用することで完全に回避可能であること。
• 攻撃の複雑度: 秘密鍵を受動的に復元する計算量は $O(U \cdot p^r / M)$ となります（$U$ はユニシティ距離、$M$ は観測ビット数）。
• 意味: 統計的な偏りではなく、代数構造の周期性を突くことで、実用的な計算量で鍵を復元できることを示しました。

3.2 能動的攻撃の結果

• 発見: 幾何級数クエリを用いることで、加法群の構造的制限を完全に迂回し、乗法的ホモモルフィズムを直接利用可能にすること。
• 攻撃の複雑度: 秘密鍵を能動的に復元する計算量は $O(p^r / M)$ となり、理論的な下限に達します。
• 意味: 単一次数（$d=1$）の拡張体版 PRF は、能動的攻撃に対して完全に破られていることを証明しました。

3.3 防御策の提案（高次数変種）

• 対策: 秘密鍵を単一多項式から、$d$ 個の独立した多項式係数（$K = (K_{d-1}, \dots, K_0)$）を持つ多項式 $x^d + K_{d-1}x^{d-1} + \dots + K_0$ に拡張すること。
• 効果: 次数 $d \ge 2$（特に $d \ge 3, 4$）の場合、幾何級数クエリによる因数分解が数学的に不可能になります。中間項（$K_1 x$ など）が存在することで、鍵とシーケンスが密に結合され、$O(p^r/M)$ の攻撃が無力化されます。
• 将来の課題: 次数 2 の変種に対しても、Tschirnhaus 変換や「平方完成」を用いた高度な還元技術（Meet-in-the-Middle 攻撃など）により、複雑度が $O(p^{\lfloor d/2 \rfloor r})$ まで低下する可能性が示唆されており、より高い次数（$d \ge 3$）が推奨されます。

4. 意義と結論

本論文の意義は以下の点に集約されます。

1. 構造的脆弱性の解明: 拡張体上での「キャリーなし」特性が、一見セキュリティを強化するかのように見えますが、実際には決定論的な周期性を生み出し、新たな攻撃ベクトル（差分署名バケット化）を可能にすることを初めて示しました。
2. 能動的攻撃の完全性: 乗法群の性質を利用した幾何級数クエリにより、拡張体上の Legendre PRF が乗法的ホモモルフィズムの弱点を露呈し、効率的に鍵復元可能であることを実証しました。
3. 実装ガイドラインの提示: 拡張体上で Legendre PRF を安全に使用するには、単一次数（$d=1$）は絶対に使用せず、高次数（$d \ge 2$、推奨は $d \ge 3$）の鍵変種を採用する必要があることを形式的に確立しました。

結論として、拡張体上の単一次数 Legendre PRF は、MPC や ZKP などの重要な暗号プロトコルにおいて、構造的・代数的な還元攻撃に対して安全ではないことが証明されました。今後の実装においては、代数構造をより複雑にする高次数多項式への移行が必須であるという重要な提言がなされています。