格子問題とその基本問題

はじめに

現在広く利用されている暗号技術は、量子コンピュータの登場によって安全性が揺らぐ可能性があると指摘されています。この問題への解決策として二つのアプローチが注目を集めています。一つは、量子コンピュータでも解けない計算問題に基づいた「耐量子計算機暗号（PQC）」 です。もう一つは、量子力学の原理を利用する「量子暗号（QKDなど）」 です。

私はこれらの最先端の暗号技術に強い関心があり、独学で得た知識を体系的に整理するために、記事シリーズとしてまとめています。

本記事では、その中でも特に重要な基盤である格子問題に焦点を当てて整理していきます。
格子問題のイメージや直感的な理解から始め、暗号で重要となるLWE問題やSIS問題にも触れ、最終的にこれらがPQCアルゴリズム(例：ML-KEMやML-DSA)の土台としてどのように応用されているかを整理していきます。

なお、PQCやQKD、従来の暗号技術について詳しく知りたい方は、以下の記事もあわせてご覧ください。

• PQC(耐量子計算機暗号)の概要と必要性
• QKD（量子鍵配送）の概要と必要性
• 従来の暗号方式（公開鍵暗号・共通鍵暗号）

格子とは

格子とは、直感的には「規則正しく並んだ点の集合」です。結晶の中で原子が一定の間隔で並んでいる様子に近いです。

数学的には、格子は以下のように定義されます。

格子の定義

m次元ユークリッド空間$R^m$上でn個の線型独立なベクトル$b_1$,$b_2$,...,$b_n$ (n≦m)を使って、次のように表される点の集合を 格子$L$ と定義します。

$L$ = $L$($b_1$,$b_2$,...,$b_n$) := {$Σ_{i=1}^n a_ib_i :a_i \in Z$} , $b_i \in Z^m$

※ここでは行を基底ベクトルとして扱います。

これは、m次元 n個のベクトル$b_i$を、全て整数係数で線型結合して得られる全ての点の集合を意味します。この時、ベクトル$b_1$,$b_2$,...,$b_n$は、格子$L$の基底と呼ばれます。その基底ベクトルを列として持つn x mの整数行列BをLの基底行列と言います。($L = L(B)$)
特にm = nの時、格子Lは完全階数である、といいます。
階数$n$が2以上のとき、生成する異なる基底は無限に存在し(点の集合は同じ)、二つのn x mの整数行列$B_1,B_2$を格子Lの基底行列とすると、$B_1 = UB_2$を満たすn x nのユニモジュラ行列U(整数行列かつ行列式が±1となる行列)が存在します。格子Lの体積$bol(L)$は基底行列Bの取り方によりません。
格子$L$上の最短な日零ベクトルのノルムを$L$の第一逐次最小とよび、$λ_1$($L$)で表します。(格子そのものは同じなので、その中で「最短のベクトル」を探す時の結果も同じです。)

重要ポイント

• 整数係数であること
  実数係数なら空間全体を埋め尽くしてしまいますが、整数に限定することで格子点が離散的に並びます。
• 基底は一意ではない
  一つの格子でも、基底の取り方は複数存在します。
  例えば2次元の場合、$(1,0),(0,1)$を基底にしても、$(-1,0),(0,1)$を基底にしても、生成される格子は同じです。

格子の種類

格子にはいくつかの種類があり、それぞれ異なる役割を担っています。

1. $Z^n$上の格子
   これは、最も基本的な格子です。全ての成分が整数であるn次元ベクトルで構成される、点の集合です。

2. 双対格子
   ある格子$L$に対して、特別な関係を持つもう一つの格子を双対格子$\hat{L}$ と呼びます。
   双対格子は、元の格子$L$のベクトルと内積をとると、必ず整数になるようなベクトルの集合です。

   $\hat{L}$={$x \in R^n$：<x,y> $\in Z$, $∀y \in L$}

   Lの基底行列Bに対して、$\hat{B} = (B^{-1})^T$は双対格子$\hat{L}$の基底行列となり、この$\hat{B}$を双対基底行列と呼びます。m次の単位行列$I_m$に対し、$B\hat{B} = I_m$を満たすので、$vol(L) × vol(\hat{L}) = 1$が成り立ちます。

   元の格子$L$が「密」(基底ベクトルが短い)であるほど、その双対格子$L^⊥$は「疎」(基底ベクトルが長い)になります。後述するカーネル格子とイメージ格子は双対な関係にあります。

