CRT-Decomposed $Σ$-Protocols for CSIDH

技術要約：CSIDH クラス群作用のための CRT 分解された $\Sigma$-プロトコル

問題提起
本論文は、CSIDH（Commutative Supersingular Isogeny Diffie-Hellman）群作用に基づいたアイソジェニーベースのブラインド署名および識別プロトコルのセキュリティ証明における決定的な弱点を扱っている。現在の最先端のスキーム（例：CSI-Otter, Tanuki）は、インタラクティブな識別プロトコルに依存しており、そのセキュリティ簡約は**フォッキング補題（forking lemma）**に依存している。この補題は、秘密鍵を抽出するために量子アドバーサリを「巻き戻す（rewinding）」ことを必要とするが、これは二次的なセキュリティ損失を招き、内部状態を複製できない量子アドバーサリに対しては理論的に無効である。その結果、これらの証明は、この損失を補うために、より大きく低速なパラメータの使用を強いている。本論文は、CSIDH 類群の代数的構造を活用することで、この巻き戻しステップを排除し、**ストレートライン抽出（straight-line extraction）**を可能にすることを目指している。

手法
著者らは、CSIDH のイデアル類群の**中国剰余定理（CRT）**構造を利用したゼロ知識知識証明（$\Sigma$-プロトコル）を構築する。このアプローチは、群構造が正確に既知である場合にのみ適用可能であり、現在、その条件を満たしているのは CSIDH-512 のみである。

1. CRT 分解: 次数 $N$ の類群 $C\ell(\mathcal{O})$ を、$N$ の素数冪因子に対応する独立した巡回成分に分解する。秘密鍵 $s$ は、各素数因子 $q_i$ を法とする成分 $s_i$ に分割される。
2. ホップ曲線（Hop Curves）: プロトコルは、群作用の中間状態を表す一連の「ホップ曲線」（$F_0, \dots, F_k$）を公開する。各ホップ $i$ は、特定の部分群 $\langle h_i \rangle$（位数 $q_i$）内でのベクトル化問題に対応する。
3. プロトコル構造: プロトコルは $k$ 個のホップで構成され、各ホップは $t$ 個の並列ラウンドで実行される。各ラウンドにおいて、証明者はランダムな変位をコミットし、検証者はバイナリチャレンジ（$c \in \{0,1\}$）を発行し、証明者は値 $z$ で応答する。
4. 代数的抽出: 異なるチャレンジを持つ2つの受理されたトランスクリプトを見つけるために巻き戻しを必要とする標準的な証明とは異なり、本プロトコルでは、秘密は閉形式の代数公式を介して回収可能である。同じコミットメントに対する2つの受理されたトランスクリプトが与えられた場合、秘密の成分は単にレスポンスの差（$z_0 - z_1$）であり、その後にモジュロ逆数と CRT 再結合を行う。
5. QROM コンパイル: 各ラウンドには正確に2つのレスポンスが存在するため、プロトコルは Unruh の変換と互換性がある。これにより、インタラクティブなプロトコルを、フォッキング補題による損失を完全に回避した、**量子ランダムオラクルモデル（QROM）**におけるストレートライン抽出可能な非対話的知識証明へと変換できる。

主な貢献
本論文の主な貢献は以下の5点である：

1. 形式的定義: 暗号学的群作用に対する**弱い抽出可能性（weak extractability）**を形式化し、エキストラクターが受理されたトランスクリプトから（格子簡約やヒューリスティックを用いず）環演算のみを用いて秘密を回収できるセキュリティ概念を定義した。
2. プロトコル構成 ($\Pi_{CRT}$): 以下の4つの特性を証明するプロトコルを構築した：
   • 完全な完全性（Perfect Completeness）: 正直な証明者は常に成功する。
   • 完全な特殊 HVZK（Perfect Special HVZK）: トランスクリプトは、無制限の観測者に対しても秘密に関する情報を漏洩しない。
   • 2-特殊健全性（2-Special Soundness）: 秘密は、単純な減算とモジュロ逆数による2つのトランスクリプトから代数的に回収可能である。
   • 知識誤差（Knowledge Error）: 証明者が鍵なしで成功する確率は $2^{-t}$ である。
