Lenstra-Lenstra-Lovász(LLL) algorithm

Given a basis $\{v_1,\dots ,v_n\}$ of a lattice, we observed that the basis is good if it is "nearly orthogonal". So, we may make the given basis into a mutually orthogonal basis $\{v_1^{\ast },\dots ,v_n^{\ast }\}$ using the Gram-Schmidt process. However, the GS process contains divisions so the result $\{v_i^{\ast }\}$ does not generate the same lattice. So, we need more processes called the Lenstra-Lenstra-Lovász(LLL) algorithm.

LLL-reduced Condition

We first define the notion of "nearly orthogonal". Given a basis $\{v_i\}$, after the GS process we have orthogonal $\{v_i^{\ast }\}$ and let ${\mu }_{i,j}=\frac{v_i\cdot v_j^{\ast }}{v_j^{\ast }\cdot v_j^{\ast }}$ for all $j<i$. ${\mu }_{i,j}$ are the entries of the upper triangular matrix in the QR decomposition.

The basis $\{v_i\}$ is called to satisfy the Size Condition, if

$${\mu }_{i,j}\le \frac{1}{2}$$

for all $j<i$. If $v_i$ were orthogonal, then ${\mu }_{i,j}=0$ for all $j<i$. So, the size condition roughly says that the new $v_i$ does not contain too much information(length of vectors) from $v_j$.

Next, the basis $\{v_i\}$ is called to satisfy the Lovász Condition, if

$$\frac{3}{4}\Vert v_i^{\ast }{\Vert }^2\le \Vert v_{i+1}^{\ast }{\Vert }^2+{\mu }_{i+1,i}^2\Vert v_i^{\ast }{\Vert }^2$$

for all $i$. Note that $v_i^{\ast }$ and $v_{i+1}^{\ast }+{\mu }_{i+1,i}{v}_i^{\ast }$ are respectively projections of $v_i$ and $v_{i+1}$ onto $\mathrm{Span}\{v_1,\dots ,v_{i-1}{\}}^{\perp }$. I mentioned that ${\mu }_{i,j}$ measures the information contained in $v_i$ associated with $v_j$. To achieve orthogonal property, every $v_i$ should contain enough information not associated with others. The size condition says that $v_i$ does not contain too much information from $v_j$. But this is not enough if $v_i$ is too small so that $v_i$ satisfies the size condition but does not contain its own information enough. The Lovász condition assures that the $v_i$ contains at least $\frac{3}{4}$ new information. A basis $\{v_i\}$ is called LLL-reduced if it satisfies both the size condition and Lovász condition.

LLL algorithm

If the size condition does not hold for some $j<i$, we may replace $v_i$ into $v_i-a{v}_j$ for some $a\in \mathbb{Z}$, then

$$\frac{|(v_i-a{v}_j)\cdot v_j^{\ast }|}{\Vert v_j{\Vert }^2}=\frac{|v_i\cdot v_j^{\ast }|}{\Vert v_j{\Vert }^2}-a$$ since GS process garuantees $v_j\cdot v_j^{\ast }=v_j^{\ast }\cdot v_j^{\ast }$. The appropriate $a$ is the closest integer to ${\mu }_{i,j}$. So we can make any basis to satisfy the size condition. The LLL algorithm is a repetition of size reduction and vector swap. After the size reduction for each $j<i$, we check the Lovász condition. If the Lovász condition does not hold for $i$, we swap $v_i$ and $v_{i+1}$ then implement size reduction again. One can show that this procedure terminates in a finite step, precisely $O(n^2(\log n+\log max\Vert v_i\Vert ))$. In terms of basic operation, the algorithm needs $O(n^6{\log }^{3}max\Vert v_i\Vert )$ operations. I refer to Wikipedia for the detailed algorithm.

If an LLL-reduced basis can be obtained easily, the private key of a lattice-based cryptosystem can be revealed. For the security of the cryptosystem, $n$ should be large enough so that the LLL algorithm can not work.

Babai's closest plane algorithm

In the previous post, we've seen Babai's rounding-off algorithm. With an LLL-reduced basis, the rounding-off algorithm can solve $\kappa$-CVP for

$$\kappa =1+2n{\left(\frac{9}{2}\right)}^{\frac{n}{2}}.$$

For a better result (smaller $\kappa$), we introduce Babai's closest plane algorithm. Unlike the rounding-off algorithm, this uses GS basis. Given a basis $\{v_i\}$, let $\{v_i^{\ast }\}$ be the GS basis (their entries can be represented in $\mathbb{Q}$). Here is the algorithm explained in Mathematics of Public Key Cryptography by Steven Galbraith

With an LLL-reduced basis, Babai's closest plane algorithm can solve $2^{n/2}$-CVP$ which is a lot better than the rounding-off algorithm.