Overview

Having introduced the LLL reduction, we now provide a more general notions of a reduced basis for a lattice as well as provide bounds for the basis vectors. The key idea behind introducing these definitions is that once we know some basis vector is []-reduced, we can bound the sizes of the basis, which is important when algorithms require short vectors in a lattice. For fast algorithms, LLL-reduction is typically the most important notion as it can be computed quickly. Two main definitions appear often when discussing lattice reductions, which we will provide here.

Definitions

A basis$\left\{b_i\right\}_{i=1}^d$is size-reduced if $\left|\mu_{i,j}\right|\leq\frac12$. Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let $L$be a lattice, $1\leq i\leq\dim L=d$, we define the $i^\text{th}$successive minima$\lambda_i(L)$ as

Intuitively, $\lambda_i(L)$is the length of the "$i^\text{th}$ shortest lattice vector". This intuition is illustrated by the definition of $\lambda_1$:

However this is not precise as if $v$is the shortest lattice vector, then $-v$is also the shortest lattice vector.

Unfortunately, a basis$b_i$for $L$where $\lambda_i(L)=\left\lVert b_i\right\rVert$for dimensions $5$ and above. This tells us that we can't actually define "the most reduced basis" in contrast to the 2D case (see Lagrange's algorithm) and we would need some other definition to convey this intuition.

An alternate definition of$\lambda_i(L)$that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at least$i$linearly independent vectors in$L$.

Exercises

1) Show that both definitions of $\lambda_i$ are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$. Show that the successive minima are all$2$but no basis$b_i$can satisfy $\left\lVert b_i\right\rVert=\lambda_i$.

Definition

The basis$\left\{b_i\right\}_{i=1}^d$ is Minkowski-reduced if $b_i$has minimum length among all vectors in $L$ linearly independent from$\left\{b_j\right\}_{j=1}^{i-1}$. Equivalently, $b_i$has minimum length among all vectors $v$such that $\left\{b_1,\dots,b_{i-1},v\right\}$can be extended to form a basis of$L$. Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is

Bounds

The proof presented here is based off [Waerden 1956]. We proceed by induction. Let$b_i$be a Minkowski-reduced basis for some lattice$L$. The lower bound is immediate and for $i=1$, the upper bound is immediate as well.

Let $v_1,v_2\dots v_i$be linearly independent vectors such that$\left\lVert v_j\right\rVert=\lambda_j(L)$. Let $L_{i-1}$be the sublattice generated by $b_1,b_2,\dots b_{i-1}$. Evidently some$k$must exist such that$v_k$is not in $L_{i-1}$. Consider the new lattice $L'=L\cap\text{span}\left(b_1,b_2,\dots b_{i-1},v_k\right)$. Let$v'_k$be the shortest vector in$L'-L_{i-1}$such that$b_1,b_2,\dots,b_{i-1},v'_k$is a basis for $L'$and we have

If$n=1$, then we are done since$v_k$can be extended to a basis of $L$, so $\left\lVert b_i\right\rVert\leq\left\lVert v_k\right\rVert=\lambda_k(L)\leq\lambda_i(L)$. Otherwise, we have $n^2\geq4$. Let $v_k'=p+q$where$p$is the projection of$v'_k$in$L_{i-1}$. Since by definition we have$\left\lVert p\right\rVert^2\leq\left\lVert p\pm b_i\right\rVert^2$, we must have

Furthermore, since

we have $\left\lVert q\right\rVert^2\leq\frac14\lambda_k^2$, hence we have

but since $\lambda_i(L)^2\leq \left\lVert b_i\right\rVert^2$by definition, the case of $i=2,3$cannot occur here (hence $n=1$in these cases).

Exercises

1) Show that both definitions of Minkowski-reduced lattice are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$. We have showed in a previous exercise that the successive minima are all$2$but no basis$b_i$can satisfy $\left\lVert b_i\right\rVert=\lambda_i$, show that for any Minkowski reduced basis $b_i$, the basis must satisfy $\left\lVert b_i\right\rVert^2=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2$

Definition

Let $\pi_i$as the projection to the orthogonal complement of $\left\{b_j\right\}_{j=1}^{i-1}$.Then the basis is HKZ-reduced if it is size-reduced and $||b_i^*||=\lambda_1\left(\pi_i(L)\right)$. This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections.

Bounds

Definition

Let $\delta\in\left(\frac14,1\right)$. A basis$\left\{b_i\right\}_{i=1}^d$is $\delta$- LLL-reduced if it is size reduced and satisfy the Lovász condition, i.e.

This notion of reduction is most useful to use for fast algorithms as such a basis can be found in polynomial time (see LLL reduction).

Bounds