LLL Algorithm

Lattice Reduction

lattice reduction의 목적은 임의의 lattice basis를 같은 lattice를 표현하는 더 짧고, 수직에 가까운 basis들로 구성하는 것이다. 따라서 short vectors를 찾기 때문에 shortest vector problem(SVP)의 근사 해를 낸다.

이전에 살펴본 정리를 보면 $\vert \det(U) \vert = 1$인 integer matrix $U$에 대해 $B=UB^{\prime}$이며 이는 $B$와 $B^{\prime}$가 같은 lattice를 represent하는 것이라 했다. 이를 통해 같은 lattice를 represent하면서 basis에 transformations(vector-switching, vector-addition)을 하는 것이 가능하다.

matrix $T_{i,j}$를 basis의 왼쪽에 행렬곱하면 $i$번째 basis와 $j$번째 basis를 swap할 수 있다(vector-switching). matrix $L_{i,j}(k)$를 basis의 왼쪽에 행렬곱하면 $i$번째 basis에 $j$번째 basis를 k번 더한 것과 같다(vector-addition). 중요한 점은 두 행렬 모두 determinants가 $\pm 1$이라는 것이다. 즉 이 두 행렬을 이용해 basis에 transformation을 해도 같은 lattice를 represent하고, 이 transformation은 LLL algorithm에서 중요한 역할을 한다.

LLL Algorithm

Orthogonality

SVP를 푸는 가장 직관적인 답은 기저의 수직성(Orthogonality)를 생각하는 것이다. 왜냐하면, 다음이 성립하기 때문이다.

basis $B$가 orthogonal하고, $\lambda_1 = \sum a_ib_i$라고 하자. 이 때 일반성을 잃지 않고 $a_i \neq 0$이라고 하자. (즉, coefficient가 nonzero인 기저만 생각하자).

\[\begin{aligned} \lVert \lambda_1 \rVert^2 &= \lVert a_1b_1 + ⋯ + a_kb_k \rVert^2 \\ &=a_1^2 \lVert b_1 \rVert^2 + ⋯ + a_k^2 \lVert b_k \rVert^2 \\ &\geq a_i^2 \min \lVert b_i \rVert^2 \\ &\geq \min \lVert b_i \rVert^2 \end{aligned}\]

2번째 줄을 보면, basis가 orthogonal하기 때문에 벡터의 길이(norm) 계산이 독립적으로 분리된다. 이를 통해 기저가 orthogonal하면 SVP문제를 풀 수 있음을 확인할 수 있다.

그렇다면, Lattice를 orthogonal하게 만들기 전에 일반적인 vector 공간에서 수직인 기저를 아주 효율적으로 찾는 방법인 Gram-Schmidt Orthogonalization부터 살펴보자.

Definition. (Gram-Schmidt Orthogonalization.) Given a basis $B$ for vector space $V$, an orthogonal basis $B^* $ can be obtained through the following process.

\[b_i^* = b_i - \sum_{j=1}^{i-1} \mu_{i,j}b_j^*\]

하지만 Gram-Schmidt Orthogonalization를 lattice problem에 그대로 적용할 수가 없는데, 이유는 격자의 특성상 정수 계수의 선형 결합만을 허용하지만 Gram-Schmidt 계수인 $\mu_ {i,j} = \frac{⟨b_ i, b_ j^* ⟩}{\lVert b_ j^* \rVert^2}$가 실수이기 때문이다. 따라서 Gram-Schmidt 결과인 $b_ i^*$는 일반적으로 integer vector가 아니고, 격자 벡터도 아니므로 이런 직교 기저는 격자 위에 존재할 수 없다.

이 때문에 SVP문제를 해결하기 위해 환원 알고리즘인 LLL을 사용하여 정수 조건을 유지한 채로 최대한 orthogonal에 근사한 기저를 찾는다. 이 과정에서 Gram-Schmidt를 이용하되, 직교한 실수 기저는 이후에 언급할 조건 비교로만 사용하고 실제 격자 기저는 정수 조건을 만족하도록 조정한다.

LLL Reduction

Definition. ($\delta$-LLL Reduced Basis) Consider a basis $B$ of $\mathcal{L}$ and its Gram-Schmidt basis $B^* $. ($B^* ⊂ ℝ^n$.) If $B$ and $B^*$ satisfy the following conditions, then $B$ is called an $\delta$-LLL Reduced Basis of \(\mathcal{L}\).

