Many current cryptographic schemes rely on the security of lattice based assumptions. In addition, attacks on multiple cryptosystems in the past rely on lattice reduction to function.
In quite a few cases (my past posts being a main example), lattice reduction is treated as a black box algorithm that can be run. In this post I plan on detailing the underlying mechanisms a bit more.
Background: Lattices (again)
Lattices are a discrete additive subgroup spanned by a set of independent basis vectors. A lattice $\mathcal{L}(\bm{B})$ is the set of all integer linear combinations of those basis vectors.
Definition (Lattice). A lattice $\mathcal{L}(\bm{B})$ is defined as the set of points
$$\mathcal{L}(\bm{B}) = \left\{ \sum_{i=1}^{k} z_i\bm{b}_i : z_i \in \mathbb{Z} \right\} $$
Note that multiple bases can span the same lattice.
Theorem. Two bases $\bm{B}_1, \bm{B}_2$ span the same lattice if and only if $\bm{B}_1 = \bm{B}_2\bm{U}$, such that $\bm{U}$ is unimodular.
Definition (Volume). The volume of a lattice spanned by a basis $\bm{B}$ is given by $$\text{vol}(\mathcal{L}) = \sqrt{\bm{B}^T\bm{B}}$$
The volume of a lattice is independent of the choice of basis for our lattice. We see this as $$ \sqrt{\det\left(\bm{B}_2^T\bm{B}_2\right)} = \sqrt{\det\left(\bm{U}^T\bm{B}_1^T\bm{B}_1\bm{U}\right)} = \sqrt{\det\left(\bm{B}_1^T\bm{B}_1\right)} $$
One of the most important problems is the Shortest Vector Problem, which asks to find the shortest nonzero vector in a lattice. Now this problem is really hard to solve.
However, we can approximate the shortest vector fairly easily with the LLL algorithm.
The LLL Algorithm
To approximate the shortest vector, the main inner step in the LLL algorithm relies on size reduction, which is defined in terms of a Gram Schmidt basis.
Definition (Gram Schmidt orthogonalization). Let $$\bm{B} = \left\{\bm{b}_1, \cdots, \bm{b}_n \right\}$$
Then the Gram Schmidt orthogonalization $\bm{B}^* = \left\{\bm{b}_1^{*}, \cdots, \bm{b}^*_n \right\}$ is defined as follows:
$$\bm{b}_1^* = \bm{b}_1$$ $$\bm{b}_i^{*} = \bm{b}_i - \sum_{j = 1}^{i - 1} \mu_{i, j} \bm{b}_j^{*}$$
Where $\mu_{i, j} = \left< \bm{b}_i, \bm{b}^{*}_j\right> / \left< \bm{b}^{*}_j, \bm{b}^{*}_j \right>$.
This Gram Schmidt basis is a method of orthogonalizing a basis. It might seem quite opaque, but note that the $\mu \bm{b}^{*}$ coefficient is just the projection of a standard vector onto a GSO vector, creating a new orthogonal vector.
In the above image, we have $\left\{\bm{v_1}, \bm{v_2}\right\}$ being converted to GSO. We see that $\bm{u}_1 = \bm{v}_1 = \bm{v}^{*}_1$ and $\bm{u}_2 = \bm{v}^{*}_2$.
Definition (Size-reduced). A basis $\bm{b}_1, \cdots, \bm{b}_n$ is size reduced if considering its GSO representation, $$|\mu_{i, j}| \le \frac{1}{2}$$ for $1 \le j < i \le n$.
A single basis vector $\bm{b}_i$ is size reduced if $|\mu_{i, j}| \le \frac{1}{2}$ for $1 \le j < i$.
To size reduce a basis vector $\bm{b}_k$, we can do the following:
- For $i = k - 1 \cdots 1$, do the following 2 steps:
- $\bm{b}_k = \bm{b}_k - \lfloor \mu_{k, i} \rceil \bm{b}_i$
- Update the GSO.
To get a size reduced basis, we can size reduce each vector individually.
[LLL82] then also introduced the concept of LLL-reduced.
Definition (LLL-reduced). A basis $\bm{b}_1, \cdots, \bm{b}_n$ is LLL-reduced with parameter $\delta$ if it is size reduced and if $$\delta ||\bm{b}_{k - 1}^{*}||^2 \le ||\bm{b}_{k} + \mu_{k,k - 1}\bm{b}_{k - 1}^{*}||^2$$
So what is interesting about this extra condition? Well if we magically have a LLL-reduced basis, it satisfies the following properties:
Theorem (LLL). Let $\delta \in (1/4, 1]$. Let $\bm{b}_1, \cdots, \bm{b}_n$ be a $\delta$-LLL-reduced basis of a lattice $\mathcal{L}$. Then,
$$||\bm{b}_1|| \le \left(1/(\delta - \frac{1}{4})\right)^{(d - 1)/4}\cdot (\text{vol}(\mathcal{L}))^{1/d}$$
So if we have an LLL-reduced basis, then the basis vector outputted will be somewhat short, approximating the shortest vector problem.
So now we want a fast algorithm to convert a basis into an LLL-reduced basis.
The LLL algorithm consists of two main operations: swaps (to meet the LLL condition), and size reduction (to meet the size reduction condition).
Size reduction tends to shorten the projection of the vector $\bm{b}_k$ in relation to the vectors $(\bm{b}_1, \cdots, \bm{b}_{k - 1})$. The LLL condition tends to shorten $\bm{b}^{*}_{k}$.
The algorithm in itself is quite simple, the difficulty lies in showing it runs in polynomial time.
- Compute the GSO of the basis $\bm{B}$
- While $k < n$, do the following.
- Size reduce $\bm{b}_k$, and update the $\mu$ values.
- If $\delta ||\bm{b}^{*}_{k - 1}||^2 > ||\bm{b}^{*}_{k}||^2 + \mu^2_{k, k - 1}||\bm{b}^{*}_{k - 1}||^2$
- Swap $\bm{b}_{k}$ and $\bm{b}_{k - 1}$
- $k = k - 1$
- Else: $k = k + 1$
- Output $\bm{b}_1, \cdots, \bm{b}_n$.
Now if this algorithm terminates, the if condition inside the loop guarantees that all vectors satisfy the LLL condition, and we see that all of them will be size reduced as well.
Therefore, we now have an algorithm to get an approximate shortest vector. Now one major issue with the LLL algorithm currently is a majority of the computation goes into operations that use the GSO of the vectors. The GSO vectors are typically rationals due to the projections done within the GSO process.
When computing using rationals, we typically represent them as floating point values. However, this comes at the cost of a loss of precision and longer computations. The GSO process is unstable, meaning if values are replaced with floating point approximations, it behaves very differently.
Some Improvements
The main issue with floating point computation occurs when computing the inner product $\left<\bm{b}_i, \bm{b}_j\right>$. This adds quite a bit of error, as computing there are quite a few inner products and projections within the GSO.
To account for this, a new algorithm was developed in [NS09] which can deal with floating point approximations. The key insight they made was to store all inner products into a Gram matrix. Instead of performing the size reduction in one step (which adds a lot of floating point error), we can perform the size reduction incrementally in small steps and updating Gram matrix, which introduces less error.
Another improvement made in [MSV09] was to replace the Gram matrix operations with Householder transformations, which not only improves the precision of the floating point approximations, but also improves the number of operations done.
Now, even with all of the following improvements, we can only meet the approximate bound given by LLL. However, what if we want to approximate vectors which are not the shortest vector, but are shorter than the LLL bound?
Block Korkin Zolotarev
The BKZ algorithm solves this problem of finding an intermediate approximate short vector. It allows one to reduce based on a block parameter. BKZ typically runs superexponentially with respect to the block parameter. However, with low block sizes, it can reduce further than LLL in reasonable time.
Hermite Korkin Zolotarev
Before introducting the notion of block reduction, it is helpful to talk about HKZ reduction. This is a much stronger reduction than LLL, and the only known algorithms for HKZ are superexponential in the dimension.
Definition (Projected Lattice). We let $$\pi_i(\bm{x}) = \sum_{j \ge i} \frac{\left<\bm{x}, \bm{b}^{*}_j \right>}{\left<\bm{b}^{*}_j, \bm{b}^{*}_j \right>}\bm{b}^{*}_{j}$$
This is the projection of the vector $\bm{x}$ onto the span of $\bm{b}_i, \cdots, \bm{b}_n$.
Let $\mathcal{L}_{[i, j]}$ denote the lattice $\pi_i(\mathcal{L}(\bm{b}_i, \cdots, \bm{b}_j))$, projecting all lattice points spanned by the basis vectors from $i$ to $j$ into the subspace of rank $j - i + 1$.
Definition (HKZ-Reduced). A basis $\bm{b}_1, \cdots, \bm{b}_n$ is HKZ-reduced if it is size reduced and $||\bm{b}^{*}_{i}||$ is the shortest nonzero vector in $\mathcal{L}_{[i,n]}$.
The HKZ reduction condition is much stronger than the LLL condition, so much so that we cannot find an HKZ reduced basis in polynomial time. Specifically, the strength of this is shown with the following theorem.
Theorem (HKZ). If a basis $\bm{b}_1, \cdots, \bm{b}_n$ is HKZ-reduced, then $$\frac{4}{i + 3} \le \frac{||\bm{b}_i||^2}{\lambda_i^2} \le \frac{i + 3}{4}$$
where $\lambda_i$ is the length of the $i$-th shortest nonzero vector.
This theorem shows that each of the HKZ reduced vectors is very close the actual shortest vectors in the lattice. Meanwhile, the LLL bound is more lenient.
Block reductions
Block reduction was introduced by Schnorr for reduction of vectors that do not meet the LLL bound. Instead of the HKZ condition, we instead have the following:
Definition (BKZ-Reduced). If a basis $\bm{b}_1, \cdots, \bm{b}_n$ is $\beta$-BKZ-reduced if it is size reduced and $||\bm{b}^{*}_{i}||$ is less than the shortest nonzero vector in $\mathcal{L}_{[i, k]}$ where $k = \min(i + \beta - 1, n)$.
In this case, we decrease the size of the projected lattice to $\beta$, instead of $n$. Intuitively, a BKZ reduced basis is a basis where the vectors are the shortest possible vectors in the projection of the lattice of size $\beta$.
In this geometric notion of lattice reduction, we will also see that the LLL algorithm solves the shortest vector problem in a projected lattice of rank $2$.
Theorem (BKZ and LLL relation).
A basis $\bm{b}_1, \cdots, \bm{b}_n$ is 2-BKZ-reduced if and only if it is LLL-reduced with $\delta = 1$.
The algorithm for BKZ is somewhat involved. The main step involves a subroutine to find the shortest vector in a projected lattice of size $\beta$. The original formulation for BKZ in [SE94] involved creating a tree of a subset of the vectors, where each subtree is a projection of that subset on a smaller lattice. Afterwards, one performs a depth first search on the tree. There is no good upper bound on the complexity of BKZ, which remains an open problem.
Improvements
The enumeration subroutine for BKZ can be optimized based on many parameters and structure of the lattice. After constructing the tree, some branches (those with high probability of not having the shortest vector in the projected lattice) can be pruned off from the main tree, improving the search.
A true estimate of the cost and success of enumeration and pruning is unknown, and current estimates rely on standard heuristics. However, in practice BKZ performs quite well for low blocksize ($\beta < 30$).
Conclusion
LLL, HKZ, and BKZ are all important algorithms for current state of the art lattice reduction and linear programming. Though we typically do not consider how such algorithms work, it is better to understand the internals when such algorithms do not work on specific lattices.
I have been leaving out the proofs for a lot of these theorems and statements that have been made (including analysis for these algorithms). However, check out the references and this blog post from the Simons institute if you would like to actually see the proofs.
An implementation of all of these algorithms lies within the fpLLL repository. Check it out if you are interested!