In 1985 Lagarias and Odlyzko [26]
developed a general attack on knapsack cryptosystems which reduces solving
subset sum problems to the problem of finding the Euclideannorm shortest
nonzero vector in a point lattice. Recent improvements to this attack [12,19]
have stimulated interest in finding lattice basis reduction algorithms
wellsuited to the lattices associated with subset sum problems. This thesis
studies a new approach to lattice basis reduction originally developed by M.
Seysen [38].
Seysen's reduction algorithm was initially developed to find simultaneously good
bases of a lattice and its dual lattice. However, it may also be successfully
applied to solving subset sum problems, especially when combined with other
known reduction methods. Using a collection of techniques, including Seysen's
algorithm, we show that it is possible to solve in practice a much larger class
of subset sum problems than was previously possible.
Let B be a set of vectors
in
.
If these vectors are independent, then they form a basis of
and any point
in nspace may be written as a linear combination of vectors in B:
Consider the set of points
which may be written as the sum of integer multiples of the basis
vectors:
We call this set L the point lattice (or just lattice)
described by the basis B. Point lattices are pervasive structures in
mathematics, and have been studied extensively. See [25],
for example, for a survey of the field. In the area of combinatorial mathematics
alone it is possible to phrase many different problems as questions about
lattices. Integer programming [20],
factoring polynomials with rational coefficients [27],
integer relation finding [16],
integer factoring [35],
and diophantine approximation [36]
are just a few of the areas where lattice problems arise. In some cases, such as
integer programming existence problems, it is necessary to determine whether a
convex body in
contains a lattice point (for some specific lattice). In other cases the items
of interest are short vectors in the lattice. As we shall see below, for certain
cryptographic applications, we would like to be able to quickly determine the
Euclideannorm shortest nonzero vector in a lattice. It is important to note
that the difficulty of finding the Euclideannorm shortest nonzero vector in a
lattice is an open question. If
,
then the supnorm of ,
denoted
,
is defined as
It is known that finding the supnorm shortest nonzero vector in a lattice is NPhard [5]. Based on this evidence, we suspect that finding the Euclideannorm shortest nonzero vector for any given lattice is also computationally difficult. However, it may be possible to find the shortest nonzero vector for many lattices quickly. Indeed, current techniques for finding short vectors are slow in theory but often perform well in practice. The remainder of this chapter establishes the environment for our study of lattices and specific applications to cryptography. Section 1.2 discusses reduced bases of lattices and lattice reduction theory. Section 1.3 mentions some of the algorithms which currently exist for computing a reduced lattice basis B' given a basis B of a particular point lattice. In particular, we detail the operation of the LenstraLenstraLovász (LLL) basis reduction algorithm [27], which is currently the best known method for finding short vectors in a lattice.
Any lattice L may be described by many different lattice bases. Let 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 of lattice L is said to be Minkowskireduced if
is the shortest nonzero vector in L.
For , is the shortest vector in L such that may be extended to a basis of L.
Minkowskireduced lattice bases always contain the shortest nonzero vector in the lattice. Subsequent basis vectors are selected by choosing the shortest lattice vector in L which is not a linear combination of the already selected basis vectors . If , then it would be impossible to extend ( ) to be a basis of L. The definition of KorkinZolotarev reduction is similar to that of Minkowski. We say a basis is KorkinZolotarev reduced if it satisfies the following three conditions:
is the shortest nonzero vector in L.
For , let S_{i} be the (i1)dimension subspace spanned by the basis . Let be the orthogonal complement of S_{i} in . Finally, let P_{i}(L) denote the orthogonal projection of L onto . Then choose such that is the shortest nonzero vector in P_{i}(L).
Size reduction condition. For
,
where .
In the definition of Minkowski reduction, successive basis vectors are added to the lattice basis only if is the shortest vector in the lattice which will allow the basis to be extended. In KorkinZolotarev reduction, though, successive basis vectors are chosen based on their length in the orthogonal complement of the space spanned by the previous basis vectors . 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 KorkinZolotarev 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.
Although both Minkowski reduction and KorkinZolotarev reduction provide
frameworks for studying lattice basis reduction, computing a reduced lattice
basis (in either sense) is in general a difficult problem. Currently, there are
no known polynomialtime algorithms for finding either a Minkowski or a
KorkinZolotarev reduced basis for a given lattice L. If such an
algorithm existed, then we would be able to find the Euclideannorm shortest
nonzero vector in L in polynomial time by finding the reduced basis, for
which
is the desired vector. Thus, any polynomialtime lattice basis reduction
algorithm we use will not be able to satisfy the strict conditions of Minkowski
or KorkinZolotarev reduction. Techniques for finding relatively small vectors
in a lattice have been known for some time (see [22]
for example); it was not until recently, though, that a fast algorithm was known
which was guaranteed to produce lattice bases with relatively short vectors. In
[27]
Lenstra, Lenstra and Lovász described a polynomialtime algorithm for
transforming a give lattice basis
of lattice L into an LLLreduced lattice basis
.
A basis B' is LLLreduced if it has the following two properties:
where the parameter
and
(That is,
is a GramSchmidt orthogonalized basis generated from B). Notice that LLL
reduction is similar to but weaker than KorkinZolotarev reduction. The
LenstraLenstraLovász basis reduction algorithm converts lattice basis B
into B' by performing two types of transformations. In a sizereduction
step, LLL finds the largest j such that there exists an i > j
and
violates Equation 1.1.
By performing the transformation
where
denotes the nearestinteger function, we find that the new value of
is
.
In the exchange step, LLL searches for the smallest value of i
such that
and
fail to satisfy Equation 1.2.
Here LLL swaps the two vectors (
and
)
to force compliance with the second LLLreduced condition. The LLL basis
reduction algorithm alternately performs sizereduction and exchange steps until
both Equations 1.1
and 1.2
are satisfied, at which point the algorithm halts. LLLreduced lattice bases
satisfy a number of bounds. In particular, if y is the global LLL
constant, then the first vector in the reduced lattice basis
satisfies:
In particular, for
(the value used in [27]),
we have
Thus the length of is at most an exponential multiple of the length of the shortest nonzero vector in the lattice. (Similar bounds exist for the other vectors in the reduced basis.) In practice, the LLL algorithm usually performs much better than this exponential bound, although example lattice bases are known which cause the LLL algorithm to exhibit worstcase performance. Most of the work on lattice basis reduction algorithms since the introduction of LLL has focused on improving and extending the technique. For example, the version of LLL described above requires rational arithmetic (the variables in particular must be stored as fractions); multiprecision floatingpoint numbers are usually used to reduce the computation requirements, but may introduce error into the calculations. One method of reducing the multiprecision requirements is described in [33]. Similarly, [32] showed how to modify the LLL algorithm so that the set of input vectors can be linearly dependent. Hierarchies of LLLtype algorithms have been investigated [34], stretching from LLLreduction at one end of the spectrum to KorkinZolotarev reduction at the other. However, little effort has been expended on looking at algorithms not derived from or similar to LLL. This thesis examines an approach to lattice basis reduction of different structure than that of the LLL algorithm and related methods. This method was originally suggested by M. Seysen [38] to simultaneously produce a reduced basis and a reduced dual basis for some lattice L. Where the LLL algorithm concentrates on local optimizations to produce a reduced lattice, the Seysen approach considers the entire basis for methods of optimization. (Recall that the LLL sizereduction steps only consider for the smallest possible j, and that only adjacent vectors and may be exchanged.) Chapter 2 describes the first phase of the research, in which Seysen's basis reduction algorithm and multiple variants were implemented and examined. Theoretical and empirical analyses of the fixed components of Seysen's algorithm are given. For those parts of the algorithm which are permitted to vary, we examine some of the possible variations, and look at the effect of these changes on the performance of the algorithm. Possible extensions of the algorithm are also discussed. The motivation behind our study of Seysen's lattice basis reduction algorithm is presented in Chapter 3. It is known that certain subset sum problems may be solved by finding the shortest nonzero vector in a particular lattice (the lattice is generated based on the specific construction of the subset sum problem). The best methods previously known for reducing subset sum problem lattices [26,33] involve the LLL algorithm and some other heuristics, and are not very successful for n > 25 (n is the size of the subset sum problem to be solved). Chapter 3 details experiments which used Seysen's algorithm in combination with the LLL algorithm and other heuristics to solve a much greater range of subset sum problems.
In 1988, Martin Seysen proposed a new method for performing lattice basis
reduction [38].
Seysen's basis reduction algorithm (or just Seysen's algorithm)
differs from the LLL algorithm and its variants in that it considers all vectors
in the lattice simultaneously, and performs operations on those vectors which
will reduce the lattice according to some measure. Recall that the LLL algorithm
works locally on the lattice it is reducing; LLL will only perform an operation
on two vectors which are adjacent to each other in the ordered lattice basis.
Seysen was motivated to create a new method for basis reduction by a desire to
find a better way to simultaneously reduce a lattice and its reciprocal (or
dual) lattice. If lattice L is defined by basis vectors
,
then the dual lattice L^{*} of L is defined by basis
vectors
,
where
Now consider what happens in the dual lattice when we perform a row move
on
and
in L. (A row move is any operation which adds a constant multiple
of one lattice basis vector to another basis vector.) Let
,
where
.
We consider what changes must occur in the dual lattice basis vectors
,
since Equation 2.1
must hold at all times. For ,
we find that:
For k = i, however, this is not the case:
Thus, when we add
to
in the basis of lattice L, we must subtract
from
in the basis of L^{*}. It is easy to see that if lattice L
is reduced with the LLL algorithm, the resulting reduced lattice may have a dual
in which some basis vector is quite large, as no attempt is ever made to
consider the size of the dual basis when row moves are being performed. Seysen's
algorithm attempts to choose row moves that reduce both the lattice and its
dual. We now outline the basic operation of Seysen's algorithm. Let L and
L^{*} be a lattice and its dual which we wish to simultaneously
reduce. Let A and A^{*} be the associated quadratic forms
of L and L^{*}, respectively:
The element a_{i,j} of matrix A is the inner
product of the basis vectors
and
of lattice L. Notice that A and A^{*} are inverses
of each other and are symmetric. If L is the lattice defined by basis B,
then any other basis B' of L may be written as:
where
(i.e. T is an
integer matrix with determinant 1). The quadratic form A' associated with
B' may similarly be derived from A:
For any quadratic form A, define the Seysen measure S(A)
as follows:
A basis B is then Sreduced if:
We suspect that it is computationally difficult to find the optimal
transformation matrix T for a given basis B. Consider, however,
the class of transformation matrices
defined by:
(The matrix U_{i,j} has exactly one nonzero entry.
Matrix
has diagonal entries of 1 and exactly one nonzero offdiagonal entry.)
Rightmultiplying B by any
simply adds
times the
column of B to the
column of B. If the columns of B are the basis vectors
,
then
is simply the transformed basis
.
Since it is easy to perform calculations with
transformations, we focus our attention on products of one or more
transformation matrices. It can be shown that every
may be written as such a product:
We call a quadratic form S_{2}reduced if
Seysen suggests the following algorithm for S_{2}reducing a
quadratic form:
while (A is not S_{2}reduced)
do
choose i,j such that
with
let
let
where
denotes the nearestinteger function. This procedure for S_{2}reducing
a quadratic form is Seysen's basis reduction algorithm. To date, little has been
proven concerning the performance of Seysen's algorithm. There are no known
bounds on the Seysen measure of an S_{2}reduced basis (although
bounds have been proven for Sreduced lattice bases), nor on the length
of the shortest nonzero vector in the basis. The running time of Seysen's
algorithm is clearly bounded if the lattice basis consists of only integer
vectors, but it is not known if the algorithm even terminates for basis vectors
with real coefficients. However, preliminary experiments performed by Seysen on
lattices of dimension
suggest that this technique may be faster than the LLL algorithm and yield bases
with shorter vectors. Based on these observations, a comprehensive investigation
of theoretical and practical aspects of Seysen's algorithm was undertaken. This
chapter details the results of our study of Seysen's basis reduction algorithm.
Section 2.1
below discusses the theoretical underpinnings of Seysen's algorithm. Empirical
tests performed with various versions of the Seysen algorithm are detailed in
Section 2.2.
Section 2.3
mentions some modifications which may be made to Seysen's algorithm when the
performance of the basic version breaks down. Finally, Section 2.4
discusses possible extensions to Seysen's algorithm.
We consider first the theoretical foundations of Seysen's basis reduction
algorithm. There are a number of questions concerning the actual structure of
the algorithm which immediately arise. For a given quadratic form A, how
might the Sreduced and S_{2}reduced forms derived from A
differ? Is it even sufficient to consider only
transformation matrices, or are there lattices for which it is impossible to
find the Sreduced form using only
transformations? How do we choose the order in which to apply the
transformations, or equivalently how do we choose pairs of basis vectors for row
moves? Is the Seysen measure function
a ``good'' way to rank different bases of a lattice? Finally, given that S(A)
is an acceptable measure function, is our choice of
,
given i and j, optimal? This section considers theoretical
justifications for all of these questions. Section 2.2
below considers these questions from an empirical point of view.
As defined above, a basis B is Sreduced if and only if its
associated quadratic form A satisfies:
(2.4) 
Thus, in order to Seysenreduce a given lattice L which we know has basis
B, we need to find a transformation matrix
such that for all other
we have
.
As
is the set of all
matrices of unit determinant, we suspect that it is computationally difficult to
find the desired matrix T directly. However, there are ways to avoid
having to compute matrix T directly. Specifically, we can restrict our
attention to a set of generating matrices for
,
as we show below. Initially, let us assume that n = 2 and that A
is the quadratic form associated with a lattice basis we wish to reduce.
thus contains all
matrices
with
ad  bc = 1. Now, it is known [2,37]
that the set G_{2} is a set of generating matrices for
,
where:
That is, if ,
then there exists a sequence of matrices
such that
(Actually, the set
is sufficient, since
Section 2.2.2
below discusses the performance of Seysen's algorithm when we restrict
.)
Notice that the matrices
and
describe all possible row moves which can be performed on a
matrix. As an example, note that the matrix
is generated by:
(S_{0} corresponds to swapping the two rows in a matrix.) Thus,
the set of matrices
for
is exactly a set of generating matrices for
.
Therefore, it is sufficient for n = 2 for Seysen's algorithm to consider
only products of matrices of the form
.
The difficulty is in choosing the right matrices and the right order of
operations. Our analysis above assumed n = 2, but similar results are
known where n is an arbitrary integer [30].
For fixed n > 0,
is a set of generating matrices for . Thus, it would be sufficient for Seysen's algorithm to consider only T_{i,j}^{1} and T_{i,j}^{1} transformation matrices if it could pick the proper triples at every step. In practice, Seysen's algorithm chooses triples where , but the basic problem is still choosing the right triples in the right order. Choosing the correct (i,j) pairs to reduce and the value of for that pair are discussed below.
Seysen's algorithm does not specify how to choose which pair of basis vectors
to reduce on each iteration of the algorithm. At every iteration, it is
necessary to find an (i,j) pair for which there exists a
transformation matrix
,
such that:
Therefore, given that initially there are likely to be many pairs of vectors
which may be reduced, we must decide how to select the best pair. Two options
appear immediately as candidate vector selection methods: lazy selection
and greedy selection. A lazy selection scheme simply chooses any
available (i,j) pair in the easiest possible manner. For example,
we can imagine two nested loops which generate (i,j) pairs and
stop at the first pair for which
,
where
Once such a pair is found, a
transformation can be performed on the lattice basis. Then the algorithm could
search for another (i,j) pair, perhaps continuing the search at
the first pair lexicographically after (i,j). The second possible
candidate selection method is a greedy approach. Here we calculate
for each possible pair (i,j), where
is defined:
Thus, any transformation matrix will have . The algorithm then uses the pair of vectors which minimizes in the next row move. One immediate disadvantage to a greedy approach is that it requires more extensive computations than the lazy selection method. This is true of any set of selection criteria which attempts to choose vector pairs to reduce in some fashion which performs better than random selection. If the two selection methods yield reduced bases of comparable Seysen measure, the added cost of an ``intelligent'' method may be greater than the time saved by reducing the number of row operations. However, if one method should yield lattices with lower Seysen measure, the extra costs may be justified. We should point out that there is a distinction between choosing a pair of vectors to reduce and actually performing the reduction. Choosing a pair of vectors to reduce because they have the greatest potential to reduce the Seysen measure does not necessarily imply that we should perform the entire reduction and use the largest possible value of . It may be wise to perform only a fraction of the possible row moves and reevaluate other possible pairs of vectors. We run the risk, if we are too greedy, of getting stuck too soon in a local minimum. There are reasons both to favor and to suspect the value of intelligent vector pair selection methods. One of the advantages that Seysen's method has over the LLL family of basis reduction algorithms is that it looks at all the vector pairs simultaneously. The LLL algorithm works in a fashion similar to a bubble sort and LLL only considers row operations involving ``adjacent'' basis vectors (i.e. and for ). The cost of intelligent selection methods in terms of additional operations is certainly a disadvantage, but only if the cost is a significant fraction of the total running time. Section 2.2.1 below discusses these issues and presents empirical evidence of the cost and performance of a number of selection schemes for Seysen's algorithm. From our experiments, the greedy selection scheme performs better than the lazy scheme, and the additional computation required to implement greedy selection is small.
Equation 2.2
above introduced the Seysen measure function
;
the entire operation of Seysen's lattice basis reduction algorithm centers on
this quantization of relative reduction of two bases of lattice L. It is
natural to question whether Seysen measures are indeed a reasonable means of
ranking different lattice bases. We mention here some of the theoretical
evidence which suggests that ranking lattice bases by their Seysen measure is
appropriate. The use of the quantity
derives from elementary ndimensional geometry. Recall the definition of
the dual lattice
of lattice B:
where
is the Dirac delta function (
if i = j,
otherwise). Now, fix i and notice that
where
is the angle between
and
.
(Note that
beacuse of the way in which
is defined.) Let S_{i} denote the (n1)dimensional
hyperplane spanned by the basis vectors
.
Notice that
is perpendicular to S_{i} by definition. Thus, given that
is the angle between
and
,
the angle between
and S_{i} is
.
Thus, if
,
Equation 2.5
becomes
If basis vector
is relatively dependent of the other vectors
,
then the angle between
and the hyperplane S_{i} will be relatively small, and
thus
will be large. Conversely, if
is relatively independent of the other basis vectors,
will be close to
radians, and the product
will be close to one^{2.1}.
These geometric arguments lead directly to a measure which is a function of the
products
where
.
Since
,
we could choose the function
as the measure function. Unfortunately, as Section 2.4.4
points out below, there is no simple formula for finding the optimal value of
for a row move involving the basis vectors
and
.
Seysen is able to avoid these computational difficulties by using
as the measure function, which does yield a simple formula for .
Since
,
the squared terms in the S(A) function are guaranteed to be larger
on a termbyterm basis than the corresponding terms in the S_{1}(A)
sum. Thus, if lattice basis B_{1} has smaller measure than basis B_{2}
using the S_{1} measure function, B_{1} will also
have smaller measure than B_{2} when compared using the Seysen
measure S. An additional advantage to using a function of the
product terms is that bounds exists on the size of the individual terms. In [17]
Hċstad and Lagarias show that the following bound applies for some primal basis
B and dual basis B^{*} of a given lattice:
This bound immediately implies that there exists a basis of L with Seysen
measure bounded by
,
since:
Seysen shows in [38]
that the bound in Equation 2.6
may be improved to
which reduces the bound on S(A) for an Sreduced lattice
to:
To date, this is the best known bound on the Seysenmeasure of an Sreduced
lattice basis. However, as is the case with the LLL algorithm, in some cases
Seysen's algorithm produces S_{2}reduced lattice bases which
have measures much lower than the theoretical bound.
We now consider the choice of
values in Seysen's basis reduction algorithm. Assume that S(A) is
as in Equation 2.3
above, and that only twovector row moves are considered (i.e. transformation
matrices of the form
for integer values of i,j and ).
We first show that
yields the maximum possible reduction in S(A) for fixed values of i
and j where
.
Further, we show that if we require
,
then
is indeed the value which yields the best possible reduction in the Seysen
measure of the lattice basis. Let i,j be fixed integers with
;
and
are the basis vectors on which we will perform a row move. Without loss of
generality, we assume that
will be added to
and
will be subtracted from
.
Define
and
to be the values of
and
after the row move is performed:
Let A and A^{*} be the quadratic forms associated with the
lattice and its dual before the row move occurs, and let A' and A^{*}'
be the associated quadratic forms after the row move. Then
Now, given that
transition matrices have exactly one offdiagonal nonzero entry, it is easy to
see that A' differs from A only in the values in the
row, the
row, the
column, and the
column. The same is also true for A^{*}'. Since the Seysen
measure function S(A) only depends upon the diagonal elements in A
and A^{*}, we know that
When A is rightmultiplied by
,
the
column of A is added to the
column of A. When this matrix is subsequently leftmultiplied by
,
the
row is added to the
row. Thus, after these two transformations, the value of a_{i,i}
is unchanged, but
If we perform a similar analysis in the dual quadratic form A^{*},
we find that
Using Equations 2.12
and 2.13,
Equation 2.11
becomes:
Differentiating with respect to
and setting the result equal to 0, we find that:
Thus, if
could take on any real value, for fixed i and j the minimum value
of S(A') is obtained with
.
We have shown that the minimum value of S(A) with
is obtained when
satisfies Equation 2.8.
Our goal now is to show that if
is restricted to integer values, Equation 2.9
yields that value of
for which S(A) is minimized. Let
We know that for fixed i,j,
minimizes the value of .
Furthermore, as
is a quadratic function of ,
at least one of
and
must minimize
for fixed, integer values of .
Consider
and
:
Thus,
As S(A) is a nonnegative valued function which we want to
minimize, we are interested in large, negative
values (i.e.
should be large,
).
Thus, if Equation 2.14
is > 0, we should choose
;
similarly, if Equation 2.14
is < 0, set
.
When is Equation 2.14
greater than zero?
Thus, if
,
then Equation 2.14
is positive, and we should choose
.
If
,
Equation 2.14
is negative, and we should set
.
Thus,
which proves Equation 2.9.
In the previous section we attempted to provide some theoretical justification
for Seysen's basis reduction algorithm. The basic analysis suggests that
Seysen's technique is viable, but as yet there are no significant bounds on the
running time of the algorithm. In this section we detail numerical experiments
which were performed using Seysen's algorithm. These experiments yield greater
insight into the classes of lattices best suited for reduction by Seysen's
algorithm, as well as an indication of the effectiveness of Seysen's technique.
Before we begin detailing the empirical results it is appropriate to detail our
test conditions. All implementations of Seysen's basis reduction algorithm and
the LLL algorithm were written in FORTRAN. Multiprecision floating point
arithmetic operations were performed by a package of routines written by David
Bailey at the NASA Ames Research Center [4].
Tests were run on Silicon Graphics, Inc., IRIS4D workstations; the IRIS uses
the MIPS R3000 chip set as its main processor. The experiments described below
explore many of the same aspects of Seysen's algorithm discussed in the previous
section. Section 2.2.1
compares lazy and greedy schemes for choosing the row move to perform on each
iteration of the algorithm. The effects of restricting
choices are discussed briefly in Section 2.2.2.
Sections 2.2.3
and 2.2.4
compare the performance of Seysen's algorithm with the LLL lattice on two
classes of lattice bases.
In Section 2.1.2
above we outlined the differences between lazy and greedy methods for selecting
a row move to perform on each iteration of the Seysen while loop. In
this section we describe the results of test lattice reductions on
smalldimension lattices using both the lazy and greedy approaches. All
experimental tests were performed on random integer lattices of determinant one.
Integer lattice bases were generated as follows. Let B be an
integer matrix where the
column of B corresponds to basis vector
.
The elements of matrix B are:
The function
generates a random number chosen uniformly from the interval [0,x]; in
these experiments x = 4. Notice that
since B
is uppertriangular and all diagonal entries
b_{i,i} = 1. To generate a random, dense lattice
which is not uppertriangular yet still has determinant equal to 1, we perform
random row moves on matrix B to generate matrix B'. We choose n^{2}
pairs of integers (i,j) with
and .
For each such pair,
is chosen to be +1 or 1 with equal probability. Then, the current
is scaled by
and added to
.
(That is, we set
.)
The result of these n^{2} random row moves is matrix B',
which is a basis for our test lattice L. Since
transformations preserve the determinant of the lattice, we know that
.
We may thus measure the performance of Seysen's algorithm on lattice L by
how close reduced lattice L' is to I_{n}.
n 
Avg. # Steps (Lazy) 
Avg. # Steps (Greedy) 
Ratio (Lazy/Greedy) 
20 
2079.90 
758.50 
2.74 
25 
4096.40 
1624.25 
2.52 
30 
7444.80 
3279.45 
2.27 
35 
8787.35 
3094.25 
2.84 
Table 2.1 summarizes the results of tests
comparing the performance of lazy and greedy selection methods. Twenty test
lattices were generated for each dimension
.
In all cases where ,
both lazy and greedy algorithms were able to completely reduce all test lattices
to I_{n}. The table shows the average number of row moves
required by the lazy and greedy methods to reduce a lattice to I_{n}.
On average, the lazy selection scheme required over twice as many row reductions
as the greedy scheme did to reduce a given test lattice. At n = 35 the
lazy algorithm was able to reduce to I_{n} only two of the
twenty attempted lattices; the remaining problems all encountered local minima
during the reduction, thus halting Seysen's algorithm. The greedy implementation
was unable to completely reduce any of the n = 35 test lattices. The two
versions of the algorithm performed about equally well if we look at the Seysen
measure of the reduced n = 35 test lattices. These experimental results
tell us two things concerning the relative merits of lazy and greedy selection
schemes. First, when both lazy and greedy methods are likely to produce lattice
bases with similar Seysen measures, the greedy selection methods will save at
least a factor of two in the number of reduction steps. Second, based on the n
= 35 data, using greedy instead of lazy does not appear to significantly reduce
the performance of the algorithm as a whole. For our test lattices neither
method performed significantly better than the other in terms of the Seysen
measure of the S_{2}reduced lattice bases. One might argue that
it is not reasonable to compare only the number of reduction steps required to
reduce lattices using greedy and lazy selection methods, since that measure
fails to take into account the cost of selecting the two basis vectors to
reduce. A naive implementation of the greedy algorithm might require O(n^{2})
time, as there are
possible pairs of basis vectors
which must be considered. However, it turns out that, after an initial O(n^{2})
precomputation phase, only O(n) time is required to greedily
select the next row move. Assume that we have computed
values for all pairs of integer
.
Now, after a specific row move involving basis vectors i' and j'
is performed, the only previously computed values of
which need to be updated are those for which
i = i', i = j', j = i' or j = j'.
(If you consider
to be an array of values, the
and
rows and columns of
are all that need to be recomputed.) Thus, this recomputation can be performed
in O(n) time. Storing
values can reduce the cost of a greedy selection method from O(n^{2})
to O(n). However, even O(n) cost would be
prohibitive if the actual amount of computation required to select a pair of
vectors was comparable to the cost of performing a row move. This is not the
case; performing a row move requires O(n) multiprecision math
operations, whereas the stored
values need only be stored as single or doubleprecision floating point
numbers. (The values are generally different enough that 32 or 64 bits will
provide more than enough precision.) Since multiprecision operations take
significantly more time than doubleprecision operations, and since each
rowmove requires O(n) operations, it seems reasonable to discount
the added cost of performing the greedy selection as noise when compared to the
cost of implementing the main portion of the algorithm. Based on these
experimental results, we chose to use a greedy selection strategy in all
subsequent implementations of Seysen's basis reduction algorithm. For lattices
where we know that Seysen's algorithm will be able to perform a significant
amount of basis reduction, such as the sparse lattices associated with subset
sum problems (see Chapter 3),
the greedy selection method and its expected reduced execution time are
preferred.
As shown in the previous section, the selection method for choosing row moves in
Seysen's algorithm can affect both the algorithm's performance and running time.
In our comparison of lazy and greedy selection methods above, however, we
implicitly sidestepped another such issue: the method by which values of
are chosen for a specific row move. Section 2.1.4
showed that for specified lattice basis vectors
,
the value of
which minimizes
is:
However, recall from Section 2.1.1 that any transformation matrix may be represented as the product of matrices (+1 if , 1 otherwise). Thus, when a transformation is applied to lattice basis B, we are implicitly performing row moves at once. It may be the case that for some lattices, a finer degree of control is required; that is, a greedy algorithm might perform even better if it was restricted to performing only T_{i,j}^{1} and T_{i,j}^{1} transformations. That way the algorithm would have the finest possible degree of control over row operations. It is also important to note that a greedy selection mechanism uses values in two distinct places. First, in order to select a pair of basis vectors to reduce, the greedy approach calculates for all possible values of ( is the function in Equation 2.15 above). Once a pair of vectors has been chosen, a transformation is applied. In the first case, is used as part of the scoring mechanism in order to choose a set of basis vectors to reduce. In the second case plays a different role, the number of times to add vector to . Because values have these two distinct functions, it is important that we distinguish between those roles when testing methods of choosing values. We consider in this section three versions of Seysen's basis reduction algorithm and their performance on a set of randomly generated integer lattices^{2.2}. All three versions use a greedy selection scheme to choose the next row move to perform. They differ only in the set of allowed values of in the scoring and transformation phases. These version are:
: may take on any integer value when choosing a set of basis vectors for the next row move, and any may be performed on those vectors.
: may take on any integer value when choosing a set of basis vectors for the next row move. However, only T_{i,j}^{1} and T_{i,j}^{1} actual transformations are allows. (If we add to . If we subtract from .)
: may only be when choosing the next row move, and only transformations may be performed on the basis.
The
version is identical to our ``greedy'' implementation of the previous section;
it will serve as our control. The
version of Seysen's algorithm is designed to greedily select the best possible
row move based on unlimited
values, but to perform the least possible number of changes to the lattice basis
before recomputing what to do next. The
version also restricts lattice basis changes to the minimum amount possible on
each step, but this version selects a row move based only on what it can do
immediately to reduce the S(A) measure, not on any ``future
potential.''
n 
L_{10} 
S(A) 
L_{10}^{*} 
Method 
L_{10}' 
S(A') 
L_{10}^{*}' 
# Steps 





0. 
20. 
0. 
757.4 
20 
82.4 

118.2 

0. 
20. 
0. 
767.0 





0. 
20. 
0. 
787.3 





0. 
25. 
0. 
1622.1 
25 
132.0 

192.9 

0. 
25. 
0. 
1603.4 





0. 
25. 
0. 
1610.3 





0. 
30. 
0. 
3275.3 
30 
195.8 

287.2 

0. 
30. 
0. 
3176.1 





0. 
30. 
0. 
3316.1 





110.4 

112.6 
3037.0 
35 
269.2 

390.0 

99.0 

102.2 
3022.0 





112.3 

114.6 
2920.8 





216.9 

227.1 
2240.2 
40 
343.8 

507.0 

206.5 

217.0 
2399.4 





205.0 

217.3 
2527.2 





304.6 

323.5 
2369.9 
45 
434.0 

656.7 

290.6 

312.3 
2569.8 





296.5 

315.8 
2739.2 





402.8 

429.2 
2698.1 
50 
541.2 

833.5 

386.1 

418.4 
3276.4 





393.8 

422.4 
3491.1 
Table 2.2 compares the performance of the
,
and
versions of Seysen's basis reduction algorithm. For each value of n,
twenty test lattices of dimension n were generated and Seysenreduced by
each of the three methods. The table lists aggregate information for each value
of n (all numbers shown are the geometric mean of the experimental values
obtained for each of the twenty test lattices):
n: The dimension of the test lattice in this group.
L_{10}: before reduction.
S(A): The Seysen measures before reduction.
L_{10}^{*}: before reduction.
Method: The restructions placed of values.
L_{10}': after reduction.
S(A'): The Seysen measure after reduction.
L_{10}^{*'}: after reduction.
# Steps: The number of row moves performed during the reduction.
For , all three implementation were able to completely reduce all test lattices to I_{n}. The only difference in the performance of the three methods was in the number of reduction steps required to reduce a test lattice, and these differences were minor (no more than 5% variation among any of the values for a given dimension). More differences among the methods appeared once and Seysen's algorithm was no longer able to reduce any of the test lattices to I_{n}. For the majority of the test lattices, the appears to yield the most Seysenreduced lattice basis, although it requires significantly more row moves to perform this reduction than the method. This improvement is expected; after all, the only difference between the and methods is that that latter looks more frequently at the lattice basis and takes smaller ``steps'' while performing a reduction. However, as the dimension of the lattice basis increased, the ratio of row moves required by to row moves required by also increased. By the time n = 50, the method required approximately 30% more reduction steps to reduce test lattices than the method did. The performance of the method fell somewhere between that of and for test lattices with . This is somewhat surprising in and of itself, since the capability of the method to consider future reduction is severely limited. This unexpected performance may be an artifact of our method of generating test lattices; we only performed n^{2} row operations on the initial uppertriangular lattice basis and used only transitions to modify the lattice basis. This could account for the relatively good performance of the method, and also the differences between the and methods. The experiments summarized in Table 2.2 do not indicate that any one of the tested methods consistently performs better than the others. Without any clear indication that one method would yield significantly better results (especially as ), we were reluctant to use any method in Seysen's algorithm except the one implicitly defined by Seysen himself. For special types of lattices, it is probably worthwhile to compare these methods again. It may be that increased performance by the method more than offsets the increase in the number of row operations. However, for our experiments in subsequent sections (and the subset sum lattices of Chapter 3) we continued to use the form of Seysen's algorithm.
The previous sections detailed small tests which compared the relative
performance of Seysen's algorithm when a few minor changes were made to its
structure. In this section and the following one we investigate more fully the
performance of the algorithm itself as a reduction technique for selfdual
lattice bases and random integer lattices. Our next series of tests was
suggested by J. C. Lagarias (personal communication) to test the
selfdual reduction performance of the algorithm. Let
be the lattice basis consisting of the following basis vectors:
If
is represented as a matrix with
as the
column, then we have:
Basis
has the property that
grows exponentially with n, but rather slowly for small dimensions.
n 
L_{10} 
S(A) 
L_{10}^{*} 
L_{10}' 
S(A') 
L_{10}^{*}' 
# Steps 
5 
0.30 
7.36e+00 
0.50 
0.30 
6.59e+00 
0.30 
3 
10 
1.10 
3.65e+01 
3.80 
1.10 
1.61e+01 
1.00 
12 
15 
2.30 
1.88e+02 
10.60 
2.10 
2.78e+01 
1.90 
29 
20 
3.70 
1.00e+03 
21.10 
3.40 
4.28e+01 
3.10 
45 
25 
5.30 
5.37e+03 
35.20 
4.90 
5.80e+01 
4.20 
70 
30 
7.10 
2.89e+04 
53.00 
6.30 
7.88e+01 
6.20 
135 
35 
9.10 
1.55e+05 
74.40 
8.20 
1.03e+02 
8.00 
177 
40 
11.20 
8.35e+05 
99.50 
10.40 
1.30e+02 
9.90 
240 
45 
13.40 
4.49e+06 
128.30 
13.10 
1.72e+02 
12.80 
363 
50 
15.70 
2.42e+07 
160.70 
15.80 
2.32e+02 
16.90 
509 
55 
18.20 
1.30e+08 
196.70 
18.60 
2.62e+02 
18.30 
698 
60 
20.70 
6.99e+08 
236.40 
22.30 
3.53e+02 
22.50 
772 
65 
23.30 
3.76e+09 
279.70 
25.00 
4.01e+02 
25.70 
1067 
70 
25.90 
2.02e+10 
326.80 
26.40 
4.40e+02 
28.10 
1467 
75 
28.70 
1.09e+11 
377.40 
32.70 
6.93e+02 
36.60 
1702 
80 
31.50 
5.85e+11 
431.70 
31.90 
6.00e+02 
35.70 
2123 
85 
34.40 
3.15e+12 
489.70 
35.70 
7.25e+02 
40.40 
2775 
90 
37.30 
1.69e+13 
551.30 
39.70 
8.50e+02 
45.40 
3345 
95 
40.30 
9.10e+13 
616.60 
44.10 
1.03e+03 
51.00 
4839 
100 
43.30 
4.89e+14 
685.60 
49.00 
1.20e+03 
55.50 
6363 
105 
46.40 
2.63e+15 
758.10 
50.80 
1.19e+03 
56.70 
8303 
Tests were performed on
lattices with
using Seysen's basis reduction algorithm for dimensions
.
Based on the experimental results of Sections 2.2.1
and 2.2.2
above, we used a greedy selection method to choose which pairs of vectors to
reduce on each iteration of the algorithm, and
was allowed to be any integer value during all stages of the algorithm. The
results of these tests are given in Table 2.3.
For each test lattice, the following information is given:
n: The dimension of the lattice.
L_{10}: before reduction.
S(A): The Seysen measure of before reduction.
L_{10}^{*}: before reduction.
L_{10}': after reduction.
S(A'): The Seysen measure of after reduction.
L_{10}^{*'}: after reduction.
# Steps: The number of row moves performed during the reduction.
The exponential growth of
may be easily seen by looking at the rate of growth of the L_{10}^{*}
column in the tables. Remember that L_{10}^{*} is the sum
of the base 10 logarithms of the lengths of the dual basis vectors. This sum
grows at least linearly with respect to n; thus, the
grow exponentially in n.
For the
lattice Seysen's basis reduction algorithm yields little improvement in the
vector lengths
.
Indeed, for some values of n we have
L_{10} < L_{10}'. This is not the case, though,
for the dual lattice; Seysen's reduction algorithm greatly decreases the lengths
of the vectors in the dual basis. When the algorithm completes, we have
and the lengths of the vectors in the prime and dual lattice bases are
comparable. Figure 21
shows graphically the improvement made by Seysen's algorithm to
.
The results obtained from application of Seysen's algorithm to
lattices are quite promising. The algorithm was able to significantly reduce the
lengths of the dual basis vectors
without significantly increasing the lengths of the basis vectors for
themselves. In fact, the resulting primal and dual bases have basis vector
lengths which are comparable. Certainly this suggests that Seysen's algorithm is
a viable technique for applications in which we wish to simultaneously reduce a
lattice and its dual.
The reductions of
lattices tested application of Seysen's algorithm to a very narrow class of
lattices. From a cryptographic point of view (see Chapter 3
below), and in many other cases, our goal is to reduce random lattices with
integer basis vectors. In general, we do not know that our lattice conforms to
some specific structure; we are give only the basis vectors themselves. Thus, it
is appropriate to investigate the performance of Seysen's algorithm on randomly
generated integer lattices. When we considered in Section 2.2.1
the choice of a lazy or greedy selection method for Seysen's algorithm, we ran
tests on random integral lattices L with
of small dimension (
.
We utilize the same technique for generating random lattices as used before,
except now we consider lattices up to dimension 50. In addition to running
Seysen's algorithm over these test cases, each lattice was also reduced using
the LLL algorithm with
.
Table 2.4 summarizes the results of these
experiments. For each value of
,
,
twenty different test lattices were generated. The columns n, L_{10},
S(A), L_{10}^{*}, L_{10}', S(A'),
and
L_{10}^{*}' identify the same quantities as in Table 2.2
above. The column labeled ``# Steps (Seysen)'' reports the average number of
reduction steps (row moves) performed by Seysen's algorithm for each test
lattice. The average number of row operations performed by the LLL algorithm is
listed in the ``# Steps (Lovasz)'' column. (LLL reduction was not performed on
lattices with
because of the excessive amount of computer time required to obtain results).
n 
L_{10} 
S(A) 
L_{10}^{*} 
L_{10}' 
S(A') 
L_{10}^{*}' 
# Steps 
# Steps 
20 
82.37 

118.22 
0. (20) 
20. 
0. 
757.37 
4424.0 
25 
131.95 

192.93 
0. (20) 
25. 
0. 
1622.11 
12977.4 
30 
195.81 

287.24 
0. (20) 
30. 
0. 
3275.30 
32718.5 
31 
205.86 

308.06 
0. (20) 
31. 
0. 
3690.51 
38085.2 
32 
222.41 

323.66 
0. (11) 
1695.8 
0. 
3626.00 
44770.0 
33 
237.86 

348.19 
0. (5) 
86999.0 
0. 
3408.27 
53407.4 
34 
243.86 

358.86 
0. (1) 

0. 
3075.63 
60299.7 
35 
269.25 

390.02 
110.39 

112.57 
3036.95 
70047.2 
36 
287.16 

423.62 
138.11 

141.13 
2738.39 
80836.3 
37 
291.86 

438.94 
162.17 

167.33 
2400.10 
91491.5 
38 
310.35 

469.18 
175.52 

182.50 
2520.02 
103624.0 
39 
329.32 

500.89 
196.26 

203.87 
2555.72 
118338.0 
40 
343.84 

507.02 
216.88 

227.10 
2240.23 
132901.0 
45 
434.01 

656.67 
304.56 

323.53 
2369.90 
 
50 
541.20 

833.54 
402.80 

429.15 
2698.11 
 
The LLL basis reduction algorithm was able to reduce all tested lattice bases to
the ndimensional cubic lattice basis (i.e. B' = I_{n}),
which has Seysen measure zero. Seysen's algorithm performed similarly on all
lattice bases with .
(Values in parentheses in the L_{10}' column indicate the number
of lattice bases which were Seysenreduced to the ndimensional cubic
lattice.) For
the Seysen algorithm was able to completely reduce only some of the attempted
lattice bases; no lattice basis with
was ever reduced by the Seysen algorithm to I_{n}. The
degradation in the performance of Seysen's algorithm as n increases from
30 to 35 is quite surprising. Apparently, for these types of lattices, the
probability of reaching a lattice basis which is a local minimum of the Seysen
measure function increases substantially over that range. The LLL reduction
algorithm does not exhibit any decrease in performance, except for an overall
increase in the number of reduction steps required to convert the given lattice
basis into the ndimensional cubic lattice basis. Of course, the LLL
algorithm does take significantly longer to run than the Seysen algorithm, but
these tests suggest that Seysen's algorithm alone will not be sufficient to
reduce lattice bases in higher dimensions. We may need to combine Seysen's
algorithm with other lattice basis reduction techniques to efficiently reduce
large lattice bases. Alternately, it may be possible to use some heuristic
technique to reduce the probability of reaching a lattice basis which is a local
minimum of S(A), or to ``kick'' a Seysenreduced basis out of a
local minimum. The following section suggests a few possible methods which may
be employed when Seysen's algorithm fails to Sreduce a lattice basis and
stops at a local minimum of S(A).
We have seen above that for random, dense lattices L with ,
Seysen's algorithm starts to break down for
.
As n increases beyond 35, the number of local minima for the S(A)
function apparently increases, and thus the chance that Seysen's algorithm will
reduce lattice L to I_{n} decreases. As the number
of local minima increases, it is increasingly likely that in the process of
reducing lattice L the S(A) function (where A is the
quadratic form associated with L) will encounter one of these local
minima. As described above, Seysen's algorithm cannot tell whether it has
reached a local or a global minimum. Thus, it stops as soon as all possible
transformations cause S(A) to increase. For many types of
lattices, such as the sparse lattices generated by subset sum problems (see
Chapter 3),
Seysen's algorithm has performed sufficient work by the time it encounters a
local minimum that it is acceptable for it to stop. However, for many lattice
reduction problems Seysen's algorithm stops too soon. We would like the
algorithm to be able to detect local minima and overcome them. If one considers
the surface described by S(A) values, local minima are ``wells''
or ``depressions'' in the surface which are large enough to contain all points
reachable by performing one row move on the lattice. In this section we discuss
possible techniques for ``kicking'' the reduced lattice out of these wells;
methods of enhancing Seysen's algorithm so that it may consider other options
when it encounters a local minimum. There are many methods which could
conceivably be applied to a lattice to move it out of a local minimum; we
consider only some of these options. Section 2.3.1
considers an obvious possibility, which is to consider row moves involving 3 or
4 vectors at once (general nmoves are discussed in Section 2.4.1
below). In Section 2.3.2
we investigate simulated annealing and rapid quenching approaches to the
problem. Finally, Section 2.3.3
discusses using Hadamard matrices to permute the entire lattice basis.
As initially described in [38],
Seysen's basis reduction algorithm only considers row moves involving two basis
vectors. That is, we only consider moves of the form:
(These moves, of course, correspond to the set of transformation matrices
.)
However, there is no real theoretical reason to restrict ourselves to row moves
of the form given in Equation 2.16.
We consider here possibilities for row moves of the form
and their dual basis counterparts
Before we begin, it should be noted that there are practical reasons for not
considering row moves involving more than two vectors at any given time. First,
if we are using a greedy selection method to choose the vectors upon which to
operate, more work is required to choose the correct ntuple. (If we use
a lazy implementation this is less of a concern). Second, 2moves^{2.3}
exhibit a symmetry between the prime and dual lattice which is lost when we
consider nmoves with n > 2. When we perform a
transformation,
and
.
Thus we need not explicitly consider operations on the dual lattice, since every
dual lattice transformation has an equivalent transformation in the prime
lattice (with i,j swapped and
multiplied by 1). For nmoves with n > 2, however, this
duality is lost. The 3move
for example, has the following effects in the dual basis:
Thus, even if we use a lazy approach to choose which vectors to use in a row
operation, there are many more candidate operations which must be considered
since there is no longer any overlap between moves in the primal and dual
lattices. Calculating the best possible values of
for a given set of basis vectors is also more complicated as the number of
vectors involved in the move increases. As an example, let us consider the
computation required to choose
and
for the 3move
We assume without loss of generality that
i_{1} < i_{2} < j. Then we may
represent this transformation by a
transformation matrix, where:
Similar to Section 2.1.4
above, let us define
Now, we compute the partial derivatives of
with respect to
and ,
set them equal to 0, and solve for
and :
If we wish to implement a version of Seysen's algorithm which allows 3moves in
general, we must calculate six sets of (
)
values; one set for each of
Clearly including the six possible 3moves and the eight possible 4moves in
Seysen's algorithm is computationally expensive. However, there are reasons for
wishing to do so. When Seysen's algorithm reaches a local minimum of S(A)
for some lattice L it is reducing, it has reached a point where any
single row move increases S(A). By allowing the algorithm to look
at 3moves when it has run out of 2moves to perform, we increase the number of
configurations Seysen's algorithm must investigate before it gives up. It is
quite possible that one or more configurations which are 3move attainable but
not 2move attainable will have Seysen measure smaller than S(A).
These reduced lattices would then permit the algorithm to move out of the local
minimum and continue its reduction steps. We added routines to our
implementation of Seysen's basis reductions algorithm to implement three and
fourvector row operations. In all cases one vector was designated the
``target'' vector and integer multiples of the other two or three vectors were
added to the target. We did not notice any significant improvement in the
performance of the algorithm on random integer lattices of determinant 1 when
these additional moves were allowed to occur on any iteration of the algorithm.
In some cases, the greedy selection scheme actually performed worse when allowed
to use 3moves and 4moves; usually this decrease in performance occurred
because the algorithm ``jumped ahead'' too quickly by using the 3move and would
have done better by using a sequence of 2moves. Three and fourvector
operations were helpful, however, when a lattice reduction reached a local
minimum. In many of these cases a few 3moves (or 4moves, if considered)
existed which would carry the lattice out of the local minimum and allow the
algorithm to resume processing. Given these experiences and the increased
complexity required to operation on more than two vectors at a time, we would
suggest using nmoves when n > 2 only to move the lattice being
reduced out of a local minimum.
Many combinatorial optimization problems have been successfully attacked using simulated annealing, which was initially developed independently by [10,21]. Simulated annealing approaches resemble local optimum algorithms, except that a random component is introduced which allows occasional ``uphill'' moves (moves which worsen the current solution to the problem according to a cost schedule). As simulated annealing methods have been successfully applied to a wide variety of problems, it seems reasonable to consider adding simulated annealing techniques to Seysen's algorithm in the hope of reducing the number of lcoal minima which cause the algorithm to stop before reaching a global minimum. Modifying Seysen's algorithm to work along the lines of a simulated annealing approach would not be difficult. In the implementation of the algorithm, we simply need to accept row moves which increase the Seysen measure of the lattice basis. The probability of accepting a move which increases S(A) will depend upon the temperature of the reduced lattice, which starts high and decreases according to some cooling schedule and the reduction proceeds. It thus remains to specify the initial temperature of a lattice basis, the probability (as a function of temperature) of accepting a row move which increases S(A), and a cooling schedule which describes how temperature decreases with time/reduction steps. Another technique, based on physical systems, for solving combinatorial optimization problems is the rapid quenching approach. Simulated annealing slowly reduces the temperature of the solution, thus gradually reducing the probability of accepting a move to a higher energy/cost state. Rapid quenching, on the other hand, quickly reduces the temperature in the model, bringing the system to a minimum quickly. The system is then reheated to a temperature lower than the initial temperature, and the process is repeated. Seysen's algorithm itself can be viewed as one iteration of a rapid quenching process. The heated system is the initial lattice basis, and the algorithm itself, by greedily reducing the Seysen measure of the lattice basis, decreases the temperature of the system. We modified our implementation of Seysen's algorithm to simulate multiple rapid quenching iterations. When a lattice basis reached a minimum of the Seysen measure function and no single twovector row move could decrease S(A), a randomization function was performed on the lattice to ``heat'' it and Seysen's algorithm was subsequently applied to the heated lattice basis. Our randomizing function chose a linear number of pairs of vectors , and (with equal probability) either added to or subtracted from . (This is the same randomizing operation used previously to generate random integer lattices, except that we perform O(n) randomizations here instead of O(n^{2}) as was done before.) Multiple iterations of the heating/Seysenreducing process did successfully reduce lattice bases more than Seysenreduction alone, although it is unclear as to how much benefit can be gained from repeated applications of this process.
Our third and last suggestion for moving lattice bases out of local minima was suggested by Matthijs Coster (personal communication). Instead of randomly permuting the lattice basis as random quenching does, Coster suggests using a Hadamard matrix H to transform a Seysenreduced lattice basis B into lattice basis . Recall that matrix H is a Hadamard matrix if it satisfies the following two properties:
Each entry h_{i,j} of H is either +1 or 1.
If are the rows of H, then for all i,j with , .
It is not difficult to show that if H is an
Hadamard matrix, then n = 2 or
([1],
2.21 Exercise 10). Now, consider the lattice basis B' obtained by
multiplying B by a Hadamard matrix H. (If
we may consider B and the corresponding lattice L to be
sublattices of an n'dimension space with
.)
Each basis vector in B' is a linear combination of all the basis vectors
in B, but no two B' vectors have similar constructions, since
and
differ in
coordinates if .
The basis vectors in B' will have lengths
times the lengths of the basis vectors in B, so while we obtain a good
randomization of the lattice, the lengths of the basis vectors are still
manageable. We should point out that the matrix H is not a linear
transformation matrix;
.
This means that the lattice generated by B is not the same lattice
generated by B'. However, all ndimensional Hadamard matrices H_{n}
satisfy:
Thus,
and the net result of the operation is to scale B (and the associated lattice L) by a factor of n. Thus we can divide out the factor of n and we are left with the lattice L we started with. So, our plan of attack should be as follows. When Seysen's algorithm stops and reports that lattice basis B is a local minimum of S(A), create where H is a Hadamard matrix. Now, Seysenreduce lattice basis B' until a local minimum is reached. Then compute . Finally, Seysenreduce basis B'', producing basis B'''. Bases B and B''' describe the same lattice L. Note that there is no guarantee that S(A''') < S(A), where A,A''' and the quadratic forms associated with B,B''' respectively. Further study is required before we may conclude whether Hadamard permutations provide a reasonable method for ``kicking'' lattice basis B.
The description Seysen gave in [38]
of his algorithm was only an outline of a lattice basis reduction technique. We
have tried in this chapter to give both theoretical and empirical reasons for
the choices made in implementing Seysen's algorithm. However, we have only
touched upon a few of the many possible combinations of techniques. As the next
chapter shows, these choices are effective as reducing lattice bases derived
from subset sum problems. For other lattices, their effectiveness may be in
question. We briefly mention here some of the other possible choices for the
various components of Seysen's algorithm.
Section 2.3.1
above discussed the possibility of extending Seysen's algorithm to consider row
operations involving three and four vectors at once. It is possible to extend
these operations to encompass arbitrary kmoves where integer multiples
of k1 basis vectors are added to another basis vector. For fixed k,
let
be the target basis vector (the vector to be modified) and let
be the basis vectors to be added to
in multiples of
respectively. Then, after the row move, we will have:
Now, we may solve for the new values of the quadratic forms A and A^{*}
after the row move has occurred. In A, the only value that changes is a_{j,j}.
Its new value is:
(2.14) 
In the dual lattice quadratic form A^{*}, the values
a_{im,im}^{*}
change for
.
Their new values are:
(2.15) 
If we compute ,
the change in S(A) resulting from this row move, we find that:
Thus, for all
we have:
We may thus compute formulae for all for if we solve the simultaneous system of equations obtained by setting the k1 derivatives defined in Equation 2.21 equal to zero. Of course, we still must solve the problem of finding optimal integer values for the . For the 2move case we showed that was the best integer choice for . It is not clear that rounding will work in the kmove case. The real values derived for the may only indicate some range of integer values which need to be searched.
Seysen's original implementation of his basis reduction algorithm used a ``lazy'' approach for choosing pairs of basis vectors to reduce. Pairs of integers were searched in lexicographic order until a suitable row move involving and was found. We have presented above empirical evidence which favors a ``greedy'' approach, even when the extra computation time required to implement the ``greedy'' method is considered. Selection methods other than the ``greedy'' and ``lazy'' approaches were not considered in our experiments, but are certainly possible. For example, in addition to taking into account the reduction in S(A) which will result from a row move, we might also wish to consider the other row moves which will be blocked by performing this move. That is, if is added to , the potential S(A) reductions of all other row moves which involve either or will be modified. Perhaps we should choose row moves so that the moves they block have minimum S(A) reduction potential. We could combine this idea with the ``greedy'' method; selecting a row move with the greatest difference between the amount it reduces S(A) and the average S(A) reduction of all the moves it blocks.
In Section 2.2.2 above we looked at the effect of placing restrictions on the possible values of on the performance of Seysen's algorithm. In particular, was allowed either to be any integer value, or to only take on the values . We found that the algorithm worked slightly better if row moves were chosen with but only moves with were actually performed, probably because the changes made to the lattice basis on any single row move are smaller. We pay for the improved performance, however, though an increase in the running time of the overall algorithm, as it takes more row operations with the restriction in place to add a large integer multiple of one basis vector to another basis vector. As an example of other possible methods of choosing or restricting values, consider the following set of restrictions:
When choosing a pair of vectors for a row move, may take on any integer value.
When the row move is actually performed, if use the largest power of two strictly less than (unless , in which case should be used). If use the smallest power of two strictly greater than (again, unless , in which case 1 should be used).
We may abbreviate this set of conditions as . What we are doing is computing the best possible value of , but instead of performing one row move to compute , we perform a logarithmic number of moves. In this way we might be able to combine the benefits of the approach (fast running time) and the approach (better overall performance). This approach has not been tested, and judging from the relative differences noticed between the and cases is not likely to produce very large changes in reduction performance. However, it is an example of other possible restrictions which could be tried.
Section 2.1.3
above gave reasons for using functions of the product terms
.
In particular, the function
was selected as the Seysen measure function because it yielded a closed form
solution for the optimal value of
given i and j. However, other functions could certainly be
employed as the method of comparing different lattice bases. In this section we
briefly describe how Seysen's algorithm would have to be modified to accommodate
another measure function. We restrict our attention to versions of Seysen's
algorithm which use only row moves involving two basis vectors (i.e.
).
Recall that the formula in Equation 2.9
for the optimal choice of
was derived by maximizing the change in the Seysen measure function caused by a
row move involving two particular basis vectors. In the Seysen measure function
is changed, the only direct impact it will have upon the operation of the
algorithm is that the optimal value of
for basis vectors
will be computed in a different manner. In [38]
Seysen mentions two possible replacements for the S(A) function:
Replacing S(A) with S_{1}(A) implies that
our choice of
must minimize:
Solving
yields an extremely complex expression for .
Similar results occur when we try to substitute S_{2}(A)
for S(A). In both cases, no simple closedform solution for
exists as was the case with S(A). It may be still be possible to
utilize measure functions in Seysen's algorithm with no simple closedform
solution for
if we are willing to sacrifice some performance. If the range of possible
integer
values is bounded, for given i and j we can compute
for all possible
values in the permitted range. The
which provides the greatest change may then be selected. The cost of this
procedure is that we can no longer guarantee that the maximal
for a pair of basis vectors
may be found in constant time. If the range of
values to consider is usually small, then we will probably notice little more
than a linear slowdown in the running time of the algorithm. For large ranges of
possible
values, further heuristics might be applied, such as only considering
values which are near a power of two. In our experiments we noticed that large
values tended to occur only during the first few row reduction performed by
Seysen's algorithm. After this initial burst in reduction of S(A)
row moves tended only to involve small integer
values; it was quite rare to find
.
If similar conditions occur for the lattice bases in question, it is probably
reasonable to use a more complex measure function than S(A) and
use a small exhaustive search over a bounded range of possible
values to find the optimal
coefficient for a row move.
T. M. Apostol, Calculus, Vol. II, New York: John Wiley & Sons (1969).
T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, Graduate Texts in Mathematics 41, New York: SpringerVerlag (1976).
D. H. Bailey, Comparison of two new integer relation algorithms, manuscript in preparation.
D. H. Bailey, MPFUN: A Portable High Performance Multiprecision Package, NASA Ames Research Center, preprint.
P. van Emde Boas, Another NPcomplete partition problem and the complexity of computing short vectors in a lattice, Rept. 8104, Dept. of Mathematics, Univ. of Amsterdam, 1981.
E. F. Brickell, Solving low density knapsacks, Advances in Cryptology, Proceedings of Crypto '83, Plenum Press, New York (1984), 2537.
E. F. Brickell, The cryptanalysis of knapsack cryptosystems. Applications of Discrete Mathematics, R. D. Ringeisen and F. S. Roberts, eds., SIAM (1988), 323.
E. F. Brickell and A. M. Odlyzko, Cryptanalysis: a survey of recent results, Proc. IEEE 76 (1988), 578593.
Brun, Algorithmes euclidiens pour trois et quatre nombres, Congr. Math. Scand., Helsinki, 4564.
V. Cerny, A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm, J. Optimization Theory and Appl. 45, 4151.
B. Chor and R. Rivest, A knapsacktype public key cryptosystem based on arithmetic in finite fields, Advances in Cryptology: Proceedings of Crypto '84, SpringerVerlag, NY (1985), 5465. Revised version in IEEE Trans. Information Theory IT34 (1988), 901909.
M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr, An improved lowdensity subset sum algorithm, Advances in Cryptology: Proceedings of Eurocrypt '91, D. Davies, ed., to appear.
Y. Desmedt, What happened with knapsack cryptographic schemes?, Performance Limits in Communication, Theory and Practice, J. K. Skwirzynski, ed., Kluwer (1988), 113134.
A. M. Frieze, On the LagariasOdlyzko algorithm for the subset sum problem, SIAM J. Comput. 15(2) (May 1986), 536539.
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman and Company (1979).
J. Hċstad, B. Just, J. C. Lagarias, and C. P. Schnorr, Polynomial time algorithms for finding integer relations among real numbers, SIAM J. Comput. 18(5) (October 1989), 859881.
J. Hċstad and J. C. Lagarias. Simultaneously good bases of a lattice and its reciprocal lattice, Math. Ann. 287 (1988), 163174.
D. He, Solving lowdensity subset sum problems with modified lattice basis reduction algorithm, Northwest Telecommunication Engineering Institute (Xi'an, China), preprint.
A. Joux and J. Stern, Improving the critical density of the LagariasOdlyzko attack against subset sum problems, to be published.
R. Kannan, Improved algorithms for integer programming and related lattice problems, Proc. Symp. Theory. of Comp. (1983), 193206.
S. Kirkpatrick, C. D. Gelatt Jr. and M. P. Vecchi, Optimization by simulated annealing, Science 220 671680.
D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed., AddisonWesley 1981.
A. Korkin and G. Zolotarev, Sur les formes quadratiques, Math. Ann 6, 366389.
A. Korkin and G. Zolotarev, Sur les formes quadratiques, Math. Ann 11, 242292.
J. C. Lagarias, Point lattices, manuscript in preparation.
J. C. Lagarias and A. M. Odlyzko, Solving lowdensity subset sum problems, J. Assoc. Comp. Mach. 32(1) (January 1985), 229246.
A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515534.
J. E. Mazo and A. M. Odlyzko, Lattice points in highdimensional spheres, Monatsh. Math. 110 (1988), 4761.
H. Minkowski, Diskontinuitsbereich fur arithmetic Aquivalenz, J. reine Angew. 129, 220224.
J. R. Munkres, Analysis of Manifolds, Redwood City: AddisonWesley (1988).
A. M. Odlyzko, The rise and fall of knapsack cryptosystems, Cryptology and Computational Number Theory, C. Pomerance, ed., Am. Math. Soc., Proc. Symp. Appl. Math. 42 (1988), 7588.
M. Pohst, A modification of the LLL reduction algorithm, J. Symb. Comp. 4 (1987), 123127.
S. Radziszowski and D. Kreher, Solving subset sum problems with the L^{3} algorithm, J. Combin. Math. Combin. Comput. 3 (1988), 4963.
C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theoretical Computer Science, 53 (1987), 201224.
C. P. Schnorr, Factoring integers and computing discrete logarithms via diophantine approximation, Advances in Cryptology: Proceedings of Eurocrypt '91, D. Davies, ed., to appear.
A. Schönhage, Factorization of univariate integer polynomials by diophantine approximation and by an improved basis reduction algorithm, International Colloquium on Automata, Languages and Programming (ICALP '84), J. Paredaens, ed., Lecture Notes in Computer Science 172, SpringerVerlag, NY (1984), 436447.
J.P. Serre, A Course in Arithmetic, Graduate Texts in Mathematics 7, New York: SpringerVerlag (1973).
M. Seysen, Simultaneous reduction of a lattice basis and its reciprocal basis, to be published.