格子基底簡約を可視化してみた

# 格子ってなんぞや

## 格子の定義

格子暗号とか格子基底簡約とか聞くけど実際なんなんという人のために，とりあえず定義だけでも書いておく（詳細は[[YA19](#ya19-青野良範-and-安田雅哉-格子暗号解読のための数学的基礎格子基底簡約アルゴリズム入門-2019-近代科学社)]を参照のこと）．**$n$次元格子**$L\subseteq \mathbb{R}^m$とは，$n$個の一次独立なベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\in\mathbb{R}^m$の整数係数の一次結合全体

```math
L=\mathcal{L}(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n)=\left\{\left.\sum_{i=1}^n x_i\boldsymbol{b}_i~\right|~ x_1,\ldots,x_n\in\mathbb{Z}\right\}
```

である．このとき，$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$を格子$L$の**基底**，基底を並べて作った行列$\boldsymbol{B}\in\mathbb{R}^{n\times m}$を**基底行列**と呼ぶ．特に$n=m$のとき，**完全階数**と呼び，ここでは特に断りのない限り完全階数格子についてのみ述べる．

## Gram-Schmidtの直交化（GSO）

線形代数を勉強したことがあるならば知っていると思うが，Gram-Schmidtの直交化ベクトルを紹介しておく．

```math
\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 \le n)
\end{aligned}
\right. 
```

で定まるベクトル$\boldsymbol{b_1}^\star,\ldots,\boldsymbol{b_n}^\star$を**Gram-Schmidtの直交化ベクトル（GSOベクトル）**，$\mu_{i, j}$を Gram-Schmidtの直交化係数（GSO係数）と呼ぶ．


## 双対格子

「双対」という言葉は数学をやっていると色々なところで出てくるが，格子にも双対はある．基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$で生成される格子$L=\mathcal{L}(\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n)$の**双対格子**は

```math
\widehat{L}=\lbrace\boldsymbol{x}\in\mathbb{R}^n\,\left|\, {}^\forall\boldsymbol{y}\in L,\ \langle\boldsymbol{x}, \boldsymbol{y}\rangle\in \mathbb{Z}\right.\rbrace
```

で定義される．実はもっと簡単に双対格子の基底行列は$\boldsymbol{D}=(\boldsymbol{B}^\top)^{-1}$で与えられることが知られている．

# 幾何級数仮定（GSA）

非常に簡単に言えば，良い基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$に対して，どうやら$\log \lVert \boldsymbol{b}_1^\star\rVert, \ldots, \log \lVert \boldsymbol{b}_n^\star\rVert$がある直線上にのってそうだから，これを仮定しようというやつ．この直線のことなんかを**GSAスロープ**や**GSA**と呼ぶこともある．厳密な定義などは[[Sch03](#sch03-claus-peter-schnorr-lattice-reduction-by-random-sampling-and-birthday-methods-in-symposium-on-theoretical-aspects-of-computer-science-stacs-2003-volume-2607-of-lecture-notes-in-computer-science-pages-145156-springer-2003)]を参照のこと．

# 格子基底簡約ってなんぞや

## 格子基底簡約とは

格子$L$について，その基底は無数に存在する．そのうち，各基底ベクトルが短く，且つ直交に近いときにその基底は**良い基底**であるという．逆に各基底ベクトルがめっちゃながくてめっちゃ平行に近いとき**悪い基底**であるという．**格子基底簡約**とは，悪い基底を良い基底に変換しようねというものである．
ここでは，幾つか基底簡約の例を載せる．

## LLL基底簡約

$n$次元格子の基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が$\delta$**-LLL簡約されている**[[LLL82](#lll82--arjen-klaas-lenstra-hendrik-willem-lenstra-and-lászló-lovász-factoring-polynomials-with-rational-coefficients-mathematische-annalen-2614515534-1982)]とは，

```math
\begin{aligned}
\textbf{サイズ簡約条件}~&1\le{}^\forall j<{}^\forall i\le n,~ |\mu_{i, j}|\le\frac{1}{2}\\
\textbf{Lovász条件}~&2\le {}^\forall k\le n,~\delta\cdot \|\boldsymbol{b}_{k-1}^\star\|^2\le\|\pi_{k-1}(\boldsymbol{b}_k)\|^2
\end{aligned}
```

を満足するときを言う．

## DeepLLL基底簡約

$n$次元格子の基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が$\delta$**-DeepLLL簡約されている**[[SE94](#se94-claus-peter-schnorr-and-martin-euchner-lattice-basis-reduction-improved-practical-algorithms-and-solving-subset-sum-problems-mathematical-programming-66181199-1994)]とは，

```math
\begin{aligned}
\textbf{サイズ簡約条件}~&1\le{}^\forall j<{}^\forall i\le n,~ |\mu_{i, j}|\le\frac{1}{2}\\
\textbf{deep-exchange条件}~&1\le {}^\forall i< {}^\forall k\le n,~\delta\cdot \|\boldsymbol{b}_i^\star\|^2\le\|\pi_i(\boldsymbol{b}_k)\|^2
\end{aligned}
```

を満足するときを言う．

## PotLLL基底簡約

$n$次元格子の基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が$\delta$**-PotLLL簡約されている**[[FSW14](#fsw14-felix-fontein-michael-schneider-and-urs-wagner-potlll-a-polynomial-time-version-of-lll-with-deep-insertions-designs-codes-and-cryptography-73355368-2014)]とは，

```math
\begin{aligned}
\textbf{サイズ簡約条件}~&1\le{}^\forall j<{}^\forall i\le n,~ |\mu_{i, j}|\le\frac{1}{2}\\
\textbf{deep-exchange条件}~&1\le{}^\forall k<{}^\forall \ell\le n,~\delta\cdot \text{Pot}(\boldsymbol{B})\le\text{Pot}(\sigma_{k, \ell}(\boldsymbol{B}))
\end{aligned}
```

を満足するときを言う．但し，$\mathrm{Pot}(\boldsymbol{B}):=\prod_{i=1}^n \lVert\boldsymbol{b}_i^\star\rVert^{2(n-i+1)}$は格子基底の**ポテンシャル量**であり．$\sigma\_{k, \ell}(\boldsymbol{B})=\sigma\_{k, \ell}(\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace)=\lbrace\ldots, \boldsymbol{b}\_{k - 1}, \boldsymbol{b}\_\ell, \boldsymbol{b}\_{k}, \ldots, \boldsymbol{b}\_{\ell-1}, \boldsymbol{b}\_{\ell+1}\ldots\rbrace$は，**deep-insertion**である．

## 双対型LLL基底簡約

$n$次元格子の基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が$\delta$**-双対型LLL簡約されている**とは，$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$の双対基底が$\delta$-LLL簡約基底であるときを言う．

## GSAスロープの動画

以下にGSAスロープの動画をはっつける．とは言っても，現時点ではQiitaに動画をはっつけられないらしいので$\texttt{gif}$で貼り付けることにする．
動画のやつは[私のHP](https://satoshin-des.github.io/index.html)の方に乗せてあるので，$\texttt{mp4}$形式で見たいという方は私のHPから見てみてね．

https://satoshin-des.github.io/math.html

また，以下にLLLの動画を生成する際に使用した$\texttt{Python}$のソースコードを置いておく．

```python
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as amt

def Gram_Schmidt_squared(b):
    n, m = b.shape
    GSOb = np.zeros((n, m))
    mu = np.identity(n)
    B = np.zeros(n)

    for i in range(n):
        GSOb[i] = b[i].copy()
        for j in range(i):
            mu[i, j] = np.dot(b[i], GSOb[j]) / np.dot(GSOb[j], GSOb[j])
            GSOb[i] -= mu[i, j] * GSOb[j].copy()
        B[i] = np.dot(GSOb[i], GSOb[i])
    return B, mu


def LLLReduce(b, d = 0.99):
    n = b.shape[0]
    B, mu = Gram_Schmidt_squared(b)
    k = 1
    
    fig = plt.figure()
    ax = fig.add_subplot(111)
    images = []

    while k < n:
        im = ax.bar(np.arange(len(B)) + 1, np.sqrt(B), color='blue')
        plt.yscale('log')
        images.append(im)
        
        for j in range(k)[::-1]:
            if abs(mu[k, j]) > 0.5:
                q = round(mu[k, j])
                b[k] -= q * b[j].copy()
                mu[k][: j + 1] -= q * mu[j][: j + 1].copy()

        if B[k] < (d - mu[k, k - 1] * mu[k, k - 1]) * B[k - 1] and k > 0:
            b[k], b[k - 1] = b[k - 1], b[k].copy()

            #Update GSO-information
            nu = mu[k, k - 1]
            c = B[k] + nu * nu * B[k - 1]; c_inv = 1. / c
            mu[k, k - 1] = nu * B[k - 1] * c_inv
            B[k] *= B[k - 1] * c_inv
            B[k - 1] = c
            t = mu[k - 1, : k - 1].copy()
            mu[k - 1, : k - 1] = mu[k, : k - 1]
            mu[k, : k - 1] = t.copy()
            t = mu[k + 1 :, k].copy()
            mu[k + 1 :, k] = mu[k + 1 :, k - 1] - nu * t.copy()
            mu[k + 1 :, k - 1] = t.copy() + mu[k, k - 1] * mu[k + 1 :, k]
            k -= 1
        else: k += 1
    im = ax.bar(np.arange(len(B)) + 1, np.sqrt(B), color='blue')
    plt.yscale('log')
    images.append(im)
    print("start")
    anime = amt.ArtistAnimation(fig, images, interval=100)
    anime.save("LLL.mp4", writer="ffmpeg")
    return b
```

## LLLの場合

![LLL.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3734379/2d5d4f36-fe35-7e66-03ec-aca94fda2749.gif)


## DeepLLLの場合

![DeepLLL_1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3734379/ad706a3f-72cd-6986-e15d-5249a95a263f.gif)


:::note warn
DeepLLLは，他のと同じ基底の取り方をするととても長い動画になってしまうため，都合上異なる基底の取り方をしている．
:::


## PotLLLの場合

![PotLLL.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3734379/84c1fe87-4e09-949b-2b98-dcfeafc46fe6.gif)


## 双対型LLLの場合

![DualLLL.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3734379/6e8b1780-0e6a-8d62-2e49-aebb539530fe.gif)


# 参考文献

###### [YA19] 青野良範 and 安田雅哉. 格子暗号解読のための数学的基礎：格子基底簡約アルゴリズム入門, 2019. 近代科学社.
###### [LLL82]  Arjen Klaas Lenstra, Hendrik Willem Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4):515–534, 1982.
###### [SE94] Claus-Peter Schnorr and Martin Euchner. Lattice basis reduction: Improved practical algorithms and solving subset sum problems. Mathematical programming, 66:181–199, 1994.
###### [Sch03] Claus Peter Schnorr. Lattice reduction by random sampling and birthday methods. In Symposium on Theoretical Aspects of Computer Science (STACS 2003), volume 2607 of Lecture Notes in Computer Science, pages 145–156. Springer, 2003.
###### [FSW14] Felix Fontein, Michael Schneider, and Urs Wagner. PotLLL: A polynomial time version of LLL with deep insertions. Designs, Codes and Cryptography, 73:355–368, 2014.