3. マシン検証: 著者らは、CSIDH-512 の正確な 258 ビットのモジュラス上でこの代数レイヤーを実装した。10,000 個のランダムなインスタンスを用いて検証を行い、代数的抽出が完全に機能し、実際のアイソジェニーを計算することなくプロトコルのロジックが保持されることを確認した。
4. 限定的な結果（負の結果）:
   • チャレンジ空間の制限: CRT 分解は、1ラウンドあたりのチャレンジ空間を拡大しない。複数の曲線を公開しない限り、バイナリチャレンジが必要である。
   • セキュリティコスト: ホップ曲線を公開することにより、鍵回収の古典的セキュリティは $\approx 2^{128.6}$ から $\approx 2^{67.3}$ の群作用評価へと低下する。これは、問題が最大成分における中間一致攻撃（meet-in-the-middle attacks）によって解ける、独立した部分群内のベクトル化インスタンスへと分解されるためである。
5. QROM セキュリティ: 本プロトコルを Unruh の変換によってコンパイルすると、QROM においてオンライン抽出を伴う非対話的知識証明が得られることを証明し、乗法的なフォッキング補題の損失を取り除いた。

結果および定量的分析

• インスタンス化: スキームは CSIDH-512 上に実装されている。類群は5つの素数因子（ビット長：2, 6, 21, 96, 135）を持つ。
• セキュリティ境界:
  • 古典的: セキュリティは最大の素数因子（$q_{max} \approx 2^{135}$）によって制限される。中間一致攻撃のコストは $O(\sqrt{q_{max}}) \approx 2^{67.3}$ である。論文は、ホップ曲線の公開により、CSIDH-512 はこの構成下では 128 ビットの古典的セキュリティを達成しないことを指摘している。
  • 量子: セキュリティは、他の CSIDH スキームと同様に、Kuperberg 型の篩（sieve）によって制限される。
• パフォーマンス:
  • 署名サイズ: $t=128$ ラウンド、$k=5$ コンポーネントの場合、署名サイズは約 24.1 KiB である（CSI-FiSh の 263 B や CSI-Otter の 8 KiB と比較）。
  • 計算量: 代数的抽出およびシミュレーションはマイクロ秒未満である。支配的なコストは依然としてアイソジェニー評価であり（1 アクションあたり 40 ms と推定）、全プロトコルの署名時間は約 25.6 秒となる。
• シミュレーション: モンテカルロ・シミュレーションにより、サウンドネス誤差が理論的な $2^{-t}$ の境界内に 95% の信頼区間で一致することが確認された。

意義および主張
本論文は、既知の構造を持つ類群（CSIDH-512 など）に対して、本構成が構造的に完全かつ正しいと主張している。その主な意義は、巻き戻しステップを排除することで、アイソジェニーベースの知識証明に対する量子安全なセキュリティ簡約を提供することにある。これは、ポスト量子セキュリティ証明における既知の脆弱性である。

しかし、著者らはトレードオフについても明示している：

• セキュリティへの謙虚さ: ホップ曲線の公開によるセキュリティ低下のため、本スキームは CSIDH-512 に対して定量的な 128 ビットのセキュリティを備えていない。著者らは、本構成は「（各因子が $\ge 256$ ビットであるような）大きな素数因子を持つ将来のパラメータセットにおいてのみ、定量的に安全である」と述べている。
• 万能薬ではない: CRT 分解は、サウンドネスに必要なラウンド数を減らすものではない。それは単に抽出メカニズムを変更するものである。
• 今後の課題: この知識証明に基づくブラインド署名の構築、およびエンドモルフィズム環問題への非偽造性のタイトな簡約を今後の課題としている。

要約すると、本論文は、CSIDH ベースの知識証明における「巻き戻し問題」を解決する、数学的に厳密でマシン検証済みのプロトコルを提示している。これは、署名サイズが大きくなり、現在のパラメータセットでは古典的セキュリティが低下するという代償を払いつつも、QROM 安全なブラインド署名への道を提供するものである。