LLL系の基底簡約についてまとめてみた

Last updated at 2025-08-05Posted at 2025-08-05

間違えなどにお気づきの方が居ればご指摘ください．
他のアルゴリズムも随時追加していきます．

最初に

みなさん．格子暗号というものをご存じでしょうか．知っている人もいれば知らない人もいるかと思います（当たり前）．
この格子暗号というものは，いわゆる耐量子計算機暗号の一つです．簡単に言えば，量子計算機を使っても簡単には解けない暗号の一つで，格子という数学の道具を使っているものです．$\boldsymbol{n}$次元格子とは，一次独立な$n$本のベクトル$\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n$（この$n$本のベクトルの組$\lbrace\boldsymbol{b}_1, \ldots, \boldsymbol{b}_n\rbrace$を格子の基底と呼びます）に対して

L=\mathcal{L}(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n):=\left\lbrace \left.\sum_{i=1}^na_i\boldsymbol{b}_i~\right|~a_1,\ldots.a_n\in\mathbb{Z}\right\rbrace

と定義されます．簡単に言えば，ベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\in\mathbb{R}^n$の整数係数の一次結合全体の集合です．
もう少し，数学的に言えば，次の最短ベクトル問題（SVP）や最近ベクトル問題（CVP）が量子計算機でも求解困難であることによりその安全性が保障される暗号です．

最短ベクトル問題（SVP）
$n$次元格子$L$が与えられたとき，$\lVert\boldsymbol{v}\rVert$が最小となるような非零なベクトル$\boldsymbol{v}\in L\setminus\lbrace \boldsymbol{0}_n\rbrace$を見つけよ．

簡単に言えば，一番短い$L$の元を見つけてね，という問題です．

最近ベクトル問題（CVP）
$n$次元格子$L$と$L$の元ではないベクトル$\boldsymbol{t}\in \mathbb{Z}^n\setminus L$（目標ベクトルやターゲットベクトルと呼ばれる）が与えられたとき，$\lVert\boldsymbol{v}-\boldsymbol{t}\rVert$が最小となるような$L$のベクトル$\boldsymbol{v}\in L$を見つけよ．

簡単に言えば，$\boldsymbol{t}$に一番近い$L$の元を見つけてね，という問題です．

さて，ここで書く格子基底簡約とSVPやらCVPやらに何の関係があるんや，と思った方もいらっしゃるかもしれませんが，実はこれらの格子問題（SVPやCVPなどの総称）を解くに当たって，格子基底簡約は必須の技術です．なんでなのかについては詳しくは述べませんが，非常に簡単に言うと，基底簡約を施すことによって問題を解くのが楽になります．
ここでは，そんな基底簡約の中でもLLL系のアルゴリズムについてまとめていこうと思います．

ちょっとした準備

格子$L$の基底ベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n$に対して，

