Skip to content

Lattice Basis Reduction Algorithms

Lenstra–Lenstra–Lovasz

Basic Introduction

The LLL algorithm finds a basis on a lattice that satisfies the following properties:

image-20180717213241784

Moreover, the basis generated by this method has the following very useful properties:

image-20180717213519622

Simple Application

Here I'll give the second example from the LLL paper. Given n real numbers \alpha_i,...,\alpha_n, find a rational linear approximation for these n numbers, i.e., find n numbers m_i such that \sum\limits_{i=1}^{n}m_i\alpha_i is as close to 0 as possible. We can construct the following matrix, where a_i is the rational approximation of \alpha_i:

A = \left[ \begin{matrix} 1 & 0 & 0 & \cdots & 0 & ca_1 \\ 0 & 1 & 0 & \cdots & 0 & c a_2 \\ 0 & 0 & 1 & \cdots & 0 & c a_3 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots & 1 & c a_n \\ \end{matrix} \right]

The matrix is n*(n+1). We can compute the determinant of the corresponding lattice using the method for computing lattice determinants:

det(L)=\sqrt{AA^T}

Let us further consider the following matrix:

A = \left[ \begin{matrix} 1 & 0 & 0 & \cdots & 0 & a_1 \\ 0 & 1 & 0 & \cdots & 0 & a_2 \\ 0 & 0 & 1 & \cdots & 0 & a_3 \\\vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 &0 & \cdots & 1 & a_n \\ \end{matrix} \right]

Then

AA^T = \left[ \begin{matrix} 1+a_1^2 & a_1a_2 & a_1a_3 & \cdots & a_1a_n \\ a_2a_1 & 1+a_2^2 & a_2a_3 & \cdots & a_2a_n \\ a_3a_1 & a_3a_2 & 1+a_3^2 & \cdots & a_3a_n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_na_1 & a_na_2 &a_na_3 & \cdots & 1+a_n^2 \\ \end{matrix} \right]

Furthermore, by trying from low dimensions to high dimensions (for a rigorous proof, consider adding an extra row and column with 1 in the top-left corner), we get the lattice determinant as:

\sqrt{1+\sum\limits_{i=1}^n\alpha_i^2}

A reference proof is as follows:

After applying the LLL algorithm, we can obtain:

||b_1|| \leq 2^{\frac{n-1}{4}} (1+\sum\limits_{i=1}^n\alpha_i^2)^{\frac{1}{2n}}

Generally, the latter term tends toward 1 when taking the n-th root, because the a_i are constants and generally unrelated to n, so:

||b_1|| \leq 2^{\frac{n-1}{4}}*k

where k is relatively small. Moreover, b_1 is a linear combination of the original vectors, so:

b_1[n]=\sum\limits_{i=1}^{n}m_ic*a_i=c\sum\limits_{i=1}^{n}m_i*a_i

Clearly, if c is sufficiently large, then the sum at the end must be sufficiently small to satisfy the above constraint.

References

  • Survey: Lattice Reduction Attacks on RSA