3. q-ary格子

   正の整数$q$に対し$qZ^m \subseteq L \subseteq Z^m$(格子$L$は整数格子$Z^m$とそのq倍の間にあること)を満たす完全階数m次元格子$L$をq-ary格子といいます。すなわち、これは剰余環$Z_q$上で定義された格子です。

   二つの自然数$m > n$に対し、任意の整数$q > 0$とn x m整数行列$X$に対して、以下の二つのm次元q-ary格子を定義します。

   $Λ_q(X)$ = {$y \in z^m：∃s \in Z^n s.t. y ≡ sX$} (mod $q$)
   ${Λ_q}^⊥(X)$ = {$y \in z^m：yX^T ≡ 0$} (mod $q$)

   このとき、これらの二つの格子は互いに双対な関係にあります。
   $Λ_q(X)$は「イメージ格子」、 ${Λ_q}^⊥(X)$は「カーネル格子」と呼ばれます。

   $Z_q=Z/qZ$は、整数を法$q$で割った余りの世界、剰余環であり、加算や乗算はこの法のもとで行われます。この環は、LWE問題や耐量子暗号で使われるq-ary格子を構成するための基礎となります。

   剰余環について詳しく知りたい方は、こちらの記事をご覧ください。

格子問題

格子問題とは、格子上で定義される特定の計算問題を指します。これらの問題の多くは、古典コンピュータでは解くのが非常に難しい(NP困難であると信じられている)一方で、量子コンピュータでも効率的に解くことができないと考えられています。

格子問題には様々な種類がありますが、代表的なものをいくつか挙げます。

1. 最短ベクトル問題(SVP：Shortest Vector Problem)
   • 完全階数nの格子$L$の基底{$b_1$,$b_2$,...,$b_n$}が与えられたとき、格子上の最短な非零ベクトル$v \in L$(原点から最も近い格子点)を見つけ出す問題。($||v|| = λ_1(L)$を満たす格子ベクトル$v \in L$を見つける)
   • 高い階数の格子において、SVPを効率的に解く方法は知られていません。
2. 最近ベクトル問題(CVP:Closest Vevtor Problem)
   • 完全階数nの格子$L$の基底{$b_1$,$b_2$,...,$b_n$}と$w \in R^n$ \ $L$が与えられたとき、$w$に最も近い格子ベクトル$v \in L$を見つけ出す問題。
   • SVPよりもさらに、効率的な解法が知られていません。
3. 近似最近ベクトル問題(Gap-CVP)
   • CVPの近似版で、最近ベクトルが特定の距離内にあるかどうかを判定する問題です。

なぜ、格子問題が暗号に利用されるのか

格子には、非常に手強い数学的難問が隠されています。具体的には、格子点の中から特定の条件を満たす点を見つけることは、非常に難しいとされています。その鍵は、格子の基底にあります。

前述のように、同じ格子でも基底の取り方は複数存在しますが、基底には「良い」ものと、「悪い」ものが存在します。「良い」基底とは、各ベクトルが短く、お互いにほぼ直行していることを指し、「悪い」基底とは、各ベクトルが長く、お互いにほぼ平行であることを指します。悪い基底で定義された格子は、一見すると不規則な点の集まりに見え、目的の点を見つけることが極めて困難になります。

すなわち、この「悪い基底」で隠された、格子の持つ幾何学的な構造を解き明かすことこそが、格子問題の本質であり、その難しさの根源です。
これは攻撃者が暗号を解読しようとする際に用いられるだけでなく、暗号の安全性を評価する上でも不可欠です。もし効率的な簡約アルゴリズムが存在して格子問題を簡単に解けてしまうなら、その暗号は安全とは言えなくなってしまいます。

