💻 computer science

Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware

この論文は、Lean 4 と Mathlib を用いて、ML-KEM/ML-DSA の PQC ハードウェアにおける NTT パイプラインの算術的マスキングが、新鮮なランダム性を用いることで ISW 第一順序プローブモデルにおいて構造的に安全であることを、9 つの定理で機械的に検証し、Adams Bridge アダプタの構造的欠陥を明らかにしたものです。

原著者： Ray Iskander, Khaled Kirah

公開日 2026-04-23

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Ray Iskander, Khaled Kirah

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

🍪 物語の舞台：未来のクッキー工場

想像してください。世界中で使われる新しい「超安全なクッキー（暗号）」を作る巨大な工場があります。この工場では、クッキーの味（秘密のデータ）を盗まれないように、**「魔法の粉（マスク）」**をまぶして加工しています。

この工場には、クッキーを並べる**「ベルトコンベア（NTT パイプライン）」**があり、クッキーは複数の工程（ステージ）を通過して完成します。

🔍 問題：「安全なはずなのに、なぜ危ないの？」

これまでの設計では、「各工程（ステージ）ごとに魔法の粉をまけば、全体も安全だ」という直感が通用していました。
しかし、この論文の著者たちは、**「直感は嘘をつくことがある」**と気づきました。

ある設計（Adams Bridge）の失敗例：
最初の工程（0 番目）ではしっかり魔法の粉をまいていましたが、その後の工程では粉をまきませんでした。「最初の工程が安全なら、その後の工程も大丈夫だろう」と考えた設計者たちがいました。
しかし、**「最初の工程で隠れた秘密が、次の工程で漏れ出してしまう」**という罠がありました。

🛠️ この論文の解決策：「新しい魔法のレシピ」

著者たちは、**「Lean 4」**という「数学の証明をコンピュータにチェックさせる魔法の道具」を使って、以下の 3 つの重要な発見をしました。

1. 「魔法の粉」は「毎回新しいもの」でなければならない

アナロジー： 料理をするとき、一度使ったスプーンを洗わずに次の料理に使えば、味が混ざってしまいます。
発見： 各工程（ステージ）を通過するたびに、**「新しい魔法の粉（Fresh Masking）」**を必ずまかなければ、秘密は守れません。前の工程の粉が残っていると、後で秘密がバレてしまいます。

2. 「見かけ上の安全」は嘘つき（罠）

アナロジー： 「クッキーの形が変わらなければ、味も変わらない」と思っている人がいます。でも、実は中身（秘密）が変わっても、形（出力）は同じに見えることがあるのです。
発見： 設計者が「この工程は安全だ」と判断するために使う「点ごとのチェック」は、実は**「間違っている」**ことが証明されました。これを「点ごとのチェックの罠」と呼んでいます。正しいチェック方法は、「魔法の粉の全パターンを混ぜたとき、結果が均一にばらけているか」を見ることです。

3. 「ベルトコンベア全体」が安全になる証明

アナロジー： 1 つの工程が安全でも、ベルトコンベア全体が安全とは限りません。でも、**「各工程で必ず新しい魔法の粉を使う」というルールを守れば、「ベルトコンベア全体が数学的に 100% 安全」**であることが証明できました。
発見： このルール（Fresh Masking Design Principle）を守れば、どんな大きさの工場（パイプラインの長さ）でも、どんな種類のクッキー（モジュラス）でも、**「秘密が漏れる確率はゼロ」**であることが、コンピュータに厳密に証明されました。

💡 なぜこれが重要なの？

従来の「直感」は危険だった： これまで多くのエンジニアは「各工程が安全なら全体も安全」と信じていましたが、それは誤りでした。この論文は、その誤解を数学的に正しました。
失敗した設計の理由がわかった： 現在使われている「Adams Bridge」という設計がなぜ脆弱だったのか、その根本原因（魔法の粉を途中からまき忘れていること）が、この証明によって明確に説明されました。
証明書の発行： この研究は、単なる「お話し」ではなく、**「コンピュータが厳密にチェックした証明（ゼロの誤り）」**です。これから新しい暗号ハードウェアを作る人たちは、この証明書を「FIPS（政府の安全基準）」の申請書に添付して、「これは数学的に安全です」と主張できるようになります。

🎯 まとめ

この論文は、**「未来の暗号ハードウェアを作る人へ」**のメッセージです。

「『各工程が安全なら全体も安全』という古い考えは捨ててください。代わりに、**『各工程ごとに新しい魔法の粉（ランダムなマスク）を必ず使う』**というシンプルなルールを守ってください。そうすれば、コンピュータが証明した通り、あなたの設計は絶対に安全になります。」

これは、複雑な数学の証明を、**「新しい粉を毎回使うこと」**というシンプルで重要な設計原則に変換した、非常に実用的で素晴らしい成果です。

この論文「Fresh Masking Makes NTT Pipelines Composable: Machine-Checked Proofs for Arithmetic Masking in PQC Hardware」は、ポスト量子暗号（PQC）ハードウェア、特に ML-KEM（FIPS 203）および ML-DSA（FIPS 204）で用いられる数論的変換（NTT）のアーキテクチャにおける、算術的マスキングの安全性を形式検証（Lean 4）によって証明したものです。

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

1. 問題定義

ポスト量子暗号のハードウェアアクセラレータでは、NTT（数論的変換）がパイプライン化されたコルリー・チューキー（Cooley-Tukey）バタフライ回路として実装されています。

