Given a basis $\{v_1, \ldots, 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^*, \ldots, v_n^*\}$ using the Gram-Schmidt process. However, the GS process contains divisions so the result $\{v_i^*\}$ 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^*\}$ and let $\mu_{i,j} = \frac{v_i \cdot v_j^*}{v_j^* \cdot v_j^*}$ 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} \leq \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} \| v_i^*\|^2 \leq \|v_{i+1}^*\|^2 + \mu_{i+1, i}^2 \| v_i^*\|^2$$
for all $i$. Note that $v_i^*$ and $v_{i+1}^* + \mu_{i+1, i}v_i^*$ are respectively projections of $v_i$ and $v_{i+1}$ onto $\mathrm{Span} \{ v_1, \ldots, 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^* |}{ \| v_j \|^2} = \frac{| v_i \cdot v_j^* |}{ \| v_j \|^2} -a $$ since GS process garuantees $v_j \cdot v_j^* = v_j^* \cdot v_j^*$. 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 \|v_i \|))$. In terms of basic operation, the algorithm needs $O(n^6 \log^3 \max \|v_i \|)$ 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^*\}$ 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.
댓글
댓글 쓰기