ML-KEM：格子ベース暗号の理論と原理
はじめに
PQC（耐量子計算機暗号）やQKD（量子鍵配送）といった最先端の暗号技術に強い関心を持っている大学3年生です。将来的には大学院でこれらの分野を研究し、より安全なデジタル社会の構築に貢献したいと考えています。
暗号技術への興味のきっかけは、もともと熱中していた電子工作です。Bluetooth通信を用いたさまざまなデバイスを自作する中で、「もし通信が第三者に改ざんされたら、意図した通りのデータが得られなくなるのではないか」という懸念を抱くようになりました。
その後、現在使用されている暗号技術について調べる中で、将来的に量子コンピュータの登場が従来の暗号システムに深刻な脅威をもたらす可能性があることを知りました。この問題に対応するために、PQCやQKDといった新しい暗号技術が活発に研究・開発されていることも理解しました。
こうした背景から、私はPQCやQKDの学習と情報発信に取り組んでいます。難しい内容も分かりやすく伝えることを目標に、独学で得た知識を体系的に整理し、記事シリーズとしてまとめています。
本記事では、その中でも標準化されたPQCアルゴリズムの一つ、ML-KEMについてまとめます。
前提
本記事では、以下の知識を前提として進めます。
-
従来の暗号技術(公開鍵暗号方式・共通鍵暗号方式)の基本
-
PQCの直感的な理解
-
ML-KEMで用いられる数学的問題である格子問題の概要
-
離散フーリエ変換（DFT）の原理
-
NTT（数論変換）の原理
これらについて詳しく知りたい方は、以下の記事をご覧ください。
ML-KEMの登場
ML-KEMは、2024年8月、NIST(アメリカ国立標準技術研究所)によって発表された、PQCの標準アルゴリズムの一つです。
量子コンピュータの発展により、従来の暗号技術は将来的に安全性が脅かされる可能性があります。そのため、量子コンピュータでも解くことが困難な数学的問題を基盤とする暗号アルゴリズム、すなわちPQCの開発・実用化は急務となっています。標準化されたML-KEMは、この流れの中で特に注目を集めています。
暗号方式と暗号アルゴリズムの位置付け
暗号プロトコル
├─ 暗号方式（KEM, 署名, 共通鍵暗号）
│ └─ 暗号アルゴリズム（AES, ML-KEM, ML-DSA など）
│ └─ 数学的問題（素因数分解、格子問題 など）
└─ 鍵交換の順序やハンドシェイクの流れ
ML-KEMはKEM（Key Encapsulation Mechanism、鍵カプセル化方式）の一種です。
KEMは、共通鍵を安全に共有する仕組みであり、仕組みは次の通りです。
- 送信者は受信者の公開鍵を使って共通鍵を暗号化（カプセル化）する
- 受信者は自分の秘密鍵で復号（デカプセル化）し、共通鍵を取得する
公開鍵暗号方式を利用するため、KEMは公開鍵暗号の一種と考えることもできます。
ML-KEMの安全性
1. 格子問題
ML-KEMの安全性は、格子問題と呼ばれる数学的に解くことが非常に難しい問題にその根拠を置いています。
特に、ML-KEMでは、この格子問題を暗号に適した形に加工したLWE問題（Learning With Errors）を、さらに多項式の世界に拡張したModule-LWE問題を採用しています。この仕組みによって、ML-KEMは量子コンピュータに対しても強固な安全性を実現しています。
詳しい説明は、こちらをご覧ください。
暗号アルゴリズム ─ ML-KEM（KEM）
↓ 基づく
数学的問題 ─ Module-LWE問題（LWE問題）
↓ 根拠となる
格子問題─ CVP（最近点問題）、SVP（最短ベクトル問題）
2. デカプセル化時の検証ステップ
詳しくは後ほど説明しますが、、ML-KEMのデカプセル化時には、受け取った暗号文が正規の送信者によって正しく生成されたものかを検証する、極めて重要なステップが組み込まれています。
この検証こそが、単なるデータの復号（CPA安全性）を超えて、悪意のある改ざんを防ぐCCA安全性を実現するための核心部分です。
具体的には、受信者は受け取った暗号文を復号して得た情報をもとに、もう一度ゼロから暗号文を再計算します。そして、その再計算した暗号文と、最初に受け取った暗号文が完全に一致するかを比較します。
この比較の結果に応じて、処理が分岐します。
- 一致した場合: 正当な暗号文とみなし、本来の共通鍵を生成します。
- 一致しなかった場合: 改ざんと判断しますが、エラーを返さずに、全く無関係な 「偽の共通鍵」を生成して 正常に処理を終えます。
この「偽の鍵を返す」という挙動により、攻撃者の視点から見ると、正規の暗号文を送ったときも、改ざんした暗号文を送ったときも、常に処理は「成功」したように見えます。
復号の成否が区別できなくなるため、攻撃者は秘密鍵を探るための手がかりを一切得られず、CCA攻撃は無力化されるのです。
Module-LWEを高速化する魔法：NTT
Module-LWE問題の演算は、外側から見ると
そこでML-KEMでは、計算を高速化するために 数論変換(Number Theorem Transform、以下 NTT) を利用しています。NTTは、多項式の掛け算を劇的に速くする「魔法の技術」で、離散フーリエ変換(DFT)の考え方を整数環に応用したものです。
ML-KEMの仕組みを深く理解するためには、離散フーリエ変換やNTTの原理を押さえておくことが欠かせません。
離散フーリエ変換、NTTについて詳しく知りたい方はこちらをご覧ください。
ML-KEMアルゴリズムの概要
ML-KEMのアルゴリズムは、詳細を見る前に大きく以下の流れで整理できます。
-
鍵生成
- K-PKE鍵生成アルゴリズムを使用して、共通鍵を安全に受け取るためのカプセル化鍵（公開鍵）とデカプセル化鍵（秘密鍵）を生成します。
-
カプセル化（Encapsulation）
- 送信者は、受信者のカプセル化鍵（公開鍵）を使用し、共通鍵と暗号文を生成します。
- 送信者は受信者に暗号文のみを送信します。
-
デカプセル化（Decapsulation）
- 受信者は送られてきた暗号文を秘密鍵で復元し、共通鍵を取り出します。
- このとき、暗号文が途中で改ざんされていないかを検証し、安全性が確認できた場合のみ、その共通鍵を有効にします。一致しなかった場合は、ランダム値を代替として共通鍵にします。
ML-PKEの核となるK-PKE
ML-KEMは、公開鍵暗号(Public Key Encryption,PKE)アルゴリズムである K-PKE(Key-based Public Key Encryption) を基盤としており、このK-PKEを用いて、共通鍵を安全にカプセル化して送信する仕組みを実現しています。
K-PKEでは、公開鍵・秘密鍵を作成、公開鍵による暗号化、秘密鍵による復号というプロセスを行っています。ここでは、それぞれのプロセスについて順に説明していきます。
ここでは手順の直感的な理解に焦点を当て、詳細な数式や内部処理については省略しています。より詳しい手順や、簡易実装を伴ったコードについてはこちらの記事をご覧ください。
1. K-PKEの公開鍵・秘密鍵の生成
K-PKEでは、Module-LWE問題を使って公開鍵
入力：
出力：公開鍵(暗号鍵)
-
乱数生成
- ハッシュ関数
G (p,S) -
k
- ハッシュ関数
-
公開鍵行列
\hat{\mathbf A} -
p (i,j) - 各要素はNTT多項式の係数リスト。
-
-
秘密鍵ベクトル
\mathbf s \mathbf e -
S
-
-
NTT変換
-
\mathbf s \mathbf e \hat{\mathbf s}, \hat{\mathbf e} -
k
-
-
LWE関係式の生成
-
\hat{\mathbf b} = \hat{\mathbf A} \cdot \hat{\mathbf s} + \hat{\mathbf e} - NTT表現のまま計算することで高速化。
-
k
-
-
エンコード（圧縮）
-
\hat{\mathbf b} \hat{\mathbf s}
-
-
鍵ペアの生成
- 公開鍵:
\mathrm{ek}_{\mathrm{PKE}} (encoded_b, p) - 秘密鍵:
\mathrm{dk}_{\mathrm{PKE}} encoded_s
- 公開鍵:
2. K-PKE暗号化
公開鍵
入力：公開鍵(暗号鍵)
出力：暗号文
-
公開鍵のデコード
-
\mathrm{ek}_{\mathrm{PKE}} \hat{\mathbf b} p
-
-
公開鍵行列
\hat{\mathbf A^T} -
p \hat{A^T} - 各要素はNTT多項式の係数リスト。
-
-
一時乱数ベクトル
y e_1 -
r
-
-
誤差多項式
e_2 -
r
-
-
NTT変換
-
y
-
-
ベクトル
U U = A^T y + e_1 -
e_1 y -
k
-
メッセージ
m -
m \mu - 例：0 → 0、1 →
(q + 1)/2
-
-
暗号文
V V = b^T y + e_2 + \mu -
y e_2 \mu - 1次元スカラ、各要素はn次元多項式の係数リスト。
-
エンコード(圧縮)
-
U, V -
u,v
-
-
出力
c=(u,v)
3. K-PKE復号
K-PKEでは、秘密鍵
入力：秘密鍵
出力：復号文
-
暗号文のデコード
-
c u, v
-
-
多項式
U,V -
u,v -
U k -
V
-
-
秘密鍵
s - 秘密鍵
dk_{PKE} s -
k
- 秘密鍵
-
中間多項式
w w = V - s^T \cdot U - 暗号化時の多項式化されたメッセージ
\mu - 誤差成分(
e_2+e^Ty-s^Te_1 \mu w = V−s^TU = b^Ty+e_2+μ-(As)^Ty-s^Te_1 = b^Ty+e_2+μ-(b^T-e^T)y-s^Te_1 = μ+e_2+e^Ty-s^Te_1
-
メッセージ
m' -
w m' - 復元された
m' m
-
ML-KEMの基盤であるK-PKEアルゴリズムは、Module-LWE問題に基づく安全性を持ち、一時的な乱数の利用によって耐攻撃性を高め、さらにNTTによる高速化を実現しています。
鍵交換（KEM）
└─ ML-KEM
├─ 基盤アルゴリズム：K-PKE
│ └─ 安全性：Module-LWE問題 → 格子問題(CVP)の難しさ
└─ 高速化：NTTによる多項式演算の高速化
ML-KEM パラメータセット
この表は、ML-KEMで使用される代表的なパラメータセットをまとめたものです。
-
n=256,q=3329 - 階数
k - 共有秘密鍵は常に32バイトで固定されており、暗号化・復号の際の計算量や通信量の目安にもなります。
| パラメータ | n | q | k | カプセル化鍵 (Bytes) | デカプセル化鍵 (Bytes) | 暗号文 (Bytes) | 共有秘密鍵 (Bytes) | 安全性レベル |
|---|---|---|---|---|---|---|---|---|
| ML-KEM-512 | 256 | 3329 | 2 | 800 | 1,632 | 768 | 32 | レベル1 |
| ML-KEM-768 | 256 | 3329 | 3 | 1,184 | 2,400 | 1,088 | 32 | レベル3 |
| ML-KEM-1024 | 256 | 3329 | 4 | 1,568 | 3,168 | 1,568 | 32 | レベル5 |
例えば、より高い安全性を求める場合はML-KEM-1024のように
このように、パラメータ選択はセキュリティと効率のバランスを考慮して行われます。
ML-KEMのアルゴリズム
ここでは、ML-KEMのアルゴリズムを整理します。イメージしやすいように、例として「公開鍵・秘密鍵を生成する側=Alice」「鍵をカプセル化する側=Bob」とします。
1. ML-KEM鍵生成(Alice側)
Aliceは、K-PKEを利用して鍵ペアを生成し、鍵カプセル化鍵をクライアントに送ります。
-
入力：乱数
d,z -
出力：鍵カプセル化鍵
ek dk -
K-PKEで鍵生成
-
(ek_{PKE},dk_{PKE})
-
-
カプセル化鍵・デカプセル化鍵の生成
ek=ek_{PKE} dk=(dk_{PKE},ek,H(ek),z) -
H
-
出力
(ek, dk)
-
K-PKEで鍵生成
2. ML-KEM鍵カプセル化(Bob側)
Bobはサーバーから受け取った鍵カプセル化鍵
-
入力：鍵カプセル化鍵
ek m -
出力：共通鍵
K c -
セッション鍵シードの生成
\tilde{K} = m||H(ek) -
\tilde{K}
-
共通鍵と乱数の生成
(K,r)=G(\tilde{K})
-
K-PKE暗号化
-
c ek, m, r - カプセル化鍵
ek r m c
-
-
出力
(K, c)
-
3. ML-KEMデカプセル化(Alice側)
Aliceは受け取った暗号文
-
入力：デカプセル化鍵
dk c -
出力：共通鍵
K -
デカプセル化鍵を分解
-
dk dk_{PKE},ek,H(ek),z
-
-
暗号文の復号
- m_dec = K−PKE.Dec(
ek,c - 取り出した公開鍵
ek c
- m_dec = K−PKE.Dec(
-
共通鍵と乱数の生成
- (
K r G H(ek))
- (
-
偽の共通鍵の生成
- fake_K =
J(z||c) - CCA攻撃の安全性を保証する
- fake_K =
-
暗号文の再暗号化（検証）
- c_dec = K-PKE.Enc(
ek M r - 暗号文（c,c_dec）の検証
- 一致した場合：
K - 一致しなかった場合：
K K
- 一致した場合：
- c_dec = K-PKE.Enc(
-
共有秘密鍵の出力
-
K
-
-
ML-KEM のアルゴリズムは量子耐性を持つことから非常に注目されています。私自身も現在、ML-KEM の仕組みを深く理解するために学習を進めています。理解をさらに深めるために、Python を用いて擬似パラメータで簡易実装を行いました。興味のある方は、ぜひこちらの記事もご覧ください。
Discussion