「悪い」基底から「良い」基底に変換することを 格子基底簡約(ユニモジュラ変換) といいます。

• グラム・シュミット直交化

  格子基底簡約(ユニモジュラ変換)を理解する上で欠かせない基礎が グラム・シュミット直交化 です。これは与えられた複数のベクトルを、互いに直交するベクトル集合へと変換する手法です。
  与えられた線形独立なベクトル集合 $B={b_1, b_2,…,b_n} \in \mathbb{R}^m$ に対して、直交ベクトル集合$B^*$=${b^*_1,b^*_2,…,b^*_n}$を構成する手順は次の通りです：
  
  

  1. $b^*_1 = b_1$

  2. $k \geq 2$ のとき(係数 $\mu_{k,j}$ は内積で定義されます)

     $$b^*_k = b_k - \sum^{k-1}_{j=1} \mu_{k,j} b^*_j$$
     $$\mu_{k,j} = \frac{\langle b_k, b^*_j \rangle}{||b^*_j||}$$

代表的な基底簡約アルゴリズム

<LLLアルゴリズム>
LLLアルゴリズムは、最も有名な格子基底簡約アルゴリズムの一つです。
与えられた「悪い」基底を、多項式時間で「ある程度良い」基底に変換することができます。

格子$L$の基底${b_1, b_2,…,b_n} \in \mathbb{R}^{m×n}$とそのグラム・シュミット直交化されたベクトル$b^*_1,b^*_2,…,b^*_n \in \mathbb{R}^{m×n}$について、ある$δ \in \mathbb{R} (1/4 < δ < 1)$を用いて次の条件が成り立つとき、基底がパラメータ$δ$でLLL簡約されているといいます。

1. サイズ簡約（Size-reduced）
   これは、基底ベクトル間の係数$μ_{i,j}$が小さくなるように調整し、基底がほぼ直行していることを保証する条件です。
   - 定義：すべての自然数$1 ≤ j < i ≤ n$について、グラムシュミット係数$μ_{i,j}$が次の条件を満たします。
   $$|μ_{i,j}| ≤ 1/2$$
2. Lovász条件
   これは、基底ベクトルが長さの昇順に近い順序で並んでいることを保証する条件です。
   定義: すべての自然数 $1 \le i < n$ について、ある定数 $\delta$（$1/4 < \delta < 1$）を用いて次の不等式が成立します。
   $$\left(\delta - \mu^2_{i+1,i}\right) \|\mathbf{b}^*_i\|^2 \le \|\mathbf{b}^*_{i+1}\|^2$$

LLLアルゴリズムの処理の流れ
LLLアルゴリズムは、上記の条件を満たす基底を得るために、以下の処理を多項式時間で繰り返します。

1. サイズ簡約: すべての $j < i$ について、サイズ簡約の条件 $|\mu_{i,j}| \le 1/2$ を満たすように、 $\mathbf{b}_i$ から $\mathbf{b}_j$ の整数倍を引く操作を行います。

2. Lovász条件のチェックと交換: $i=1$ から $n-1$ まで順にLovász条件をチェックします。

   • 条件が満たされない場合、隣り合うベクトル $\mathbf{b}_i$ と $\mathbf{b}_{i+1}$ を交換します。
   • 交換後、グラム・シュミット係数を更新し、前のステップに戻って処理を続行します。

3. 終了: すべての $i$ で両方の条件が満たされたとき、アルゴリズムは終了し、LLL簡約基底が出力されます。
   　　
   この処理を繰り返すことで、直交性が高く、短いベクトルを含む新しい基底が得られます。
   LLLは計算が比較的速く、SVPやCVPを「近似的に」解くことが可能です。

