ML-KEM：格子ベース暗号の理論と原理
もし誰かがあなたの手紙を勝手に開封できる世界を想像してみてください。今は安全でも、将来量子コンピュータが登場すれば、その手紙は簡単に読まれてしまうかもしれません。
こうしたリスクに備えるために登場したのがML-KEMです。
ML-KEMは、量子コンピュータに耐性を持つ暗号方式や暗号アルゴリズムの総称である PQC（耐量子計算機暗号） [1]に含まれ、安全な鍵交換に用いられる代表的な暗号アルゴリズムです。
量子コンピュータの登場により、現在の暗号通信は将来的に解読される可能性があります。特に HNDL（Harvest Now, Decrypt Later）攻撃 によって、今安全と思われる通信も後から読み取られるリスクが高まっています。こうした背景から、各国ではPQCの実用化に向けて標準化が活発に進められています。
2024年8月、NIST（アメリカ国立標準技術研究所）は、PQCの標準として ML-KEM,ML-DSA,SLH-DSAの3つの暗号アルゴリズムを発表しました。
本記事では、この中でもML-KEMに焦点を当てて解説します。残りの2つのアルゴリズムについても順次公開予定です。
暗号プロトコル
├─ 暗号方式（KEM, 署名, 共通鍵暗号）
│ └─ 暗号アルゴリズム（AES, ML-KEM, ML-DSA など）
│ └─ 数学的問題（素因数分解、格子問題 など）
└─ 鍵交換の順序やハンドシェイクの流れ
KEM(Key Encapsulation Mechanism、鍵カプセル化方式)は、共通鍵を安全に共有するための仕組みです。送信者は受信者の公開鍵を使って共通鍵を暗号化（カプセル化）し、受信者は自分の秘密鍵で復号（デカプセル化）して共通鍵を取得します。公開鍵暗号方式を利用するため、KEMは公開鍵暗号の一種と考えることもできます。
ML-KEMの安全性
ML-KEMの安全性は、格子問題という数学的な難問に基づいています。より詳しい説明は、こちらでしているため、ここでは簡単に説明します。
格子問題の直感的なイメージは、「数多くの格子点の中から、特定の条件を満たす格子点を見つけることが非常に難しい」というものです。
実際、ベクトル空間上で定義されているLWE問題やSIS問題は格子に対応させることができ、これらの問題を格子上の問題と捉えたときに解けないことから安全性が保証されています。
ML-KEMでは、このLWE問題をさらに発展させたModule-LWE問題を採用しており、このModule-LWE問題の安全性は格子問題の難しさによって保証されています。
本記事では、ML-KEMがどのように格子問題の理論を応用して構築されているのかを順を追って解説します。まずは、ML-KEMの理論的基盤であるModule-LWE問題から見ていきましょう。
ML-KEMの土台となるModule-LWE問題
先ほど触れたように、ML-KEMはLWE問題を拡張したModule-LWE問題を基盤にしています。そして、その安全性は格子問題の困難さに依存しており、これが量子耐性を支える理論的な柱となっています。
LWE問題がベクトルや行列のみを扱っていたのに対し、Module-LWE問題は、それを多項式も扱っています。
LWE問題では、次のようにベクトルや行列を扱っていました。
(mod q) ( b=As+e , A \in Z_q^{m×n} ) s \in Z_q^n
公開された情報(
Module-LWE問題では、このLWE問題の要素を多項式を要素とする行列やベクトルに置き換えます。それぞれの多項式は、n次未満で、係数は
(x)= b (x) A (x)+ s (x)(mod q) e
-
A -
s -
s(x)=(s_1(x),...,s_k(x))^T
-
-
b -
e
このkは、Module-LWEにおける多項式の数を表します。これは格子暗号プロトコルの重要なパラメータで、kの値が大きいほど、鍵のサイズは大きくなりますが、セキュリティレベルは高くなります。
このように、Module-LWE問題は、LWE問題を「多項式の世界」に持ち込むことで、LWEの安全性と、Ring-LWE問題の効率性[2]の両方を実現しています。
正確には異なりますが、どのようにModule-LWE問題とML-KEMが関わっているかを示します。
【ML-KEMの処理フロー】
┌──────────────────────────┐
│ 1. 鍵ペア生成（公開鍵・秘密鍵） │ ← Module-LWE問題を利用
└──────────────────────────┘
↓
┌──────────────────────────┐
│ 2. 公開鍵を使って暗号化（共有鍵生成） │ ← Module-LWE問題を利用
└──────────────────────────┘
↓
┌──────────────────────────┐
│ 3. 秘密鍵で復号（共有鍵復元） │ ← Module-LWE問題を利用
└──────────────────────────┘
Module-LWEを高速化する魔法：NTT
Module-LWE問題の演算は、外側から見るとk次元のベクトル演算であり、その内側ではn次元の多項式演算 が実行されています。この多項式の乗算は、そのまま実行すると非常に計算に時間がかかってしまいます。
そこで、Module-LWEでは、計算を高速化するために数論変換(Number Theorem Transform, 以下「NTT」と略します) という手法を使用します。NTTは、多項式の乗算を劇的に速くする魔法の技術です。
NTTは、離散フーリエ変換(DFT)の性質を応用したものです。ML-KEMの原理を深く理解するためには、NTT、そしてそれの元となる離散フーリエ変換の理解が欠かせません。
ここではまず、離散フーリエ変換について説明します。もし、すでにご存知の方はこちらからNTTのセクションにお進みください。
離散フーリエ変換、離散逆フーリエ変換
離散フーリエ変換(DFT:Discrete Fourier Transform)は、多項式の乗算を単純な掛け算に置き換えることができる数学的な手法です。
多項式の乗算を実際に考えてみましょう。
n次の多項式
と、n次の多項式 A(x)=A_0+A_1x+A_2x^2+...+A_nx^n を掛け合わせると、その結果は2n次の多項式 B(x)=B_0+B_1x+B_2x^2+...+B_nx^n となります。 C(x)
このとき、係数を直接計算する方法では、計算量は
どうすれば、計算量を減らすことができるでしょうか。
その鍵は、多項式の重要な性質にあります。
「m次の多項式は、m+1個の異なる点の座標がわかれば、その係数が一意に決まる」
例えば、
この性質を利用して、多項式の乗算を高速化する方法を考えます。
- 点の選択：多項式
C(x) 2n 2n+1 x_i - 値の計算：選んだ各点
x_i A(x_i)B(x_i) - 掛け算：
C(x_i)=A(x_i)B(x_i) O(n) - 係数の復元：最後に、得られた
2n+1 (x_i,C(x_i)) C(x)
このアイデアを数学的に厳密にしたものが、離散フーリエ変換です。
1のN乗根
「高速化する方法」を具体的に考える前に、この先の理解のために必要な数学的な準備をしましょう。
N乗すると1となる数を1のN乗根と言います。複素数の世界では、これは全部
ω^N=1
(k=0,1,…,N−1) ω_k=e^{2πik/N}
例えば、N=4のとき、1の4乗根は{
- 1のN乗根の性質
(ζ_N)^N=1 -
(ζ_N)^0,(ζ_N)^1,...,(ζ_N)^{N-1} -
∑_{k=0}^{N-1}(ζ_N)^{kl} L≡0
この三つの性質は後々重要になります。
離散フーリエ変換
数学的準備は終わったので、ここからは「高速化する方法」に戻りましょう。
n次多項式
, A(x)=A_0+A_1x+A_2x^2+...+A_nx^n B(x)=B_0+B_1x+B_2x^2+...+B_nx^n
を乗算した多項式
- A(x)とB(x)の次数の和
2n - かつ2のべき乗である最小の数
N N=2^k
この
求めたい多項式は次のとおりです：
C(x)=C_0+C_1・x+C_2x^2+...+C_{2n}・x^{2n}
です。
手順：
-
評価点の選定
N個の1のN乗根を準備します。x_i=(ζ_N)^i (0 \le i \le N-1) ここで、
ζ_N=e^{2πi/N} を代入すると以下のようなN本の式ができます。
-
点での多項式値を計算
これらの評価点を多項式に代入します。例えば、多項式f(x)に代入すると次のようになります。
f((ζ_N)^0)=f_0((ζ_N)^0)^0+f_1((ζ_N)^0)^1+f_2((ζ_N)^0)^2+...+f_{N-1}((ζ_N)^0)^{N-1}
f((ζ_N)^1)=f_0((ζ_N)^1)^0+f_1((ζ_N)^1)^1+f_2((ζ_N)^1)^2+...+f_{N-1}((ζ_N)^1)^{N-1}
・
・
・
f((ζ_N)^{N-1})=f_0((ζ_N)^{N-1})^0+f_1((ζ_N)^{N-1})^1+f_2((ζ_N)^{N-1})^2+...+f_{N-1}((ζ_N)^{N-1})^{N-1} 同様に、A(x),B(x)についても計算すると、計算結果は、次の式で表すことができます。
A(x_i)=A((ζ_N)^i)=Σ^{N-1}_{j=0}A_j(ζ_N)^{ij} (0 \le i \le N-1)
B(x_i)=B((ζ_N)^i)=Σ^{N-1}_{j=0}B_j(ζ_N)^{ij} (0 \le i \le N-1) - ここで、
(ζ_N)^{ij}
これをi=0,1,...,N-1
\hat A = [ A((ζ_N)^0),A((ζ_N)^1),...,A((ζ_N)^{N-1}) ]
\hat B = [ B((ζ_N)^0),B((ζ_N)^1),...,B((ζ_N)^{N-1}) ] - ここで、
これは、「多項式を1のN乗根で評価した結果のリスト」、すなわち評価点での値の配列です。
ここで重要なのは、「係数の配列」から「評価点の値の配列」への変換 こそが、離散フーリエ変換であるという点です。係数から評価値への変換は、この「順方向の回転」に対応しています。
そして、この二つの評価値の配列を要素ごとに掛け合わせることで、
\hat C = \hat A・\hat B
という新しい評価値の配列が得られます。この計算は、単なる
離散逆フーリエ変換
離散逆フーリエ変換(Inverse DFT)は、離散フーリエ変換(DFT)の逆の操作で、「評価点の値の配列」から、「係数の配列」を復元するための手法です。
\hat C = [C'_0,C'_1,...,C'_{N-1}]
↓
C(x)=C_0+C_1x+C_2x^2+...+C_{N-1}x^{N-1}
多項式の乗算を高速化するプロセスを思い出してください。
- 離散フーリエ変換：多項式を「係数」から「評価点の値」に変換する。
- 要素ごとの乗算：二つの配列を対応する要素ごとにを掛ける。
- 離散逆フーリエ変換：掛け合わせた結果を、再び「係数」に戻す。
離散逆フーリエ変換は、このステップ3に該当します。
逆変換の計算式
逆変換は次のように定義されます：
(mod q) C_j=N^{-1}Σ^{N-1}_{i=0}C'_k(ζ_N)^{-ji} (0 \le j \le N-1)
ここで：
-
(ζ_N)^j x_j (0 \le j \le N-1) -
N^{-1}
1のN乗根を負の指数で用いているのは、離散フーリエ変換で「正の指数」によって回転させた値を、逆方向(負の指数)に回転させて元に戻すためです。また、離散フーリエ変換の過程でN回の加算により値がしてスケーリングされているため、元の大きさに戻すために
この計算により、各
C(x)=C_0+C_1x+C_2x^2+...+C_{N-1}x^{N-1}
このようにして、二つの多項式の乗算結果の計数列を取り戻すことができます。
NTT
NTT(数論変換) は、離散フーリエ変換の原理を応用し、多項式の計算を整数環上(mod q)で高速に、かつ正確に行うためのアルゴリズムです。すなわち、離散フーリエ変換が複素数を扱うのに対し、NTTは 法qの世界(
ML-KEMでは、NTTを利用して、整数環上で多項式演算を高速化しています。
NTTを可能にする「魔法の数」
NTTを機能させるには、特定の数学的条件を満たす必要があります。その鍵となるのが、複素数のフーリエ変換で使う 「1のN乗根」 に相当する、整数版の値です。
ML-KEMが採用しているModule-LWE問題は、多項式を要素とする行列やベクトルに置き換えていますが、それぞれの多項式の次数はn次未満、係数は[0,q-1]の範囲の整数です。NTTを適用するために以下の条件が満たされます。
-
多項式の次数 n
Module-LWE問題で使われる多項式の係数の数nとNTTで使う評価点の数Nは同じで(
n=N -
法 q
q-1が多項式の次数nで割り切れる必要があります。これは、NTTで使う「n次の原始根」r_N
原始根とn次の原始根
mod qの原始根 rは、次の条件を満たす数です。
- rとqは互いに素
- {
} (mod q)が全て異なる r^1,r^2,⋯,r ^{q−1}
→つまり、(mod q)となる最小の正の整数kはq-1 r^k ≡ 1 NTTで使う「n次の原始根」
は、次のように作ります。 r_N
まず、mod qの原始根rを一つ選びます。
そこから、
(mod q)と定義します。 r_N = r^{(q-1)/n} この「n次の原始根」
は次の性質を持ちます。 r_N
(mod q) r_N^n ≡ r^{q-1} ≡ 1 - かつ、
のとき、 0 < k < n !≡ 1 (mod q) r^k
の影響 (q-1)/n
の大きさは、「n次の原始根である」という性質には影響しません。 (q-1)/n - ただし、指数演算の計算負荷や、原始根探索のしやすさには間接的に関係します。
- 指数が大きいと繰り返し二乗法で計算回数が増えます。
の因数構造が複雑だと、原始根の検証に時間がかかります。 q-1
NTTの計算では、
| フーリエ変換の1のN乗根 | NTTの「魔法の数」 |
|---|---|
|
|
|
|
|
|
NTTにおける「n次の原始根」
簡単な例
多項式
-
NTTによる変換：
a(r_N^k) = \sum_{j=0}^{3} a_j r_N^{jk} \pmod q \quad (k=0,1,2,3)
\hat{a} = [a(r_N^0),a(r_N^1),a(r_N^2),a(r_N^3)] -
逆NTTによる復元：
a_j = \frac{1}{4} \sum_{k=0}^{3} \hat{a}[j] r_N^{-kj} \pmod q (j=0,1,2,3)
このように、「係数の配列」から「評価点の値の配列」への変換することで、多項式演算を高速化できます。
NTTを使った多項式演算の高速化を理解したところで、次は、Module-LWE問題を基盤としているML-KEMアルゴリズムについて見ていきましょう。
ML-PKEの核となるK-PKE
ML-KEMは、公開鍵暗号(Public Key Encryption,PKE)アルゴリズムである K-PKE(Key-based Public Key Encryption) を基盤としており、このK-PKEを用いて、共通鍵を安全にカプセル化して送信する仕組みを提供しています。
ML-KEMを理解するうえで不可欠なK-PKEについて、以下で紹介します。
鍵交換（KEM）
└─ ML-KEM
├─ 基盤アルゴリズム：K-PKE
│ └─ 安全性：Module-LWE問題 → 格子問題の難しさ
└─ 高速化：NTTによる多項式演算の高速化
K-PKEでは、公開鍵・秘密鍵を作成、公開鍵による暗号化、秘密鍵による復号化というプロセスを行っています。ここでは、それぞれのプロセスについて順に説明していきます。
1. K-PKEの公開鍵・秘密鍵の生成
ここでは、
入力：
出力：公開鍵(暗号鍵)
-
ランダムな乱数の生成
(p,\sigma)\leftarrow G(d\Vert k) - ハッシュ関数
G - k は Module-LWE のパラメータで、使用する多項式の数を表します。
- ハッシュ関数
-
公開鍵行列の生成
\hat{\mathbf A} = \bigl(\hat A[i,j]\bigr)_{0\le i,j<k}\in (T_q)^{k\times k} \hat{\mathbf A} \bigl(\hat A[i,j]\bigr) -
NTT表現された多項式の生成
n n=256 -
擬似乱数の効率的な生成
前述の乱数p i, j 例として、
q=3329 q 2^{12}=4096
生成された整数がq \hat{A}[i, j]
このプロセスを
k \times k \hat{A} -
-
秘密鍵ベクトルと誤差ベクトルの生成
\mathbf s = (s[i])_{0\le i<k}\in (R_q)^k,\quad \mathbf e = (e[i])_{0\le i<k}\in (R_q)^k - 各
s[i] e[i]
- 各
-
NTT変換
\hat{\mathbf s} \hat{\mathbf e} s[i] e[i] -
LWE関係式の生成
- NTT空間上でLWE関係式(Module-LWE問題)を作成します。
\hat{\mathbf b} = \hat{\mathbf A}\cdot \hat{\mathbf s} + \hat{\mathbf e} = \Bigl(\sum_{j=0}^{k-1}\hat A[i,j]\circ \hat s[j] + \hat e[i]\Bigr)_{0\le i<k}\in (R_q)^k -
公開鍵・秘密鍵の生成
\mathrm{ek}_{\mathrm{PKE}} = (\hat{\mathbf A},\hat{\mathbf b}),\quad \mathrm{dk}_{\mathrm{PKE}} = \hat{\mathbf s} -
出力
(\mathrm{ek}_{\mathrm{PKE}},\ \mathrm{dk}_{\mathrm{PKE}})
2. K-PKE暗号化
ここでは、平文を公開鍵(暗号鍵)
入力：公開鍵(暗号鍵)
出力：暗号文 c
-
一時乱数ベクトル
y y=(y[i])_{0≤i<k} \in (R_q)^k - k行1列の列ベクトル
-
y[i] - 多項式の係数は中心二項分布からサンプリング
-
誤差ベクトル
e_1 e_1=(e_1[i])_{0≤i<k} \in (R_q)^k - k行1列の列ベクトル
-
e_1[i] - 多項式の係数は中心二項分布からサンプリング
-
誤差多項式
e_2 e_2∈R_q - 単一のn次未満の多項式(スカラ)生成
- 係数は中心二項分布からサンプリング
-
NTT変換
\hat y=(y^[i])_{0≤i<k} \in (T_q)^k -
ベクトル
u u=NTT^{−1}(A^T∘y^)+e_1 = A^Ty+e_1
=(∑^{k−1}_{j=0} \hat A[j,i]∘\hat y[j]+\hat e[i])_{0≤i<k}∈(R_q)^k - k行1列ベクトル
- 各要素はn次未満の多項式
- NTTを用いて高速化
- 逆NTTで多項式に復元
- LWE関係式(Module-LWE問題)に似ていますが、uはyを安全に伝えるための情報です。
-
メッセージmの多項式化
μ=Decompress(ByteDecode(m))∈R_q - ByteDecode：バイト列 → ビット列 {0,1}
- ビット列をn個の係数に伸長
- ビット 0 → 係数 0
- ビット 1 → 係数 (q−1)/2
μ(x)=μ_0+μ_1x+...+μ_{n−1}x^{n−1} \in R_q -
メッセージの暗号化
v v=NTT^{−1}(b^T∘y^)+e_2+μ = b^Ty+e_2+μ \in R_q - n次未満の多項式
-
u - 逆NTTで多項式に復元
- 受信者が秘密鍵を使ってメッセージを復号できる本体。
-
出力
c=(u,v) - k行1列のベクトル
u v
- k行1列のベクトル
3. K-PKE復号
ここでは、秘密鍵
入力：秘密鍵
出力：復号文 m'
- 多項式
w w=v−NTT^{-1}(\hat s^T ∘ NTT(u)) = v−s^Tu ∈ R_q - n次未満の多項式
-
w
- メッセージ
m' m′=ByteEncode(Compress(w)) - 暗号化で行った操作(ByteDecode → Decompress) の逆操作
-
- 多項式
w - 係数を 0 または
(q-1)/2 - 丸めた値をビット 0 または 1 に変換
- 係数を 0 または
- 多項式
-
- 得られたビット列をバイト列に変換
-
- 最終的に
m' m
- 暗号化で行った操作(ByteDecode → Decompress) の逆操作
ここまでで、ML-KEMの基盤であるK-PKEアルゴリズムについて、公開鍵・秘密鍵の生成、暗号化、復号化の流れを順に説明してきました。また、K-PKEはModule-LWE問題に基づく安全性を持ち、一時的な乱数の利用によって耐攻撃性を高め、さらにNTTによる高速化を実現していることも理解できたと思います。
ここからは、ML-KEMがこのK-PKEをどのように活用して、共通鍵を安全にカプセル化し、相手に送信する仕組みを提供しているのかを説明していきます。
(再掲)
鍵交換（KEM）
└─ ML-KEM
├─ 基盤アルゴリズム：K-PKE
│ └─ 安全性：Module-LWE問題 → 格子問題の難しさ
└─ 高速化：NTTによる多項式演算の高速化
ML-KEMの全体像：鍵カプセル化(KEM)の処理
ここでは、ML-KEMの仕組みについて詳しく説明していきます。イメージしやすいように、例として「受信者する側=サーバー」「送信する側=クライアント」とします。
1. ML-KEM鍵生成(サーバー)
サーバーはK-PKEを使って、鍵を生成し、公開鍵(鍵カプセル化鍵)をクライアントに送ります。
- 入力：乱数d,z
- 出力：公開鍵(鍵カプセル化鍵)
ek dk
-
K-PKEで乱数dから鍵ペア(公開鍵、秘密鍵)を生成
(ek_{PKE},dk_{PKE})=K-PKE.Gen(d) -
公開鍵(鍵カプセル化鍵)
ek dk 鍵カプセル化鍵
ek=ek_{PKE}
デカプセル化鍵dk=(dk_{PKE},ek,H(ek),z) - Hはハッシュ関数
-
出力
(ek,dk)$
- サーバーは 公開鍵(鍵カプセル化鍵)
ek - デカプセル化鍵
dk
- サーバーは 公開鍵(鍵カプセル化鍵)
2. ML-KEM鍵カプセル化(クライアント)
クライアントはサーバーから受け取った公開鍵(鍵カプセル化鍵)
- 入力：鍵カプセル化鍵
ek(=ek_{PKE}) - 出力：共有秘密鍵
K_{final}
-
セッション鍵シード
\tilde{K} \tilde{K}=m||H(ek) - m：クライアントがランダムに生成した秘密値
-
H(ek) ek - これらを連結して
\tilde{K} ek
-
暫定鍵と乱数の生成
(K,r)=G(\tilde{K}) - ハッシュ関数Gを使用して、暫定鍵
K
- ハッシュ関数Gを使用して、暫定鍵
-
K-PKE暗号化
-
(ek,m,r)
-
-
共有秘密鍵を生成
K_{final}=J(K||c) - ハッシュ関数Jを使用して、暫定鍵と暗号文から共有秘密鍵を生成
-
出力
(K_{final},c)
3. ML-KEMデカプセル化(サーバー)
サーバーは受け取った暗号文cと自分のデカプセル化鍵
-
入力：デカプセル化鍵
dk(= dk_{PKE},ek,H(ek),z -
出力：共有の秘密鍵
K_{final} - 暗号文cをK-PKEで復号 (2-3の「K-PKE暗号化」に対応)
- 秘密鍵
dk_{PKE}
- 秘密鍵
- 暫定鍵
K' (K',r')=G(m'||H(ek)) - ハッシュ関数Gを使用して、暫定鍵
K'
- ハッシュ関数Gを使用して、暫定鍵
- 暗号文の再暗号化(検証用)
- r'を使用して、(ek,m',r')を入力にK-PKE暗号化を再実行し、暗号文c'を生成
- 比較
-
c′ = c -
c′ ≠ c
-
- 共有秘密鍵
K_{FINAL} K_{FINAL}=J(K'||c) - 暫定鍵
K' - このステップにより、
- 正常時：送信者側の
K_{final} - 改ざん時：異なる鍵が生成され、攻撃を防止
- 正常時：送信者側の
- 暫定鍵
- 暗号文cをK-PKEで復号 (2-3の「K-PKE暗号化」に対応)
ML-KEMの全体の流れ
暫定鍵K'
なぜ、暫定鍵
クライアントから送られてきた暗号文 cとサーバー側で再生成した暗号文 c'を比較したとき、一致しない場合は暫定鍵
この問題を防ぐために、ML-KEMではFujisaki–Okamoto変換を用い、暫定鍵
CCA(選択暗号文攻撃)
攻撃者が任意の暗号文を作成し、復号オラクルに入力して復号結果を観察することで、受信者の秘密鍵やランダム値
復号オラクル
受信者の復号処理(復号エラー/成功、改ざん検知の結果、部分的な復号結果など)を「攻撃者が自由に問い合わせられるもの」と仮定した理論モデル。実際に独立した機能があるわけではありません。
IND-CCA2
CCA攻撃に晒されても、攻撃者が秘密情報を推測できないことを保証する強い安全性の概念です。
つまり、ML-KEMでは暫定鍵
ML-KEMについて理解が深まったでしょうか。最後に、もう一度その特徴を簡単にまとめます。
(再掲)
鍵交換（KEM）
└─ ML-KEM
├─ 基盤アルゴリズム：K-PKE
│ └─ 安全性：Module-LWE問題 → 格子問題の難しさ
└─ 高速化：NTTによる多項式演算の高速化
ML-KEMはPQC(耐量子計算機暗号) の一つであり、基盤となるK-PKE暗号アルゴリズムを通じて安全な通信を実現します。その安全性はModule-LWE問題に基づいており、さらに多項式演算を NTT(数論変換) を使って効率的に処理することで、高速化を実現しています。
参考文献：
- https://www.cryptrec.go.jp/report/cryptrec-gl-2004-2022.pdf
- https://www.cryptrec.go.jp/report/cryptrec-tr-2001-2024.pdf
Discussion