Reduced Lattice Bases

Any lattice L may be described by many different lattice bases. Let $B_1,B_2,\ldots{}$ be distinct sets of vectors, all of which form bases of lattice L. We can imagine that there exists some ordering or ranking of the bases B_i, and thus one or more of the B_i might be considered ``good'' lattice bases of L. Lattice reduction theory deals with identifying ``good'' lattice bases for a particular lattice. If we are given a basis B which describes L, we would like to reduce B to basis B', also describing L, where B' is a ``good'' lattice basis in the sense of some reduction theory. There are two classical lattice reduction theories, one due to Korkin and Zolotarev [23,24] and one due to Minkowski [29]. A basis $B = (\bold{b_1},\bold{b_2},\ldots{},\bold{b_n})$ of lattice L is said to be Minkowski-reduced if

1.

$\bold{b_1}$ is the shortest nonzero vector in L.

2.

For $2 \leq i \leq n$, $\bold{b_i}$ is the shortest vector in L such that $(\bold{b_1},\ldots{},\bold{b_i})$ may be extended to a basis of L.

Minkowski-reduced lattice bases always contain the shortest nonzero vector in the lattice. Subsequent basis vectors $\bold{b_i}$ are selected by choosing the shortest lattice vector in L which is not a linear combination of the already selected basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}}$. If $\bold{b_i} = \sum_{j=1}^{i-1} z_j \bold{b_j}, z_j \in {\Bbb Z}$, then it would be impossible to extend ( $\bold{b_1},\ldots{},\bold{b_i}$) to be a basis of L. The definition of Korkin-Zolotarev reduction is similar to that of Minkowski. We say a basis $B=(\bold{b_1},\ldots{},\bold{b_n})$ is Korkin-Zolotarev reduced if it satisfies the following three conditions:

1.

$\bold{b_1}$ is the shortest nonzero vector in L.

2.

For $2 \leq i \leq n$, let S_i be the (i-1)-dimension subspace spanned by the basis $(\bold{b_1},\ldots{},\bold{b_{i-1}})$. Let $S_i^\perp$ be the orthogonal complement of S_i in ${\Bbb R}^n$. Finally, let P_i(L) denote the orthogonal projection of L onto $S_i^\perp$. Then choose $\bold{b_i}$ such that $P_i(\bold{b_i})$ is the shortest nonzero vector in P_i(L).

3.

Size reduction condition. For $1 \leq i < j \leq n$,

$$\left\vert \left< P_i(\bold{b_i}),P_i(\bold{b_j})\right> \right\vert \leq \frac{1}{2} \Vert P_i(\bold{b_i})\Vert^2,$$

where $P_1(\bold{x}) = \bold{x}$.

In the definition of Minkowski reduction, successive basis vectors $\bold{b_i}$ are added to the lattice basis only if $\bold{b_i}$ is the shortest vector in the lattice which will allow the basis to be extended. In Korkin-Zolotarev reduction, though, successive basis vectors $\bold{b_i}$ are chosen based on their length in the orthogonal complement of the space spanned by the previous basis vectors $\bold{b_1},\ldots{},\bold{b_{i-1}}$. Depending on the specific problem, we may find either, both, or neither of the above definitions of ``good'' lattice bases is sufficient. Certainly if the goal is to find the shortest nonzero vector in the lattice, as is the case with subset sum problems (see Chapter 3), we could use either Minkowski reduction or Korkin-Zolotarev reduction as a measure of how ``good'' a particular lattice basis is. If the item of interest involves multiple vectors in the lattice, one definition may be preferred over the other for that particular application.