技術要約: MCSI – マスクされた可換超特異イソジェニー鍵交換

1. 問題提起

本論文は、可換超特異イソジェニー・ディフィー・ヘルマン（CSIDH）の群作用に基づく、ポスト量子認証鍵交換（AKE）プロトコルの設計について論じている。CSIDHは、ポスト量子ファミリーの中で最小の公開鍵サイズを提供しているが、この群作用上での標準的な非認証交換には、主に以下の2つの問題が存在する：

1. サービス拒否（DoS）への脆弱性: 標準的な交換では、応答者はイニシエーターから提供された曲線に対して高コストな群作用の評価（数十ミリ秒を要する）を実行しなければならないが、メッセージの真正性を検証する前に行う必要がある。認証されていない攻撃者は、この高コストな計算を応答者に繰り返し強制させることが可能である。
2. エフェメラル（一時的）機密性の欠如: 標準的なCSIDH交換では、エフェメラルな公開要素（曲線）が平文で送信されるため、受動的な傍受者が鍵交換の中間状態を観察できてしまう。

さらに、本論文は一般的な誤解を明確にしている。SIDH派生のイソジェニー暗号とは異なり、可換なCSIDH派生では、トーション点の像（torsion point images）は公開されない。したがって、ここでの「マスキング」は、トーション点攻撃（SIDHを破ったもの）に対する防御策ではなく、エフェメラルな公開要素を隠蔽し、DoSを防ぐためのメカニカリズムである。

2. 手法およびプロトコル設計

著者らは、CSIDHの群作用と認証付き暗号を統合した、2メッセージ鍵交換プロトコルである MCSI（Masked Commutative Supersingular Isogeny）を提案している。

コアメカニズム

• 静的鍵: 両者は、CSIDHの類体群作用から導出された長期的な静的鍵ペア $(a, pk_A)$ および $(b, pk_B)$ を保持する。
• 静的・静的共有値 ($Z_{ss}$): セッション開始前に、当事者はそれぞれの静的秘密と相手の静的公開鍵を用いて、共有値 $Z_{ss} = (ab) \star x_0$ を計算する。類体の可換性により、両者は同一の $Z_{ss}$ を導出できる。
• ブリンディング層: 静的・静的共有値 $Z_{ss}$ は、認証付き付随データ付き暗号（AEAD） 用の対称鍵を導出するために使用される。
• プロトコルフロー:
  1. イニシエーター: エフェメラルな秘密 $u$ を生成し、エフェメラルな公開要素 $T_A = u \star x_0$ を計算し、$Z_{ss}$ によって鍵付けられたAEADスキームを用いて $T_A$ を暗号化して送信する。
  2. レスポンダー: キャッシュされた $Z_{ss}$ 由来の鍵を用いてメッセージを復号する。認証タグが失敗した場合、レスポンダーは直ちに（高コストな群作用の評価を行う前に）ハッシュ/タグのチェックのみを行って中断する。有効な場合、レスポンダーは $T_A$ を復元し、自身のエフェメラルな秘密 $w$ を生成して $T_B = w \star x_0$ を計算し、$T_B$ を暗号化して送り返す。
  3. 鍵導出: 両者は、トランスクリプトのハッシュと、以下の3つの共有値を用いてセッション鍵を計算する：
     • $Z_{ee} = (uw) \star x_0$ （エフェメラル・エフェメラル：前方秘匿性を提供）
     • $Z_{es} = (ub) \star x_0$ （エフェメラル・静的：認証を提供）
     • $Z_{se} = (aw) \star x_0$ （静的・エフェメラル：認証を提供）
     • $Z_{ss}$ （静的・静的：マスキングに使用）

設計の根拠

本論文では、ブリンディング鍵をセッション秘密自体から導出することは、循環依存を生むため、明示的に拒否している。代わりに、事前に共有された静的・静的共有値に依存している。また、著者らは、パブリックなバイト置換層（Sボックス）を暗号文に追加しても追加のセキュリティは提供されないことを証明しており、そのような修正なしに標準的なAEADを使用することを正当化している。

3. 主な貢献

本論文は、以下の具体的な貢献を行っている：

1. プロトコル仕様: CSIDHでインスタンス化された、抽象的な有効群作用上のMCSIの完全な仕様。これには、ブリンディング鍵はセッション秘密ではなく静的秘密から導出されなければならないという設計論拠が含まれる。
2. 正当性の証明: 類体の可換性、群作用の公理、およびモンゴメリ曲線の代表の一意性に厳密に依拠した、ゼロエラーの正当性を証明する定理。
3. セキュリティ証明: 強並列化仮定（GA-StCDH） に帰着する、ランダムオラクルモデル（ROM）における3つのセキュリティ定理：
   • セッション鍵の識別不能性: セッション鍵は、受動的な攻撃者に対してランダムと区別がつかない。
   • ブリンディングの機密性: エフェメラル要素は、受動的な観測者から隠蔽される。
   • 輸送の完全性: 静的秘密を持たない攻撃者は、受信者が受理するメッセージを偽造できない。
   • 注記: 証明は、CSIDHにおいて種数理論（genus theory）により偽であることが知られている決定群作用仮定（GA-DDH）を明示的に回避している。
