ML-KEM
FIPS 203 モジュール格子ベースの鍵カプセル化メカニズム標準 Module-Lattice-Based Key-Encapsulation Mechanism Standard IBMなどが開発
概要
鍵カプセル化メカニズム（KEM）は、特定の条件下で二者間が公開チャネルを介して共有秘密鍵を確立するために使用できるアルゴリズムのセットです。KEMを用いて安全に確立された共有秘密鍵は、対称鍵暗号アルゴリズムと組み合わせて、暗号化や認証といったセキュア通信における基本的なタスクを実行するために使用できます。この標準規格は、ML-KEMと呼ばれる鍵カプセル化メカニズムを規定しています。ML-KEMの安全性は、モジュール学習エラー問題の計算困難性に関連しています。現在、ML-KEMは量子コンピュータを所有する攻撃者に対しても安全であると考えられています。この標準規格は、ML-KEMの3つのパラメータセットを規定しています。セキュリティ強度が高く、パフォーマンスが低い順に、ML-KEM-512、ML-KEM-768、ML-KEM-1024です。 キーワード
1. はじめに
1.1 目的と適用範囲
この規格は、モジュール格子ベースの鍵カプセル化メカニズム（ML-KEM）を規定する。鍵カプセル化メカニズム（KEM）とは、公開チャネルを介して通信する二者間で共有秘密鍵を確立するために使用できるアルゴリズムのセットである。KEMは、鍵確立スキームの一種である。NIST承認の他の鍵確立スキームは、NIST特別刊行物（SP）800-56A「離散対数ベース暗号を用いたペアワイズ鍵確立スキームに関する勧告」2およびSP 800-56B「整数因数分解暗号を用いたペアワイズ鍵確立スキームに関する勧告」3で規定されている。 SP 800-56AおよびSP 800-56Bで規定されている鍵確立スキームは、十分な能力を持つ量子コンピュータを用いた攻撃に対して脆弱である。 ML-KEM は、現在、大規模フォールトトレラント量子コンピュータを所有する敵対者に対しても安全であると考えられている承認済みの代替方式です。ML-KEM は、NIST ポスト量子暗号標準化プロジェクトに提出された CRYSTALS-KYBER KEM 4 の第 3 ラウンド バージョンから派生しています。ML-KEM と CRYSTALS-KYBER の違いについては、付録 C を参照してください。 この標準は、セキュリティ強度とパフォーマンスのトレードオフが異なる ML-KEM の 3 つのパラメータ セットを規定しています。 ML-KEMの3つのパラメータセットはすべて、米国連邦政府の機密扱いではない機密扱いの通信システムを保護するために承認されています。
1.2 背景
過去数年間、量子コンピュータの構築は着実に進展してきました。
大規模な量子コンピュータが実現すれば、多くの一般的に使用されている公開鍵暗号システムのセキュリティが危険にさらされることになります。これには、整数因数分解問題と離散対数問題（有限体上および楕円曲線上）の解の難しさに依存する鍵確立方式やデジタル署名方式が含まれます。その結果、2016年にNISTは、耐量子公開鍵暗号アルゴリズムを選定するための公開耐量子暗号（PQC）標準化プロセスを開始しました。合計82の候補アルゴリズムがNISTに提出され、検討されました。
3回にわたる評価と分析を経て、NISTは標準化に向けて最初の4つのアルゴリズムを選定しました。これらのアルゴリズムは、暗号技術に関連する量子コンピュータの登場後も含め、予見可能な将来にわたって米国政府の機密情報を保護することを目的としています。本規格は、選択されたアルゴリズムCRYSTALS-KYBERの派生形を規定します。これは、Peter Schwabe、Roberto Avanzi、Joppe Bos、Léo Ducas、Eike Kiltz、Tancrède Lepoint、Vadim Lyubashevsky、John Schanck、Gregor Seiler、Damien Stehlé、およびJintai Ding 4によって設計された格子ベースの鍵カプセル化メカニズム（KEM）です。本規格全体を通して、ここで規定されるKEMは、モジュール学習エラー仮定に基づいているため、ML-KEMと呼ばれます。 2.4 擬似コードの解釈
このセクションでは、本標準規格のアルゴリズムを記述するために使用される擬似コードの表記規則について概説します。すべてのアルゴリズムは、2つのグローバル整数定数（𝑛 = 256、𝑞 = 3329）にアクセスできるものと理解されています。また、5つのグローバル整数変数（$ k, 𝜂_1, 𝜂_2, 𝑑_𝑢, 𝑑_𝑣）も存在します。その他の変数はすべてローカルです。5つのグローバル変数は、パラメータセットが選択されると特定の値に設定されます（セクション8を参照）。
本仕様のアルゴリズムが他のアルゴリズムをサブルーチンとして呼び出す場合、すべての引数（つまり入力）は値渡しされます。言い換えれば、入力のコピーが作成され、そのコピーを使用してサブルーチンが呼び出されます。「参照渡し」は行われません。
擬似コードの代入は「←」記号を用いて行われます。例えば、𝑧 ← 𝑦 という文は、変数𝑧に変数𝑦の値が代入されることを意味します。擬似コードの比較は記号「==」を用いて行われます。例えば、式𝑥 == 𝑤 は、変数𝑥と𝑤が同じ値を持つ場合にのみ真となるブール値です。
通常のテキスト（つまり擬似コードの外側）では、異なる表記規則が適用されます。そこでは、標準的な数学表記法に従い、値の代入と比較の両方に記号「=」が使用されます。強調が必要な場合は、代入は代わりに「∶=」で行われます。
変数は常に、そのデータ型に適した有効な値を持ちますが、次の2つの例外があります。
1. 乱数ビット生成器（RBG: random bit generator）の出力はバイト配列データ型ですが、特別な値 NULL も使用できます。この値は、乱数生成が失敗したことを示します。これはML-KEM.KeyGenとML-KEM.Encapsでのみ発生する可能性があります。 2.4.1 データ型
アルゴリズムの入力または出力を表す変数については、そのデータ型（例：ビット、バイト、ビット配列）がアルゴリズムの冒頭で明示的に記述されます。擬似コード内のほとんどのローカル変数については、データ型は文脈から容易に推測できます。その他の変数については、データ型はコメントで宣言されます。単一のアルゴリズムでは、変数のデータ型はその変数が最初に使用されたときに決定され、変更されることはありません。変数名は、異なるデータ型を含む異なるアルゴリズム間で再利用できます。
標準的なアトミックデータ型（例：ビット、バイト）とデータ構造（例：配列）に加えて、𝑚を法とする整数（つまり、$ \mathbb{Z}_𝑚の要素）も抽象データ型として使用されます。$ \mathbb{Z}_𝑚内の変数に代入が行われるたびに、𝑚を法とする縮約が暗黙的に行われます。例えば、$ z \in \mathbb{Z}_m と整数𝑥および𝑦に対して、以下の文
𝑧 ← 𝑥 + 𝑦 (2.1)
は、𝑧 に𝑥 + 𝑦 mod 𝑚 の値が代入されることを意味します。この擬似コードは、𝑚を法とする整数が実際の実装でどのように表現されるか、あるいはモジュラー減算がどのように計算されるかについては無関係です。
2.4.2 ループ構文
擬似コードでは、「while」ループと「for」ループの両方を使用します。「while」ループ構文は説明の必要がないため、その意味は不要です。「for」ループの場合は、プログラミング言語Cのスタイルに従います。アルゴリズム1に2つの簡単な例を示します。単純な合計演算には、「for」ループの代わりに標準的な数式（例：$ \sum\nolimits_{i←1}^n(𝑖 + 3)）を使用します。
2.4.3 整数配列を用いた演算
この標準規格では、𝑚を法とする整数配列（すなわち、$ \mathbb{Z}_𝑚^l の要素）を多用します。典型的なケースでは、関係する値は$ 𝑚 = 𝑞 = 3329、$ ℓ = 𝑛 = 256です。
code:アルゴリズム1 例()
2 つの単純な「for」ループを実行します。
1: for (𝑖 ← 0; 𝑖 < 10; 𝑖++)
2: 𝐴[𝑖] ← 𝑖 ▷ 𝐴 は長さ10の整数配列です
3: end for ▷ 𝐴 の値は (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) になります
4: 𝑗 ← 0
5: for (𝑘 ← 256; 𝑘 > 1; 𝑘 ← 𝑘/2)
6: 𝐵[𝑗] ← 𝑘 ▷ 𝐵 は長さ8の整数排列です
7: 𝑗 ← 𝑗 + 1
8: end for ▷ 𝐵 の値は (256, 128, 64, 32, 16, 8, 4, 2) になります
$ \mathbb{Z}_𝑚^lの配列を用いた演算については後述します。 𝑚 を $ a \in \mathbb{Z}_m かつ $ 𝑋, 𝑌 \in \mathbb{Z}_m^lとすると、以下のステートメント
$ 𝑍 ← 𝑎 ⋅ 𝑋 $ (2.2)
$ 𝑊 ← 𝑋 + 𝑌 $ (2.3)
は、2つの配列 $ 𝑍, 𝑊 \in \mathbb{Z}_m^l を生成し、すべての 𝑖 に対して $ 𝑍[𝑖] = 𝑎 ⋅ 𝑋[𝑖] かつ $ 𝑊 [𝑖] = 𝑋[𝑖] + 𝑌 [𝑖] という性質を満たします。$ \mathbb{Z}_m^l における配列の乗算は、$ 𝑚 = 𝑞 かつ$ ℓ = 𝑛 = 256 の場合にのみ意味を持ち、この場合、それは特定の環における乗算に対応する。この演算については(2.8)で説明する。
2.4.4 代数的オブジェクトの表現
ML-KEMにおける重要な演算の一つは、数論的変換（NTT: number-theoretic transform）です。これは、ある環$ 𝑅_𝑞 上の多項式$ 𝑓 を、同型環$ 𝑇_𝑞 上の「NTT表現: NTT representation」$ 𝑓 に写像するものです。環$ 𝑅_𝑞 と$ 𝑇_𝑞 、そしてNTTについては、4.3節で詳しく説明します。本標準では、$ 𝑅_𝑞 と$ 𝑇_𝑞 の元を、$ 𝑞 を法とする整数の配列を用いて、以下のように擬似コードで表現します。
$ 𝑅_𝑞 の元$ 𝑓 は、次の形の多項式である
$ 𝑓 = 𝑓_0 + 𝑓_1𝑋 + ⋯ + 𝑓_{255}𝑋^{255} \in 𝑅_𝑞 (2.4)
そして、擬似コードでは配列
$ (𝑓_0, 𝑓_1, … , 𝑓_{255}) \in \mathbb{Z}_𝑞^{256}, (2.5)
で表され、その要素には$ 𝑓 の係数が含まれる。表記法を多重定義すると、(2.5) の配列は$ 𝑓 とも表記される。したがって、配列$ 𝑓 の $ i 番目の要素には、多項式$ 𝑓 の $ i 番目の係数が含まれます (つまり、$ 𝑓[𝑖] = 𝑓_𝑖 )。
$ 𝑇_𝑞 の要素 (「NTT 表現」と呼ばれることもあります) $ 𝑔̂ は、それぞれが最大次数 1 の 128 個の多項式の組です。具体的には、
$ 𝑔̂ = ( 𝑔̂ _{0,0}+𝑔̂ _{0,1}X,𝑔̂ _{1,0}+𝑔̂ _{1,1}X,...,𝑔̂ _{127,0}+𝑔̂ _{127,1}X)\in T_q です。 (2.6)
このような代数的対象は、擬似コードでは配列で表現される。
$ (𝑔̂ _{0,0}, 𝑔̂ _{0,1},𝑔̂ _{1,0},𝑔̂ _{1,1},...,𝑔̂ _{127,0},𝑔̂ _{127,1})\in \mathbb{Z}_q^{256}(2.7)
表記法を多重定義すると、(2.7) の配列は$ 𝑔̂ とも表記される。この場合、配列の要素と係数のマッピングは$ 𝑖 \in \{0, 1, ... , 127\} において$ 𝑔̂ [2i]=𝑔̂ _{i,0} であり、$ 𝑔̂ [2i+1]=𝑔̂ _{i,1}
多項式$ f \in R_q とそのNTT表現$ f \in T_q 間の変換は、アルゴリズムNTT（アルゴリズム9）および$ NTT^{−1} （アルゴリズム10）によって行われます。これらのアルゴリズムは、前述のように係数の配列に対して作用し、$ 𝑓̂ = NTT(𝑓) および$ 𝑓 = NTT^{−1}(𝑓̂ ) を満たします。