<BKZアルゴリズム>
BKZ（Block Korkine-Zolotarev）は、LLLをさらに強力にしたアルゴリズムです。
LLLが隣接する2本のベクトルしか考慮しないのに対し、BKZでは基底をいくつかの ブロック に分割し、そのブロック内で最適なベクトルを探索します。
この「ブロック内でSVPを解く」アプローチにより、BKZはLLLよりも大幅に「良い」基底を生成でき、より短いベクトルを見つけられます。
その分計算量は大きくなりますが、BKZは現代の格子暗号の安全性評価で最も重要なベンチマークとなっています。
もしBKZを用いても解読できないほど困難であれば、その暗号は「十分に安全」と考えられます。

NP困難

クラスP：「効率よく解を求めることができる問題」のグループ
クラスNP：「効率よく解が正しいかを検証できる問題」のグループ

ここで、「効率よく」とは、多項式時間（$n^3$,$nlogn$など）以内で解けることを意味します。

NP困難な問題とは、 「クラスNPに属するどの問題よりも難しい、または同等に難しい」 とされている問題のことです。

これらの問題は、クラスNPの最も難しい部分を代表していると考えられています。もし、NP困難な問題の一つを効率よく解く方法が見つかれば、それはクラスNPに属するすべての問題も効率よく解けることを意味します。これが、多くの暗号技術がNP困難な問題の難しさに安全性の根拠を置いている理由です。

LWE問題(Learning With Errors、誤差付き学習)

要素数が素数qの有限体$F_q$上の秘密ベクトル(($s_1,s_2,..s_n$) $\in {F_q}^n$)に関するランダムな連立線形「近似」方程式が与えられたとき、その秘密ベクトルを復元する問題です。LWE問題の誤差は、平均0,標準偏差σ>0の$Z$上の離散ガウス分布から生成されます。

すなわちLWE問題は、ノイズ（誤差）を含む線型方程式の連立方程式から、元の秘密の係数$s$を解読する問題です。ノイズが解読することを困難にしています。

nを正の整数、qを奇素数とし、平均0、標準偏差σの$Z$上の離散ガウス分布$X$とします。秘密ベクトル$s \in {F_q}^n$を固定し、一様ランダムに選ばれた$a \in {F_q}^n$ と$X$からサンプルされた$e \in Z$に対し、組($a,b$)を出力する確率分布を$L_{s,x}$といいます。

($a,b$) $\in {F_q}^n × F_q$
$b$ ≡ <$a,s$> + $e$ (mod $q$)

次の二つの問題を考えることができます。

• 判定LWE：与えられた組($a,b$)が、確率分布$L_{s,x}$からサンプルされたのか、${F_q}^n × F_q$上の一様ランダムに生成されたかを判定する問題。
• 探索LWE：確率分布$L_{s,x}$のサンプルから、秘密ベクトル$s$を復元する問題。

安全性評価手法としては、判定LWEが使用されます。もし、攻撃者がLWEの出力をランダムなデータと区別できてしまうと、暗号文を「本物」と「偽物」とで区別できてしまい、暗号システムが破られる可能性があるからです。

---

2005年の論文で、RegevはLWE問題の安全性(困難性)を格子問題の解くことの難しさに帰着できることを示しました。すなわち、　LWE問題を解くことができるなら、SVP、CVP、Gap-CVPといった格子の最悪ケース(最も解くのが難しい格子のケース)も効率的に解けることを意味します。LWE問題の安全性は格子問題の最悪ケースの困難性に支えられています。
別の言い方をすると、SVP、CVP、Gap-CVPといった格子の最悪ケースを効率的に解く方法が存在しないため、LWE問題を解くことは難しいと言われています。

---

一般に、LWE問題において、確率分布を$L_{s,x}$から任意個の異なる組が得られるとします。例として、固定した$m$ > 0に対し、確率分布確率分布を$L_{s,x}$からサンプルされた異なる$m$個の組($a_i,b_i$)${ }_{i=1}^m$が得られるとします。
$1 ≦ i ≦ M$、$e_i ← X$に対し、

$b_i$ ≡ <$a_i,s$> + $e_i$ (mod $q$)

• $a_i \in A(m × n行列)$：$iは行ベクトル$
• $b = (b_1,b_2,..,b_m)$
• $e = (e_1,e_2,..,e_m)$：ノイズベクトル