1. (Size Reduced.) $\vert \mu_{i,j} \vert = \left\lvert \frac{\langle b_i, b_j^* \rangle}{\lVert b_j^* \rVert^2} \right\rvert \leq \frac{1}{2}$
2. (Lovász condition.) $\lVert b_{i+1}^* + \mu_{i+1, i}b_i^* \rVert^2 \geq \delta\lVert b_i^*\rVert^2　\delta \in \left(\frac{1}{4},1\right)$

Size Condition부터 살펴보면 $b_ i$를 직교기저 $b_ j^* $에 투영한 Gram-Schmidt 계수 $\mu_ {i,j}$는 $b_ j^*$와 $b_ i$ 사이의 각을 측정한다. 만약 $μ$가 1에 가까워 지면 각은 작아지고, $μ$가 0에 가까워 지면 각이 커지며 orthogonal에 근접한다. 따라서 Size Condition은 LLL-Reduced Basis가 orthogonal에 근사하도록 하는 조건임을 알 수 있다.

이제 Lovász condition을 살펴보자. 간혹 논문에서 $(\delta - \mu_{i+1, i}^2) \lVert b_i^* \rVert^2 \leq \lVert b_{i+1}^* \rVert^2$ 로 표현되기도 하는데, 위 Lovász condition 형태를 전개하면 동일한 식임을 알 수 있다.

우린 LLL Algorithm을 통해 최단 벡터를 찾는 것이 목적이기 때문에, 앞쪽 벡터가 짧아야 전체 격자에서 더 빠르게 최단 벡터를 찾을 수 있다. 따라서 우리가 원하는 벡터 정렬 순서는 다음과 같다.

\[\lVert b_i \rVert \leq \lVert b_{i+1} \rVert\]

하지만 모든 $i$에 대해 위 조건을 만족하려면 알고리즘을 다항시간 내에 끝낼 수 없다. 또한 앞서 Size Condition을 보면 만약 $b_j^*$가 $b_i$에 비해 충분히 길면 각도와 상관없이 조건을 만족할 수도 있다. Lovasz Condition은 이 두 가지를 고려하며, $\delta$는 주로 $\frac{3}{4}$를 쓴다.

\[\begin{aligned} \lVert b_{i+1}^* + \mu_{i+1, i}b_i^*\rVert^2 &= \lVert b_{i+1}^*\rVert^2 + \mu_{i+1, i}^2 \lVert b_i^*\rVert^2 \\ \lVert b_{i+1}^*\rVert^2 + \mu_{i+1, i}^2 \lVert b_i^*\rVert^2 &\geq \frac{3}{4} \lVert b_i^*\rVert^2 \\ \lVert b_{i+1}^*\rVert^2 &\geq \left( \frac{3}{4} - μ_{i+1, i}^2 \right)\lVert b_i^*\rVert^2 \\ &\geq \frac{1}{2}\lVert b_i^*\rVert^2 \end{aligned}\]

Lovász condition의 $b_{i+1}^* $는 Size Condition의 $b_i$에, $b_i^* $는 $b_j$에 대응된다고 생각할 수 있다. 결국 $\lVert b_ {i+1}^* \rVert^2 \geq \frac{1}{2}\lVert b_ i^* \rVert^2$ 조건을 통해 $b_{i+1}^* $의 길이가 $b_i^* $의 길이보다 아주 짧을 수는 없게 하여 Size Condition문제를 해결하고, 앞서 보았던 $\lVert b_i \rVert \leq \lVert b_{i+1} \rVert$ 벡터 정렬 순서를 조금 완화하여 벡터들의 순서를 어느정도 강제하면서 다항시간 $O(d^5n \log^3 B)$안에 해결될 수 있도록 한다.

위 관계를 통해 $\delta > \frac{1}{4}$이어야 함을 알 수 있고, 만약 $\delta=1$이 되면 최종적으로 $\lVert b_ {i+1}^* \rVert^2 \geq \frac{3}{4}\lVert b_ i^* \rVert^2$ 가 되어 벡터 정렬 순서를 조금 더 강제한다.

이렇게 구한 LLL-Reduced Basis는 기존 기저 벡터들에 대해 정수 계수로만 변형을 가해 원래 basis와 같은 Span 즉, 같은 Lattice를 생성한다.

LLL이 다항시간 안에 종료됨의 증명은 Polynomial time proof를 참고하자.

LLL Algorithm

LLL reduction의 조건에 따라 LLL Algorithm은 다음과 같이 동작한다.