\left\{
\begin{aligned}
\boldsymbol{b}_1^\star &:= \boldsymbol{b}_1, \\
\boldsymbol{b}_i^\star &:= \boldsymbol{b}_i - \sum_{j=1}^{i-1} \mu_{i, j} \boldsymbol{b}_j^\star,~
\mu_{i, j}:=\frac{\langle \boldsymbol{b}_i, \boldsymbol{b}_j^\star\rangle}{\| \boldsymbol{b}_j^\star \|^2}~(1 \!\leq\!  j \!<\! i \!\leq\! n).
\end{aligned}
\right.

で定まる$\boldsymbol{b}_i^\star$をGram-Schmditの直交化ベクトル，$\boldsymbol{U}:=(\mu_{i, j})_{1\le j<i\le n}$をGram-Schmditの直交化係数行列と呼びます．まぁ，B1やB2で習うようなGram-Schmditの直交化法そのものです．
また，

\mathrm{vol}(L)=\prod_{i=1}^n \lVert \boldsymbol{b}_i^\star\rVert

を$L$の体積もしくは行列式と呼び，

\lambda_i(L):=\min_{\begin{matrix}\boldsymbol{v}_1,\ldots,\boldsymbol{v}_i\in L\\ \boldsymbol{v}_1\ldots, \boldsymbol{v}_i:\text{一次独立}\end{matrix}} \max\lbrace \lVert \boldsymbol{v}_1\rVert, \ldots, \lVert \boldsymbol{v}_i\rVert\rbrace

を第$\boldsymbol{i}$逐次最小と呼びます．特に，$\lambda_1(L)$は$L$の非零な最短ベクトルです．
更に，写像

\pi_\ell : \mathbb{R}^n \longrightarrow \langle \boldsymbol{b}_1, \dots, \boldsymbol{b}_{\ell-1} \rangle_\mathbb{R}^\perp=\langle \boldsymbol{b}_\ell^\star, \dots, \boldsymbol{b}_n^\star \rangle_\mathbb{R},~
\boldsymbol{x} \longmapsto \sum_{i = \ell}^n \frac{\langle \boldsymbol{x}, \boldsymbol{b}_i^\star \rangle}{ \| \boldsymbol{b}_i^\star \|^2 } \boldsymbol{b}_i^\star

を$\langle \boldsymbol{b}_1, \dots, \boldsymbol{b}_{\ell-1} \rangle_\mathbb{R}$の直交補空間$\langle \boldsymbol{b}_1, \dots, \boldsymbol{b}_{\ell-1} \rangle_\mathbb{R}^\perp=\langle \boldsymbol{b}_\ell^\star, \dots, \boldsymbol{b}_n^\star \rangle_\mathbb{R}$への直交射影とします．

LLLアルゴリズム

恐らく基底簡約アルゴリズムの中では最も有名なんじゃないかなと思っています．LLLアルゴリズム¹はLLL簡約基底を求めるアルゴリズムで，LLL簡約基底とは次のようなものです．

LLL簡約基底

$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$を$n$次元格子$L$の基底とします．このとき，$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が簡約パラメタ$\frac{1}{4}<\delta<1$に対してLLL簡約されているとは

\begin{array}{ll}
&(\textbf{サイズ簡約条件})&1\le{}^\forall j<{}^\forall i\le n,&\lvert\mu_{i, j}\rvert\le \frac{1}{2}\\
&(\textbf{Lovász条件})&2\le{}^\forall k<n,&\delta\lVert \boldsymbol{b}_{k-1}^\star\rVert\le \lVert \pi_{k-1}(\boldsymbol{b}_k)\rVert^2
\end{array}

を満たすときを言います．また，Lovász条件の不等式は

\lVert\boldsymbol{b}_k^\star\rVert\ge (\delta-\mu_{k, k-1}^2)\lVert \boldsymbol{b}_{k-1}^\star\rVert^2

と同値であるので，この不等式の方をLovász条件と呼ぶこともあります．
LLLアルゴリズムでは，サイズ簡約条件を満たさない基底ベクトル$\boldsymbol{b}_k$があったら，$\boldsymbol{b}_k\gets \boldsymbol{b}_k-\lfloor\mu_{k, j}\rceil\boldsymbol{b}_j$をしてサイズ簡約条件を満たすようにして，Lovász条件を満たさない基底ベクトルの組$(\boldsymbol{b}_{k-1}, \boldsymbol{b}_k)$があったら$\boldsymbol{b}_{k-1}$と$\boldsymbol{b}_{k}$を入れ替えるということを繰り返します．
具体的には，以下の流れ図のような形です（Mermaidでやったのですこし見づらいです）．

格子基底をLLL簡約することで何が良いのかと思われる方もいらっしゃるかもわかりませんが，LLL簡約基底では各基底ベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n$のノルムが比較的短くなります（しかもLLLアルゴリズムは多項式回の反復で停止します）．具体的には以下の不等式を満たします．

\begin{array}{ll}
&&\lVert \boldsymbol{b}_1\rVert\le \left(\frac{4}{4\delta-1}\right)^\frac{n-1}{4}\mathrm{vol}(L)^\frac{1}{n}\\
&1\le {}^\forall i\le n, &\lVert \boldsymbol{b}_i\rVert\le\left(\frac{4}{4\delta-1}\right)^\frac{n-1}{2}\lambda_i(L)
\end{array}

しかし，実際にはこの上からの評価よりも短い基底ベクトルになることが多いです．

DeepLLLアルゴリズム

DeepLLL²はLLLの自然な一般化でDeepLLL簡約基底とは次のような基底のことです．

DeepLLL簡約基底

\begin{array}{ll}
&(\textbf{サイズ簡約条件})&1\le{}^\forall j<{}^\forall i\le n,&\lvert\mu_{i, j}\rvert\le \frac{1}{2}\\
&(\textbf{deep-exchange条件})&1\le{}^\forall i<{}^\forall k\le n,&\delta\lVert \boldsymbol{b}_{i}^\star\rVert\le \lVert \pi_{i}(\boldsymbol{b}_k)\rVert^2
\end{array}

を満たすときを言います．deep-exchange条件とLovász条件とを見比べればすぐに分かりますが，LLLでは隣り合う基底ベクトルのみを比較していますが，DeepLLLは必ずしも隣り合わない基底ベクトルについても比較しています．
DeepLLLもLLL同様に，サイズ簡約条件を満たさない基底ベクトル$\boldsymbol{b}_k$があったら，$\boldsymbol{b}_k\gets \boldsymbol{b}_k-\lfloor\mu_{k, j}\rceil\boldsymbol{b}_j$をしてサイズ簡約条件を満たすようにして，deep-exchange条件を満たさないベクトルの組$(\boldsymbol{b}_i, \boldsymbol{b}_k)$については，単に入れ替えるのみではなく，deep-insertionと呼ばれる入れ替えによって基底を更新します．deep-insertionとは

\sigma_{i, k}(\lbrace \boldsymbol{b}_i,\ldots,\boldsymbol{b}_n\rbrace):=\lbrace\ldots,\boldsymbol{b}_{i-1},\boldsymbol{b}_k,\boldsymbol{b}_i,\ldots,\boldsymbol{b}_{k-1},\boldsymbol{b}_{k+1},\ldots\rbrace

という操作です．これも，隣り合うベクトルのswapの自然な一般化になっていることがわかるかと思います．
DeepLLLについても，流れ図でアルゴリズムの概要を示すと以下の様になります．

DeepLLLの場合は，基底ベクトルは以下の不等式を満たす．

\begin{array}{ll}
&&\lVert\boldsymbol{b}_1\rVert\le \left(\frac{4}{4\delta-1}\right)^\frac{n-1}{2n}\left(\frac{4\delta}{4\delta-1}\right)^\frac{(n-1)(n-2)}{4n} \mathrm{vol}(L)^\frac{1}{n}\\
&1\le {}^\forall i\le n,&\lVert\boldsymbol{b}_i\rVert\le \sqrt{\left(\frac{4}{4\delta-1}\right)\left(\frac{4\delta}{4\delta-1}\right)^{(n-2)}}\lambda_i(L)
\end{array}

これにより，大きな次元の場合，DeepLLLはLLLよりも小さい上界を与えることがわかる．
しかし，DeepLLLは停止性は証明されておらず，計算量についてはLLLとは対照的にsuper-exponentialな計算量を持つことが実験的に知られている．

PotLLLアルゴリズム

PotLLL³はDeepLLLを改良し，多項式回の反復で停止するようにしたものです．

PotLLL簡約基底

\begin{array}{ll}
&(\textbf{サイズ簡約条件})&1\le{}^\forall j<{}^\forall i\le n,&\lvert\mu_{i, j}\rvert\le \frac{1}{2}\\
& &1\le{}^\forall i<{}^\forall k\le n,&\delta\cdot \mathrm{Pot}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace)\le\mathrm{Pot}(\sigma_{i, k}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace))
\end{array}