を満たすとします。このときm個のLWEサンプルは以下のように表せます。

($a,b$)
$b$ ≡ $sA^T$ + $e$ (mod $q$)

LWE暗号方式

ここでは、Regevが提案した暗号方式について紹介します。

1. 鍵生成

   一様ランダムに秘密鍵 $s \in {F_q}^n$を選びます。平均0、標準偏差σの$Z$上の離散ガウス分布$X$と秘密鍵$s$が定める$L_{s,x}$が生成する$m$個のLWEサンプル($a_i,b_i$)${ }_{i=1}^m$を公開鍵とします。ただし、$1 ≦ i ≦ M$、$e_i ← X$に対し、$b_i$ ≡ <$a_i,s$> + $e_i$ (mod $q$)を満たすとします。

   • 公開鍵：($a_i,b_i$)${ }_{i=1}^m$ m個のLWEサンプル
   • 秘密鍵：$s \in {F_q}^n$

2. 暗号化
   集合{1,2,..m}の中から、一様ランダムに選んだ部分集合を$S$とします。そして、平文 $μ \in {0,1} (1ビットのメッセージ)の暗号文を次のように暗号化します。

   c = ($Σ_{i \in S} a_i, μ・[q/2] + Σ_{i \in S} b_i) \in {F_q}^n × F_q$

3. 復号
   暗号文 $c = (a,b)\in {F_q}^n × F_q$に対し、秘密鍵$s$を使用して[$b−⟨a,s⟩]_q$を計算します。その値が十分0に近い場合は0を出力し、それ以外の場合は1を出力します。
   ただし、$[t]_q$は元$t \in F_q$を$[-q/2,q/2)$に収めた値とします。

   $b−⟨a,s⟩$
   $= μ・[q/2] + Σ_{i \in S} b_i - s(Σ_{i \in S} a_i)^T$
   $= μ・[q/2] + s(Σ_{i \in S} a_i)^T + Σ_{i \in S}e_i - s(Σ_{i \in S} a_i)^T$
   $= μ・[q/2] + Σ_{i \in S}e_i$
   $≒ μ・[q/2]$

   誤差$Σ_{i \in S}e_i$が無視できないほど誤差が大きいとき、復号に失敗します。すなわち、$Σ_{i \in S}e_i$が$q/4$より小さい時、非常に高い確率で復号に成功します。

q が大きい → 誤差が目立ちにくい（復号しやすいが安全性は下がる）
q が小さい → 誤差が目立つ（効率的だが安全性が落ちる可能性あり）

e が大きい → 誤差が大きく、LWEが解きにくい
e が小さい → 誤差が小さく、LWEが解きやすい

判定LWEの解読

$0 < β < q$を満たす実数$β$を各成分が$F_q$上一様ランダムに選ばれたn x m整数行列$X$に対して、Short Integer Solution(SIS)問題とは、$||v|| ≤ β$かつ$vX^T ≡ 0$ (mod $q$)を満たす非零ベクトル$v \in Z^m$を見つける問題です。つまり、$||v|| ≤ β$を満たすq-ary格子${Λ_q}^⊥(X)$上の短い非零ベクトル$v$を探す問題です。

判定LWE問題とSIS問題

LWEサンプルの組(a,b)に対して、n x m行列$A^T$に対するSIS問題の短い解ベクトル$v \in {Λ_q}^⊥(A^T)$がえられたとします。($0 < ||v|| < βと仮定$)LWEサンプルの組は、$b ≡ sA^T + e$ (mod $q$)を満たすので、

$<v,b> = <v,sA^T + e> = <vA,s> + <v,e> ≡ <v,e>$ (mod $q$)

が成り立ちます。また、$e$の全ての成分は離散ガウス分布からサンプルされたので、

$|<v,e>| \lesssim \quad σ√m||v|| \le σβ√m$

となる。ここで、$σβ√m << q$の場合、LWEサンプル$(a,b)$は格子$L$の点($v$)に非常に近い位置にあり、したがって統計的に格子からのサンプルと区別できてしまいます。

