LLL系の基底簡約についてまとめてみた
- 本記事は Qiita から移植してきたものになります．
- 間違えなどにお気づきの方が居ればご指摘ください．
- 他のアルゴリズムも随時追加していきます．
最初に
みなさん．格子暗号というものをご存じでしょうか．知っている人もいれば知らない人もいるかと思います（当たり前）．
この格子暗号というものは，いわゆる耐量子計算機暗号の一つです．簡単に言えば，量子計算機を使っても簡単には解けない暗号の一つで，格子という数学の道具を使っているものです．$\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）が量子計算機でも求解困難であることによりその安全性が保障される暗号です．
$n$次元格子$L$が与えられたとき，$\lVert\boldsymbol{v}\rVert$が最小となるような非零なベクトル$\boldsymbol{v}\in L\setminus\lbrace \boldsymbol{0}_n\rbrace$を見つけよ．
簡単に言えば，一番短い$L$の元を見つけてね，という問題です．
$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簡約基底とは次のようなものです．
$\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}$を入れ替えるということを繰り返します．
具体的には，以下の流れ図のような形です．
LLLの流れ図
格子基底を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簡約基底とは次のような基底のことです．
$\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$に対して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の流れ図
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を改良し，多項式回の反復で停止するようにしたものです．
$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$を$n$次元格子$L$の基底とします．このとき，格子基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$のpotentialとは
$$
\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)}
$$
と定義される量である．
$\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$に対して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}
$$
を満たすときを言う．
PotLLLは，定義を見ればわかるように，格子基底のpotentialが単調に減少するdeep-insertionのみを実行することにより，多項式回の反復で停止させるアルゴリズムです．純粋なDeepLLLよりは品質が落ちるかもしれませんが，deep-insertionを行う"DeepLLL型"の簡約アルゴリズムです．
流れ図は以下の様になります．
PotLLLの流れ図
また，PotLLL簡約基底については，基底ベクトルのノルムについての上界は知られていませんが，次のことがわかっています．
$n$次元格子の基底$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$は簡約パラメタ$\delta$に関してPotLLL簡約されているとする．このとき，$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$は$\delta$に関してLLL簡約もされている．
任意の$4^{-\frac{1}{n-1}}\le \delta < 1$に対して，$n$次元格子の基底$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$が簡約パラメタ$\delta$に関してDeepLLL簡約されているとすると，$\{\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\}$は$\delta^{n-1}$に関してPotLLL簡約もされている．
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$のGram-Schmditの直交化ベクトルの二乗和（squared-sum of Gram-Schmdit lengths）とは
$$
\mathrm{SS}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace):=\sum_{i=1}^n\lVert \boldsymbol{b}_i^\star\rVert^2
$$
で定義される量です．
$\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}
$$
を満たすときを言う．
S²LLLは，格子基底のGram-Schmditの直交化ベクトルの二乗和を単調に減少するdeep-insertionのみを行うことで多項式回の反復で停止させています．S²LLLの流れ図は以下の様になります．但し，簡単のために
$$
S_{i, k}:=\mathrm{SS}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace)-\sigma_{i, k}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace)
$$
とします．
S²LLLの流れ図