4. パラメータ分析: 素数選択に関する批判的な分析。著者らは、標準的な楕ロット曲線離散対数問題（例：NIST P-521, $p = 2^{521}-1$）のために選ばれた素数は、効率的に評価可能な類体群作用を生成するために必要な滑らかさ（小さな素因数）を欠いているため、CSIDHには使用不可能であることを示している。
5. リファレンス実装: 正解ベクトル（known answer vectors）を用いてクロス検証された、移植可能なCおよびPythonによるデュアル実装。
6. サイドチャネル監査: リファレンス実装のタイミング挙動の詳細な測定を行い、最適化されていない実装が実行時間を通じて秘密鍵の1-ノルムを漏洩させることを明らかにしている。

4. 結果と測定

パフォーマンスとオーバーヘッド

• コスト: プロトコルは、1回のセッションあたり各当事者が4回の群作用評価（およびピアごとの $Z_{ss}$ 用のキャッシュされた1回の評価）を必要とする。これは、認証なしのCSIDH交換よりも2倍高いが、対称層（AEAD）のコスト（4 $\mu$s）は群作用のコスト（130 ms）と比較して無視できる程度である。
• DoS対策: 主要なパフォーマンス上の利点はDoS耐性にある。認証されていないメッセージは、群作用の評価（130 ms）ではなく、タグチェック（2.4 $\mu$s）の後に拒否されるため、約50,000倍の高速化を実現している。
• サイズ: MCSIは、格子ベース（ML-KEM）や符号ベース（Classic McEliece）の代替案よりも大幅に小さい公開鍵を提供する。512ビットのセキュリティレベルにおいて、公開鍵は64バイト、総セッション通信量は192バイトである。

実装に関する知見

• タイミング漏洩: リファレンス実装は定数時間（constant-time）ではない。著者らは、秘密鍵の1-ノルムと実行時間の間に強い相関（ピアソン 0.90）を測定した。
• 漏洩の深刻度: 1-ノルムがわずかに異なる（可能な370のうちの5の差）2つの鍵は、約200回のタイミング測定によって区別可能である。
• 検証: 監査において、Validate 関数（曲線が超特異であることを確認する関数）は、秘密に依存する制御フローを含まないことが確認されたが、群作用の評価自体は構造上、情報を漏洩する。

5. 重要性と限界

本論文は、MCSIを、展開可能なソリューションではなく、動作するリファレンス実装を伴う一つの「仕様」として位置づけている。

重要性:

• 暗黙的な相互認証とエフェメラルな機密性を備えた、CSIDH上での認証付き鍵交換が可能であることを示している。
• 「マスキング」が、破綻した決定仮定（GA-DDH）に依存していないことを厳密に証明している。
• 可換なイソジェニー・スキームのための素数は、既存のECC標準から選ぶのではなく、滑らかさのために特別に構築されなければならないという、しばしば見落とされる重要な制約を浮き彫りにしている。

明示的な限界（本論文が証明していないこと）:

• ブリンディングの前方秘匿性: 後に攻撃者が静的秘密を入手した場合、攻撃者は $Z_{ss}$ を再計算し、記録されたトランスクリプトからブリンディングを剥ぎ取ってエフェメラル要素を明らかにすることができる。
• 強力なセキュリティモデル: 証明は、Canetti-Krawczyk (CK) モデルや拡張CKモデル（例：エフェメラル鍵の漏洩や鍵のコンプロマイズ・イミパーソネーションに対する耐性）をカバーしていない。
• 能動的攻撃者: 輸送の完全性は証明されているが、メッセージ配信を制御する能動的な攻撃者に対する完全なセッション鍵の安全性は確立されていない。
• 実装のセキュリティ: リファレンス実装は定数時間ではなく、タイミング攻撃に対して脆弱である。著者らは、デプロイメントの前提条件として定数時間実行の実装が必要であると述べている。
• 悪意のあるピア: 有効な静的鍵を持っているが、悪意のある挙動をとるピアから保護するためのFujisaki-Okamoto変換は含まれていない。

結論として、MCSIはポスト量子鍵交換のための理論的に健全で効率的かつ小規模な設計を提供しているが、著者らは、実世界の利用において安全であるとみなすためには、現在の実装に大幅な強化（特に定数時間実行）が必要であると強調している。