SVPとSIS問題の関係

SIS問題は、SVPの特殊ケースです。SVPは任意の格子$L$に対して定義していますが、SIS問題はq-ary格子${Λ_q}^⊥(X)$という特定の形の格子に対して定義しているため$SIS \lesssim\quad SVP$となります。理論上、一般のSVPが解けるならSISも解けるとされています(逆は成り立ちません)。

探索LWEの解読

格子$L$とベクトル$w$に対し、ある定数$0 < μ \le 1/2$が存在し、$min||w-v||<μλ_1(L)$
を満たすとします。このとき、与えられた$L$の基底から、目標ベクトル$w$に最も近い格子ベクトル$v \in L$を見つける問題をBounded Distance Decoding(BDD)問題といいます。

探索LWE問題とBDD問題

BDD問題はCVPの特殊ケースです。LWEサンプルの組(a,b)は$b ≡ sA^T + e$ (mod $q$)を満たすので、探索LWE問題は$b$を目標ベクトルとするq-ary格子${Λ_q}^⊥(A)$上のBDD問題とみなすことができます。$e$の全ては離散ガウス分布からサンプルされた元なので、eは短いベクトルです。そして、eが復元できると秘密ベクトル$s |in {F_q}^n$をガウスの消去法によって見つけることができます。

CVPとBDD問題の関係

CVPは与えられた$w \in R^n$ \ $L$に最も近い格子点を探す問題であるのに対し、BDD問題は$b ≡ sA^T + e$ (mod $q$)を満たす条件下で、すなわち誤差ベクトル$e$が小さい条件で正しい格子点を探す問題です。理論上、CVPが解けるならBDDも解けるとされています(逆は成り立ちません)。

q-ary格子の役割

q-ary格子である${Λ_q(X)}$(イメージ格子)、${Λ_q}^⊥(X)$(カーネル格子)は、格子問題（SVPやCVPなど）を暗号の文脈で扱いやすい形に定式化するための構造を提供します。判定LWE問題の安全性は、q-ary格子上のSIS問題の最悪ケース困難性に基づいており、探索LWE問題は、q-ary格子上のBDD問題として定式化されます。

CVPとSVPの関係

CVPとSVPの関係は、しばしば混同されがちですが、以下のように整理できます。

CVPの目標点 $b$ を　原点（ゼロベクトル）　に設定すると、CVPは「原点に最も近い格子点を見つける問題」となり、これはSVPの定義と完全に一致します。つまり、CVP は SVP を含むより広い問題なので、CVP が安全なら SVP も安全と考えられます。

NTRU問題

NTRU問題は多項式を用いた有限環上の格子問題です。
二つの正の整数$n$と$q$に対して、$R = Z[x]/(X^n - 1)$,$R_q = R/qR$と定めます。
すなわち、$R_q$は「係数が 0～q-1 の整数で、次数が N-1 以下の多項式全体」です。
係数が小さい二つの多項式$f(x) \in {R_q}^×$,$g(x) \in R_q$に対して、$h(x) = g(x)・f(x)^{-1} \in R_q$とします。($R^×$は、環$R$の可逆元の集合を表し、逆元$f^{-1}(x)$を計算できることを保証します。)
このとき、$h(x)$から、$f(x)$または$g(x)$を復元する問題をNTRU問題といいます。

NTRU暗号方式

以下では、二つの正の整数$n$と$q$に加えて、$p<<q$を満たす正の整数パラメータ$p$を準備します。

1. 鍵生成

   • 全ての係数の絶対値が小さい二つの多項式$f(x),g(x) \in R$を選びます。$f(x)$は、二つの環$R_p,R_q$において可逆とします。すなわち、$f_p(x) \in R_p$,$f_q(x) \in R_q$が存在し、

   $f_p(x)・f(x) = 1 \in R_p$ , $f_q(x)・f(x) = 1 \in R_q$

   を満たします。具体的には、$2d < n$を満たす正の整数$d$に対して、$f(x) \in T(d+1,d),g(x) \in T(d,d)$を選びます。

   $T(d,e)$ = {$a(x) \in R：a(x)$の$d$個の係数は1 , $a(x)$のe個の係数は-1 , その他の係数は全て0}

   • 公開鍵：$h(x) = f_q(x)・g(x) \in R_q$
   • 秘密鍵：$f(x),f_p(x)$