を満たすときを言う．但し，

\mathrm{Pot}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace):=\prod_{i=1}^n \lVert\boldsymbol{b}_i^\star\rVert^{2(n-i+1)}

は基底のpotentialである．
PotLLLは，定義を見ればわかるように，格子基底のpotentialが単調に減少するdeep-insertionのみを実行することにより，多項式回の反復で停止させるアルゴリズムです．純粋なDeepLLLよりは品質が落ちるかもしれませんが，deep-insertionを行う"DeepLLL型"の簡約アルゴリズムです．
流れ図は以下の様になります．

S²LLLアルゴリズム

S²LLL⁴もPotLLL同様，DeepLLLを多項式回の反復で停止させるように改良したアルゴリズムです．
$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$を$n$次元格子$L$の基底とします．このとき，$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が簡約パラメタ$0<\eta\le 1$に対してS²LLL簡約されているとは

\begin{array}{ll}
&(\textbf{サイズ簡約条件})&1\le{}^\forall j<{}^\forall i\le n,&\lvert\mu_{i, j}\rvert\le \frac{1}{2}\\
& &1\le{}^\forall i<{}^\forall k\le n,&\eta\cdot \mathrm{SS}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace)\le\mathrm{SS}(\sigma_{i, k}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace))
\end{array}