論文要約：ポスト量子暗号（PQC）ハードウェアにおける部分 Number Theoretic Transform マスキングのセキュリティマージン分析

1. 背景と問題提起

2024 年に FIPS 203 (ML-KEM) と FIPS 204 (ML-DSA) が標準化され、これらがセキュリティクリティカルなシリコン・ルーツ・オブ・トラスト（Caliptra など）に実装される中、 lattice ベースの暗号アルゴリズムの核心であるNumber Theoretic Transform (NTT) のサイドチャネル攻撃耐性が重要な課題となっています。

完全な NTT マスキングは面積オーバーヘッドが甚大であるため、一部の設計（例：Adams Bridge）では、部分マスキング（最初の INTT レイヤと点乗算のみをブーリアンマスキングで保護し、残りのレイヤはシャッフルに依存する）が採用されています。Adams Bridge の設計者は、未マスキング層に対する CPA（相関電力解析）の計算量が非常に高く（ML-DSA で $2^{46}$、ML-KEM で $2^{96}$）、さらにシャッフルが乗法的に複雑さを増大させるため、攻撃は「現実的に不可能」であると主張しています。

しかし、この主張は以下の点で疑問視されています：

1. 使用されているシャッフル方式（Random Start Index: RSI）が、完全なランダム置換よりもはるかに脆弱である可能性。
2. 従来の CPA モデルではなく、代数的な依存関係を利用したソフト解析的サイドチャネル攻撃（SASCA） や信念伝搬（Belief Propagation: BP） が、部分マスキング設計を破る可能性があること。
3. 設計者の主張するセキュリティマージンが、既存の学術文献や新しい攻撃モデルに対して過大評価されている可能性。

2. 研究方法

本論文は、Adams Bridge のセキュリティ主張を、公開されたサイドチャネル文献と独自の RTL（Register-Transfer Level）シミュレーションに基づく実験的検証によって評価します。

主要なアプローチ

• エビデンスベースのセキュリティマージン分析: 30 以上の論文から得られた証拠を「証明済み」「文献支持」「外挿」「推測」の 4 つの信頼度で分類し、7 つの分析トラックを通じて評価します。
• RTL 検証: 公開されている RTL ソースコードを解析し、実装されているシャッフル機構（RSI）の実際のエントロピーを特定します。
• SASCA パイプラインの構築: RTL シミュレーションから漏洩信号を抽出し、テンプレート攻撃、信念伝搬（BP）、格子還元（Lattice Reduction）を組み合わせた攻撃パイプラインを構築します。
• 層アブレーション研究: どの NTT レイヤを観測すれば BP が収束するかを体系的に調査し、防御策の優先順位を特定します。

3. 主要な貢献と発見

3.1 シャッフル機構の脆弱性（RSI の限界）

設計者は完全なランダム置換（$64! \approx 2^{296}$ 通り）を仮定していましたが、RTL 解析により、実装されているのはRandom Start Index (RSI) であることが判明しました。

• 実態: 1 レイヤあたり 64 通りの順序しか生成されず、エントロピーはわずか6 ビットです。
• 影響: 設計者の主張する乗法的なセキュリティ増幅（$S^L$）は成立せず、攻撃者は各レイヤで 64 通りの候補を列挙するだけで十分です。

3.2 代数的制約による探索空間の削減

• Gentleman-Sande バタフライ: 出力の一方と公開のツイードルファクタが分かれば、他方は代数的に制約されます。これにより、ML-DSA の 1 バタフライあたりの独立した未知数は $2^{46}$ から $2^{23}$ 程度に削減されます。
• SASCA/BP の効果: 従来の CPA がバタフライごとに独立して攻撃するのに対し、SASCA は NTT 全体のファクターグラフを同時に処理します。これにより、個々の係数の列挙（$2^{23}$ など）が不要となり、攻撃モデルが根本的に変化します。

3.3 37 ビットの攻撃モデルギャップ（Empirical Validation）

RTL シミュレーションに基づく SASCA パイプラインによる検証では、設計者の主張する $2^{46}$ のマージンが、以下の要因により$2^{29}$（512 回の RSI 列挙）まで縮小することが示されました。