2. 暗号化

   • $r(x) = T(d,d)$をランダムに選びます。
   • 平文$m(x) \in R_p$と公開鍵$h(x)$に対して、$r(x)$を使用して暗号文$c(x)$を生成します。

     $c(x) = p・r(x)・h(x)＋m(x) \in R_q$

3. 復号

   • 暗号文$c(x) \in R_q$に対し、秘密鍵$f(x) \in R,f_p(x) \in R_p$を用いて復号します。

     $f_p(x)・[f(x)・c(x)]_q \in R_q$

NTRU問題の解読

係数ベクトルと回転操作
環$R = Z[x]/(X^n-1)$の任意の元は$n-1$次の多項式$a(x) = a_0 + a_1x + ...＋a_{n-1}x^{n-1}$で表すことができ、その係数ベクトルを$a = (a_0,a_1,...,a_{n-1})$と書けます。$a(x)$の係数ベクトル$a$に対する回転操作を以下のように定めます。

$rot(a) = (a_{n-1},a_0,a_1,...,a_{n-2})$

すなわち、回転ベクトル$rot(a)$は、$a(x)$にxを乗じた多項式x・a(x)の係数ベクトルです。乗じる回数を$i$とすると、多項式$x^ia(x)$の係数ベクトルは$rot^i(a)$です。環$R$において、$x^n=1$より、$rot^n(a)$は元ベクトル$a$に一致します。

NTRU格子
NTRU問題における公開多項式(公開鍵)$h(x)$の係数ベクトルを$h=(h_0,h_1,...h_{n-1})$と定め、$h$から$rot^{n-1}(h)$までをn x n行列で表すと以下のようになります。

Hに$1$から$x^{n-1}$まで順に掛けると以下のように表現できます。

次の$2n$次元の行列B

で生成される$2n$次元の格子$L=L(B)$をNTRU格子といいます。このとき、$L$は連結ベクトル$(f|g)\in Z^{2n}$を含みます($f,g \in Z^n$はそれぞれ秘密多項式$f(x),g(x) \in R$)。
実際に、

$h(x) ≡ f_q(x)・g(x)$ (mod $q$)
$h(x)・f(x) ≡ g(x)$ (mod $q$)

より、$g(x) = h(x)・f(x) + q・r(x)$を満たす多項式$r(x) \in R$が存在します。そして、$(f|g) = (f|fH＋qr) = (f|r)B \in L$が成り立ちます。

連結ベクトル$(f|g) \in Z^{2n}$が非常に短く、最短ベクトルであるとすると、NTRU問題はSVPに帰着できます。

LWE問題の応用と安全性

Ring-LWE問題

LWE問題がベクトルと行列を扱うのに対して、Ring-LWE問題は係数が整数の多項式を対象とします。「Ring(環)」という名前の通り、この問題は多項式環上で定義されます。

• 多項式環$R_q$の定義
  まず、整数環$Z$を法$q$で割った環

  $Z_q=Z/qZ$

  を考えます。
  次に、多項式環$Z_q[x]$を作り、さらに$z^n+1$で割った剰余環をとることで次のように定義されます。

  $R_q=Z_q[x]/(x^n+1)$

  つまり、次数が$n$未満で、係数が$0$から$q-1$の範囲に収まる多項式が要素となります。
  この環では $x^n \equiv -1$ という関係が成り立つのが特徴です。

