CryptoBook
Search…
Lattice reduction

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
{bi}i=1d\left\{b_i\right\}_{i=1}^d
is size-reduced if
μi,j12\left|\mu_{i,j}\right|\leq\frac12
. Intuitively this captures the idea that a reduced basis being "almost orthogonal".
Let
LL
be a lattice,
1idimL=d1\leq i\leq\dim L=d
, we define the
ithi^\text{th}
successive minima
λi(L)\lambda_i(L)
as
λi(L)=min(max1ji(vj):vjL are linearly independent)\lambda_i(L)=\min\left(\max_{1\leq j\leq i}\left(\left\lVert v_j\right\rVert\right):v_j\in L\text{ are linearly independent}\right)
Intuitively,
λi(L)\lambda_i(L)
is the length of the "
ithi^\text{th}
shortest lattice vector". This intuition is illustrated by the definition of
λ1\lambda_1
:
λ1(L)=min(v:vL)\lambda_1(L)=\min\left(\left\lVert v\right\rVert:v\in L\right)
However this is not precise as if
vv
is the shortest lattice vector, then
v-v
is also the shortest lattice vector.
Unfortunately, a basis
bib_i
for
LL
where
λi(L)=bi\lambda_i(L)=\left\lVert b_i\right\rVert
for dimensions
55
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
λi(L)\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
ii
linearly independent vectors in
LL
.

Exercises

1) Show that both definitions of
λi\lambda_i
are equivalent
2) Consider the lattice
L=(2000002000002000002011111)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
22
but no basis
bib_i
can satisfy
bi=λi\left\lVert b_i\right\rVert=\lambda_i
.
Last modified 5mo ago
Export as PDF
Copy link