格子ってなんぞや

格子の定義

格子暗号とか格子基底簡約とか聞くけど実際なんなんという人のために，とりあえず定義だけでも書いておく（詳細は[YA19]を参照のこと）．$n$次元格子$L\subseteq \mathbb{R}^m$とは，$n$個の一次独立なベクトル$\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\in\mathbb{R}^m$の整数係数の一次結合全体

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の直交化ベクトルを紹介しておく．

\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)$の双対格子は

\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]を参照のこと．

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

格子基底簡約とは

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

LLL基底簡約

$n$次元格子の基底$\lbrace\boldsymbol{b}_1,\ldots,\boldsymbol{b}_n\rbrace$が$\delta$-LLL簡約されている[LLL82]とは，

\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]とは，

\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]とは，

\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の方に乗せてあるので，$\texttt{mp4}$形式で見たいという方は私のHPから見てみてね．

また，以下にLLLの動画を生成する際に使用した$\texttt{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の場合

DeepLLLの場合

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

PotLLLの場合

双対型LLLの場合

参考文献

[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.