• Ring-LWE問題の定義

  LWE問題と同様に、秘密の多項式$s(x) \in R_q$を仮定します。

  ランダムに生成された多項式$a(x) \in R_q$と小さなノイズの多項式$e(x)$を使って、次のように多項式$b(x)$を生成します。

  $b(x)=a(x)s(x)+e(x)$(mod q)

  公開されるのは $a(x)$ と $b(x)$ であり、この情報から秘密の多項式 $s(x)$ を求めることが Ring-LWE問題の目的です。

Ring-LWEの意義と利点

Ring-LWEの最大の特徴は、LWEと同等の安全性を保ちながら、実用面で大幅に改善された点にあります。

• 鍵サイズの削減

  LWEでは大きな行列 $A$ が必要でしたが、Ring-LWEでは公開鍵として わずか1つの多項式 $a(x)$ を提示するだけで済みます。
  これにより、鍵のサイズは数千〜数万分の1に縮小され、データ通信が格段に効率化されました。

• 計算速度の向上

  Ring-LWEの演算の中心は「多項式の掛け算」です。これは、LWEの行列-ベクトル積よりもはるかに効率的であり、さらにNTT（数論変換）^[1]を用いることで大幅に高速化されます。

  しかし、Ring-LWEの持つ特定の構造は、安全性をさらに高めるための課題も残していました。この課題を克服するために開発されたのが、次に説明するModule-LWEです。

Ring-LWEからModule-LWEへ

ただし、Ring-LWEの持つ特有の構造は、場合によっては、安全性に影響を与える可能性が指摘されていました。この課題を克服し、より柔軟で強固な安全性を提供する仕組みとして発展したのが、Module-LWEです。

Module-LWE問題

Ring-LWEの効率性とLWEの柔軟なセキュリティ性を組み合わせるために提案された問題です。
イメージとしては、Ring-LWEが「1つの多項式環」で表現していた世界を、LWEのような「ベクトル・行列の構造」に拡張したものです

• $k$ は、Module-LWEにおける「多項式の数」を表すパラメータです。値が大きいほどセキュリティは高まりますが、その分鍵サイズも大きくなります。

数式で表すと次のようになります：

$b(x) = A(x)s(x) + e(x) \pmod q$

• $A(x)$：多項式を要素とする行列（$k \times k$）
• $s(x)$：秘密ベクトル（$k \times 1$）、$s(x)=(s_1(x),...,s_k(x))^T$
• $b(x)$：公開ベクトル（$k \times 1$）
• $e(x)$：ノイズベクトル（$k \times 1$）

ここで扱う各要素は、Ring-LWEと同じく多項式環 $R_q$ に属する多項式です。

Module-LWEの意義と利点
1. Ring-LWEと同等の効率性
計算の中心は多項式演算なので、鍵サイズや計算速度の面でRing-LWEと同等のメリットを持っています。
2. LWEに近い安全性
複数の多項式をベクトル・行列で扱う構造を持つため、単一の多項式環に依存するRing-LWEよりも堅牢とされます。

このようにModule-LWEは、効率性と安全性を両立した格子問題として位置づけられており、
NISTが標準化したPQCの標準アルゴリズムの一つであるML-KEM も、このModule-LWEの安全性を基盤にしています。

なお、本記事では、格子問題の理解に焦点を当てているため、Module-LWEがML-KEMでどのように使用されているかを知りたい方は、こちらをご覧ください。

---

量子コンピュータの登場により、従来の暗号技術が将来的に危殆化すると指摘される中で、格子問題は「量子コンピュータでも効率的に解けない問題」として強い注目を集めています。実際に、格子問題を安全性にしているLWE問題、さらに安全性を高めたModule-LWE問題は、ML-KEMで採用されています。
ML-KEMのより具体的な仕組みについて知りたい方は、ぜひこちらの記事もご覧ください。

---

参考文献:

1. https://www.acompany.tech/privacytechlab/lattice-based-cryptography
2. 國廣 昇,安田 雅哉,水木 敬明,高安 敦,高島 克幸,米山 一樹,大原 一真,江村 恵太 (2024)「暗号の理論と技術 量子時代のセキュリティ理解のために」(KS理工学専門書)

脚注

1. NTTについてはこちらの記事をご覧ください。