• ギャップ: 設計者の CPA モデル（$2^{46}$）と SASCA モデル（$2^{29}$）の間には37 ビットの差があります。これは信念伝搬の恩恵を含まない保守的な見積もりです。
• 情報量: 約 992 回のトレース収集で、係数あたりの相互情報量（MI）が飽和し、理論的な完全復元が可能になることが示されました。

3.4 大規模な信念伝搬（BP）の検証と収束条件

ML-KEM の完全な 7 レイヤ INTT ファクターグラフ（896 個のバタフライ、2,048 個の変数）に対する BP 実験を行いました。

• 結果: SNR×N = 3,000 の条件下で、100% の係数復元を達成しました。
• 収束条件（層アブレーション）:
  1. NC1（構造的障壁）: 入力レイヤ（L1）の観測が必須です。L1 が観測されない場合、ファクターグラフが構造的に切断され、どんなに多くのトレースを集めても MI は 0 になります。
  2. NC2-NC4（コスト増幅条件）: 出力レイヤの観測、観測レイヤ間の「ギャップ」、レイヤ数は、トレース数や計算コストを増大させる要因ですが、L1 の欠如のような構造的障壁ではありません。
  3. 観測の多様性: 連続するレイヤ（例：L1-L4）を観測するよりも、均等に間隔を開けたレイヤ（例：L1, L3, L5, L7）を観測する方が、BP の収束効率が圧倒的に高いことが示されました。

4. 結果とセキュリティマージンの再評価

設計者の主張するセキュリティマージンと、文献および実験に基づくマージンの比較は以下の通りです。

対象	設計者の主張（推定）	文献支持の最悪シナリオ（Scenario B）	攻撃者有利シナリオ（Scenario A）
ML-DSA	$\approx 2^{88}$	$2^{59} \sim 2^{63}$ (約 25-29 ビット低下)	$2^{15} \sim 2^{27}$
ML-KEM	$\approx 2^{132}$	$2^{61} \sim 2^{65}$ (約 67-71 ビット低下)	$2^{16} \sim 2^{30}$

• 結論: 設計者の主張は、RSI のエントロピー過大評価や、SASCA/BP 攻撃モデルの無視により、過剰に楽観的であることが示されました。特に ML-KEM においては、既知の暗号文攻撃（KCA）によりベースとなる探索空間自体が縮小します。

5. 意義と提言

5.1 設計への提言

本論文は、部分マスキング設計における防御策の優先順位を明確にしました。

1. L1（入力バタフライ層）の必須マスキング: これが唯一の「構造的障壁」であり、これをマスキングすることで、どんなに多くのトレースを集めても BP が機能しないようにできます。
2. 戦略的ギャップ・マスキング: 連続する 3 つの中間レイヤ（例：L3-L5）をマスキングすることで、攻撃者の観測セットに「ギャップ 3」を強制します。これは中程度のトレース数（SNR×N $\le$ 5,000）では BP 攻撃を無力化しますが、大量のトレース（$\approx$ 50,000）では突破可能です。完全マスキングの 43% のコストで、実用的な防御を提供します。
3. シャッフルの限界認識: RSI などの簡易シャッフルは、完全なランダム置換に比べて脆弱であり、単独での保護手段としては不適切です。

5.2 学術的・産業的意義

• 検証手法の確立: RTL 検証、エビデンスの信頼度評価、感度シナリオ分析を組み合わせた「セキュリティマージン監査手法」を提案しました。
• PQC ハードウェア設計への警告: 面積とセキュリティのトレードオフにおいて、部分的な対策が「安全」と見なされるリスクを指摘し、標準化された検証プロセスの重要性を強調しています。
• 今後の課題: 現在の検証は RTL シミュレーションおよび FPGA 上のソフトウェアモデルに基づいています。実シリコン（SoC 環境）におけるノイズや、ハードウェア実装での SASCA/BP 攻撃の成否は、今後の実証実験（FPGA 測定など）によって確認される必要があります。

総じて、本論文は Adams Bridge の設計が「即座に破られる」ことを示唆するものではなく、主張されているセキュリティマージンが過大評価されており、設計者が想定していない攻撃モデル（SASCA/BP）に対して脆弱である可能性が高いことを定量的に示した重要な研究です。