Algorithm LLL Algorithm
 function LLL(Basis $\lbrace b_1, \cdots, b_n\rbrace, \delta$)
  while true do
   for $i=2$ to $n$ do (size-reduction)
    for $j=i-1$ to 1 do
      $b_ i^* , \mu_ {i,j} \ \gets$ Gram-Schmidt $(b_ 1, \cdots, b_ n)$
      $b_ i \gets b_ i - \lfloor \mu_ {i,j} \rceil b_ j$
   if $\exists i$ such that $\lVert b_{i+1}^* + \mu_{i+1, i}b_i^* \rVert^2 < \delta\lVert b_i^* \rVert^2$ then Swap $b_i$ and $b_{i+1}$  (Lovász condition)
   else
    return $\lbrace b_1, \cdots, b_n\rbrace$

Gram-Schmidt Orthogonalization에서 $\mu_ {i,j}$가 보통 실수 이므로 가장 가까운 정수로의 round인 $\lfloor \mu_ {i,j} \rceil$를 사용한다. 이렇게 하면 결과로 나온 vector $b_i$와 Gram-Schmidt basis $b_j^* $의 $\mu$는 항상 size-reduction 조건을 만족하게 되는데 이유는 다음과 같다.

$b_ i^{\prime} \gets b_ i - \lfloor \mu_ {i,j} \rceil b_ j$ 에서 결과로 나온 $b_ i^{\prime}$과 $b_j^* $의 $\mu_{i,j}^{\prime}$는 다음과 같이 계산된다.

\[\mu_{i,j}^{\prime} = \frac{\langle b_i^{\prime}, b_j^* \rangle}{\lVert b_j^* \rVert^2} = \frac{\langle b_ i - \lfloor \mu_ {i,j} \rceil b_ j, b_j^* \rangle}{\lVert b_j^* \rVert^2} = \frac{\langle b_i, b_j^* \rangle - \lfloor \mu_ {i,j} \rceil \langle b_j, b_j^* \rangle}{\lVert b_j^* \rVert^2}\]

여기서 $b_j^* $는 Gram-Schmidt basis이므로 $\langle b_j, b_j^* \rangle = \lVert b_j^* \rVert^2$ 이다. 따라서 최종적으로 $\mu_{i,j}^{\prime} = \frac{\langle b_i, b_j^* \rangle}{\lVert b_j^* \rVert^2} - \lfloor \mu_ {i,j} \rceil = \mu_{i,j} - \lfloor \mu_ {i,j} \rceil$ 가 된다.

결국 $\mu_{i,j}$는 실수이고, $\lfloor \mu_ {i,j} \rceil$는 $\mu_{i,j}$와 가장 가까운 정수이므로, $\vert \mu_{i,j}^{\prime} \vert = \vert \mu_{i,j} - \lfloor \mu_ {i,j} \rceil \vert \leq \frac{1}{2}$ 가 되어 size-reduction 조건을 항상 만족한다.

Gram-Schmidt가 끝난 뒤에는 모든 $i$에 대해 Lovász condition을 확인하여 조건을 만족하지 않으면 swap한다.

LLL reduction의 조건들을 통해서도 알 수 있듯이 LLL이 항상 최단 vector를 찾아주는건 아니지만, shortest vector에 근사한 vector을 찾을 수 있음을 보일 수는 있다. 이를 보이기 전에 먼저 shortest vector의 lower bound에 대한 정리와 증명은 다음과 같다.

Theorem. Let $B=\lbrace b_1, \cdots, b_n \rbrace$ be a lattice basis and $B^* = {b_1^* , \cdots, b_n^* }$ its corresponding GramSchmidt orthogonalisation. Then $\lambda_1(\mathcal{L}(B)) \geq \min_{i \in \lbrace 1, \cdots, n\rbrace} \lVert b_i^* \rVert$.

$Proof$. Let $x=(x_1, \cdots, x_n) \in \mathbb{Z}^n$ be a non-zero vector. We consider the lattice point $\mathbf{xB}$ and show that its length is bounded below by $\min_{i \in \lbrace 1, \cdots, n\rbrace} \lVert b_i^* \rVert$. Let $j$ be the largest index such that $x_j \neq 0$. Then