既存の課題: 各ステージが個別に安全であっても、パイプライン全体として安全であることは保証されていません。特に、有限体 $Z_q$ 上の算術マスキングにおける「合成（Composition）」の性質は、これまで機械的に検証された証明が存在しませんでした。既存の形式検証ツールやフレームワーク（ISW, t-SNI, PINI, DOM など）は、主に GF(2) 上のブール回路に焦点を当てており、NTT バタフライのような $Z_q$ 上の構造には適用されていませんでした。
設計者の誤解（トラップ）: 設計者が「各出力ワイヤの値が秘密情報に依存しない（Pointwise Value-Independence）」という直感的な性質を検証しようとすると、バタフライ回路ではこの性質が偽であることが判明します。これにより、安全な設計が誤って「不安全」と判定されるリスクや、逆に重要な脆弱性を見逃すリスクがありました。
実例（Adams Bridge）: CHIPS Alliance の Caliptra プロジェクトに含まれる「Adams Bridge」アクセラレータは、INTT の最初のラウンド以外でフレッシュなマスキングを適用していないことが実証的に指摘されており、これが構造的な脆弱性の原因であると考えられていましたが、その理論的根拠は形式化されていませんでした。

2. 手法とアプローチ

著者らは、定理証明支援系 Lean 4 とその標準ライブラリ Mathlib を使用し、ゼロの未検証アサーション（zero sorry）で完全な形式証明を構築しました。

対象モデル: $Z_q$ 上の算術マスキング（秘密 $s$ を $s_0 + s_1 = s \pmod q$ とする）。
脅威モデル: ISW 第一-order プロービングモデル（敵対者が各クロックサイクルで 1 本のワイヤのみを観測可能）。
核心となる洞察: NTT バタフライ回路は、フレッシュなランダムマスクに対してアフィン（線形 + 定数）関数として振る舞います。これは、ブールマスキングにおける XOR 演算に相当する「簡単なケース」です。この線形性を利用することで、複雑な非線形ガジェット（ISW 乗算など）とは異なる、直接的な合成証明が可能になります。
証明戦略:
1. 値の独立性（Value-Independence）が、フレッシュなランダム性下で一定の周辺分布（Constant Marginal Distribution）を意味することを証明（r-bearing bridge）。
2. バタフライ出力の「周辺一様性（Marginal Uniformity）」を定義し、これが秘密情報に依存しないことを証明。
3. 各ステージでフレッシュなマスクを適用する場合、パイプライン全体がこの一様性を維持することを帰納的に証明。

3. 主要な貢献

論文は、以下の 3 つの機械検証された結果を提示しています。

r-bearing bridge（r を含む橋渡し）:
- 先行研究 [15] で未解決だった「フレッシュなランダム性（fresh randomness）を含む場合」の証明を完了しました。
- 「値の独立性」が「相互情報量が 0（MutualInfoZero）」を意味することを、代数的な代理（MutualInfoZero）を通じて証明しました。
バタフライのコンテキスト別一様性（Butterfly Per-Context Uniformity）:
- 重要な警告: バタフライ出力における「点ごとの値の独立性（Pointwise Value-Independence）」は偽であることを証明しました（ $q=5$ の反例を示す）。
- 正しい性質: 代わりに、「フレッシュなマスクに対して周辺分布が一様である（Marginal Uniformity）」という性質が成立することを証明しました。具体的には、任意の出力値 $v$ に対して、それを生成するマスク値がちょうど 1 つ存在し、これは秘密情報やツイードル係数に依存しません。
- この証明は、 $q > 0$ （素数・合成数問わず）、すべてのツイードル係数、すべての入力に対して普遍的に成立します。
パイプライン合成（Pipeline Composition）:
- $k$ ステージの NTT パイプラインにおいて、各ステージでフレッシュなマスクを適用する場合、すべてのステージで「コンテキスト別一様性」が維持されることを証明しました。
- これは ISW 第一-order プロービングモデルにおける安全性の核心的な代数的不変量です。

4. 結果とアーティファクト

証明の規模: Lean 4 ファイル 3 本（約 580 行）、9 つの定理、1,738 件のビルドジョブ。すべてゼロエラー、ゼロ警告で成功しました。
Adams Bridge への適用: この証明により、Adams Bridge アクセラレータが「フレッシュなマスキングの設計原則」に違反している（中間ステージでマスクが更新されない）ことが理論的に説明されました。これにより、先行研究 [1, 2] で観測された構造的な脆弱性の根本原因が特定されました。
将来の非線形ガジェット: 本論文は線形（アフィン）なバタフライ回路に限定されています。非線形なガジェット（Barrett 簡約など）については、別の論文 [3] で PF-PINI(2) として扱われ、ここでは「1 ビットのバリア（1-Bit Barrier）」が証明されることが示唆されています。

5. 意義とインパクト

FIPS 認証への貢献: 本論文は、ハードウェア設計者や FIPS 140-3 認証機関が、NTT パイプラインの安全性を証明するために直接引用できる、機械検証された普遍的な証拠を提供します。
設計原則の確立: 「NTT パイプラインの各ステージで独立したフレッシュなマスクを適用すること」が、第一-order プロービングモデルにおける安全性を保証する設計原則（Fresh Masking Design Principle）であることを形式化しました。
誤った検証の防止: 「点ごとの値の独立性」という誤った性質を検証することによる誤判定を防ぐための警告を提供し、正しいセキュリティ特性（周辺一様性）を明確に定義しました。
ツールチェーンの統合: 形式証明（Lean 4）と構造依存性分析ツール（QANARY）を補完的に組み合わせることで、PQC ハードウェアの安全性検証の新しいパラダイムを提示しています。

要約すると、この論文は、ポスト量子暗号ハードウェアの安全性において長年懸念されていた「NTT パイプラインの合成安全性」を、算術マスキングの線形性を活用して初めて機械的に証明し、実装における重要な設計指針と検証基準を確立した画期的な研究です。