\[\begin{align} \vert \langle \mathbf{xB}, b_j^* \rangle \vert &= \vert \langle \sum_{i=1}^n x_i b_i, b_j^* \rangle \vert \\ &= \vert \sum_{i=1}^n x_i \langle b_i, b_j^* \rangle \vert　　\text{by linearity of the inner product} \\ &= \vert x_j \vert \langle b_j, b_j^* \rangle　　\text{since } b_i \text{ and } b_j^* \text{ are orthogonal for } i<j \text{ and } x_i=0 \text{ for } j<i \\ &= \vert x_j \vert \cdot \lVert b_j^* \rVert^2 \\ \end{align}\]

From the Cauchy-Schwartz inequality, we have $\vert \langle \mathbf{xB}, b_j^* \rangle \vert \leq \lVert \mathbf{xB} \rVert \cdot \lVert b_j^* \rVert$ so

\[\begin{align} \vert x_j \vert \cdot \lVert b_j^* \rVert^2 &\leq \lVert \mathbf{xB} \rVert \cdot \lVert b_j^* \rVert \\ \vert x_j \vert \cdot \lVert b_j^* \rVert &\leq \lVert \mathbf{xB} \rVert \\ \lVert b_j^* \rVert &\leq \lVert \mathbf{xB} \rVert　　\text{since } x_j \neq 0 \text{ is an integer} \\ \min_{i \in \lbrace 1, \cdots, n\rbrace} \lVert b_i^* \rVert &\leq \lVert \mathbf{xB} \rVert \end{align}\]

3번째 줄을 좀 더 설명하면 Gram-Schmidt Orthogonalization $b_i^* = b_i - \sum \mu_{i,j}b_j^* $ 에서 직교 기저 $b_j^* $를 구할 때 이전의 모든 직교 기저 $b_i^* \ (i<j)$의 방향을 제거하기 때문에, 기존 basis $b_i$에 대해서도 모두 직교하게 된다.

결국 $\mathbf{xB}$는 non-zero인 임의의 lattice point이므로 first successive minimum에 대해서도 $\lambda_1(\mathcal{L}(B)) \geq \lVert b_j^* \rVert \to \lambda_1(\mathcal{L}(B)) \geq \min_{i \in \lbrace 1, \cdots, n\rbrace} \lVert b_i^* \rVert$ 가 성립함을 알 수 있다.

Proposition. Let $B = \lbrace b_1, \cdots, b_n \rbrace$ be a $\delta$-LLL reduced basis. Then $\lVert b_1 \rVert \leq \left( \frac{2}{\sqrt{4\delta -1}} \right)^{n-1} \lambda_1$.

$Proof$. From the Lovász condition, we have

\[(\delta - \mu_{i+1, i}^2) \lVert b_i^* \rVert^2 \leq \lVert b_{i+1}^* \rVert^2\]

and from the size-reduced condition, we have $\vert \mu_{i+1, i} \vert \leq \frac{1}{2}$, so

\[\left( \frac{4 \delta -1}{4} \right) \lVert b_i^* \rVert^2 \leq \lVert b_{i+1}^* \rVert^2\]

By chaining the inequalities, we get

\[\begin{align} \lVert b_i^* \rVert^2 =& \lVert b_1 \rVert^2 \leq \left( \frac{4}{4 \delta -1} \right)^{i-1} \lVert b_i^* \rVert^2 \\ &\lVert b_1 \rVert \leq \left( \frac{2}{\sqrt{4 \delta -1}} \right)^{i-1} \lVert b_i^* \rVert \\ &\lVert b_1 \rVert \leq \left( \frac{2}{\sqrt{4 \delta -1}} \right)^{n-1} \lVert b_n^* \rVert \end{align}\]

최종적으로 앞서 Theorem의 $\lVert b_j^* \rVert \leq \lVert \mathbf{xB} \rVert$ 와 이전에 살펴보았던 Minkowski’s First Theorem $\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot \vert \det(\mathcal{L}) \vert^{1/n}$를 위 Proposition의 결과에 적용하여 다음의 결과를 얻는다.

\[\lVert b_1 \rVert \leq \left( \frac{2}{\sqrt{4 \delta -1}} \right)^{n-1} \sqrt{n} \cdot \vert \det(\mathcal{L}) \vert^{1/n}\]

Reference

1. https://eprint.iacr.org/2023/032.pdf
2. https://blog.sp301415.com/solving-integer-problems-using-lll/
3. https://cryptohack.gitbook.io/cryptobook/lattices/definitions
4. https://crypto.stackexchange.com/questions/39532/why-is-the-lov%C3%A1sz-condition-used-in-the-lll-algorithm