.nr Pt 1
.fp 4 M2
.fp 5 M6
.EQ
delim $$
gsize 11
define RR % font 5 R %
define mE % member %
define xs % x sub %
define as % a sub %
define smf % sum from %
define le % ^<=^ %
define ge % ^>=^ %
define dd % "..." %
define bs % b sub %
define spr % sup prime %
define || % | back 25 | %
.EN
.S 11
.am DE
.ls 2
.sp
..
.ds HF 3 3 3
.ds HP 11 11 11
.TL
The Rise and Fall of Knapsack Cryptosystems
.AU "A. M. Odlyzko" AMO MH 11211 7286 2C-355
.AS 1
.ls 2
.P
Cryptosystems based on the knapsack problem were among the first public key systems to be invented, and for a while were considered to be among the most promising.
However, essentially all of the knapsack cryptosystems that have been proposed so far have been broken.
These notes outline the basic constructions of these cryptosystems and attacks
that have been developed on them.
.ls 1
.AE
.MT 4
.ls 2
.H 1 "Introduction"
The \f2knapsack\f1 or \f2subset-sum problem\f1 is to determine, given positive integers (or weights)
$as 1 ,^dd ,^as n$, and $s$, whether there is a subset of the $as j$ that sums to $s$.
This is equivalent to determining whether there are variables $xs 1 ,^dd ,^xs n$ such that
.DS 2
.EQ (1.1)
smf j=1 to n ~ xs j ^as j ~=~ s ^, ~~~~~xs j ^mE^ "{"0,^1"}" ~~roman {"for all"} ~~ j ^.
.EN
.DE
If one thinks of $s$ as the capacity of a knapsack and the $as j$
as the sizes of various items, then the question is whether the knapsack
can be filled exactly
by some collection of those items.
.P
The knapsack problem is stated above in its \f2feasibility recognition form\f1, namely
we ask only whether (1.1) is solvable.
However, if this problem can be solved efficiently in general, then actual solutions can also be obtained fast.
For example, if we know there is a solution, we can find out whether there is a solution with $xs 1 =1$ by testing whether there is a solution to
.DS 2
.EQ
smf j=2 to n ~ xs j ^as j ~=~ s^-^ as 1 ^, ~~~~~
xs j ^mE^ "{"0,^1 "}" ^, ~~~~2 le j le n ^.
.EN
.DE
If there is no such solution, we know that $xs 1 =0$
for all solutions to the original problem.
Once $xs 1$ is determined, we can go on and determine $xs 2 ,^xs 3 ,^dd$, one by one,
and thus find at least one solution to (1.1).
.P
The general knapsack problem is known to be $NP$-complete [13], and so it is thought to be quite hard.
Being $NP$-complete means that if a polynomial time algorithm existed, there would also be polynomial time algorithms for all problems in the computational complexity class $NP$.
This is thought to be unlikely, since this category includes many combinatorial optimization problems that have been investigated intensively over several decades, and for which no fast algorithms are known.
This is of course a very subjective evaluation, since no good
lower bound proofs are known for any of the problems
that are $NP$-complete.
.P
To determine whether (1.1) has a solution, and if so, to find it, one can compute all the $SIGMA ^x sub j ^a sub j$ with $x sub j^member^"{"0,^1"}"$, but that takes on the order of
$2 sup n$ steps.
(We are assuming here that the $a sub j$ are not too large, and will not be too precise about counting operations.)
A better method is to compute
.DS 3
.EQ
S sub 1 mark ~=~ left { sum from j=1 to {left floor n/2 right floor} ^x sub j ^a sub j^:~~x sub j ^=^0 ~~roman or ~~ 1 ~~roman {"for all"} ~~ j right } ^,
.EN
.sp
.EQ
S sub 2 lineup ~=~ left { s ~-~ sum from {j^>^ left floor n/2 right floor} ^x sub j ^a sub j^:~~x sub j ^=^0 ~~roman or ~~ 1 ~~roman {"for all"} ~~ j right } ^,
.EN
.DE
(this takes on the order of $2 sup n/2$ operations), sort each of the sets $S sub 1$ and $S sub 2$ (in about $n2 sup n/2$ operations), and then scan $S sub 1$ and $S sub 2$, looking for a common element (about $2 sup n/2$ operations again).
An element common to $S sub 1$ and $S sub 2$ arises precisely when there is a solution to (1.1);
if
.DS 3
.EQ
y mark ~=~ sum from j=1 to {left floor n/2 right floor} ~ x sub j ^a sub j
.EN
.sp
.EQ
lineup ~=~ s ^-^ sum from {j^>^ left floor n/2 right floor} ^x sub j ^a sub j ^,
.EN
.DE
then
.DS 2
.EQ
s ~=~ sum from j=1 to n ~ x sub j ^a sub j ^.
.EN
.DE
The entire procedure takes on the order of $n2 sup n/2$ operations (but also about $2 sup n/2$ storage space, which may sometimes be prohibitive!).
Surprisingly enough, this is still the fastest algorithm known for the general knapsack problem.
.P
The basic idea of knapsack cryptosystems is to use a public set of weights $as 1 ,^dd ,^as n$ generated by $A$, say, to encode a message $( xs 1 ,^dd ,^xs n )$, $xs j ^mE^ "{"0,^1"}"$ for $1 le j le n$, as
.DS 2
.EQ (1.2)
s ~=~ smf j=1 to n ~ xs j ^as j ^.
.EN
.DE
The message that would be transmitted to $A$ would then be $s$.
An eavesdropper would see $s$, and would know $as 1 ,^dd ,^as n$, since those are public, but in order
to recover the message $(x sub 1 ,^dd ,^x sub n )$, would have to solve the (apparently intractable) knapsack problem.
.P
The difficulty with the basic scheme outlined above is that while the eavesdropper is faced with having to solve a hard knapsack problem, so is the intended receiver $A$.
That makes the scheme impractical, unless $A$ possesses tremendously
more computing power than any possible eavesdropper.
(An assumption like that is completely unacceptable, since a basic criterion is that the cryptosystem should be very easy to use, and the cryptanalysis of it ought to be very hard.)
Thus to use the knapsack problem for information transmission, it is necessary to make it possible for the intended receiver $A$ to decode messages efficiently.
There are some kinds of knapsack problems that are easy to solve.
For example, if $as j ^=^ 2 sup j-1$, $1 le j le n$, then
.DS 2
.EQ
s ~=~ smf j=1 to n ~ xs j ^2 sup j-1 ^,
.EN
.DE
and the $xs j$ are just the digits in the binary representation of $s$.
More generally, if the $as j$ form a
\f2superincreasing sequence\f1, so that
.DS 2
.EQ (1.3)
as j ~>~ smf i=1 to j-1 ~ as i ^, ~~~~~2 le j le n ^,
.EN
.DE
then the knapsack problem is easy to solve;
$xs n =1$ if and only if
.DS 2
.EQ
s ~>~ smf j=1 to n-1 ~ as j ^.
.EN
.DE
Once we find that $xs n =y$, say, we are faced with the smaller knapsack problem of determining
$xs 1 ,^dd ,^xs n-1$ such that
.DS 2
.EQ
s ^-^ y ^as n ~=~ smf j=1 to n-1 ~ xs j ^as j ^, ~~~~~~xs i ^mE^"{"0,^1"}" ^,
~~~~~~1^<=^j^<=^n-1 ^,
.EN
.DE
and thus we can retrieve the entire message $( xs 1 ,^dd ,^xs n )$ recursively.
.P
The use of a superincreasing sequence $as 1 ,^dd ,^as n$ of public weights would make it easy for the receiver $A$ to read messages, but it would not prevent the eavesdropper from doing so as well.
The basic idea of all knapsack public key cryptosystems is to start with a knapsack $bs 1 ,^dd ,^bs n$ that is easy to
solve and then transform it into the public knapsack $as 1 ,^dd ,^as n$ by a process that conceals the structure of the knapsack, so that the public
weights $as 1 ,^dd ,^as n$ will appear to have no special structure and will hopefully leave the cryptanalyst baffled.
At the same time, the designer of the system will be in a position to reverse the concealing transformation and will only have to solve the easy knapsack.
.P
The most famous transformation of an easy secret knapsack into a seemingly more complicated public one is the modular multiplication used by Merkle and Hellman [21] in their basic knapsack cryptosystem.
The receiver, who constructs the system to allow others to send information to her,
starts with a superincreasing knapsack $bs 1 ,^dd ,^bs n$ with
.DS 2
.EQ (1.4)
bs 1 ~approx ~ 2 sup n ^, ~~ bs j ~>~ smf i=1 to j-1 ~bs i ^, ~~
2 le j le n ^, ~~ bs n ~approx ~ 2 sup 2n ^.
.EN
.DE
(Some of the reasons for this choice of parameters will be presented in Section\ 2.)
She then chooses positive integers $M$ and $W$ with
.DS 2
.EQ (1.5)
M ~>~ smf j=1 to n ~ bs j ^, ~~~~~(M,^W) ~=~ 1 ^,
.EN
.DE
and computes
.DS 2
.EQ (1.6)
as j spr ~==~ bs j ^W ~( roman mod ~M ) ^, ~~~~~0 ^<^ as j spr ^<^M ^.
.EN
.DE
We cannot have $a sub j sup prime = 0$, since $(M,^W) =1$ and $M ^>^ b sub j$.
Then she selects a permutation $pi$ of $"{"1,^dd ,^n "}"$ and defines
.DS 2
.EQ (1.7)
as j ~=~ as {pi (j)} spr ^, ~~~~~1 le j le n ^.
.EN
.DE
The $as j$ form the public weights, while the $bs j$, $M ,^W$, and the permutation $pi$ are kept secret.
.P
A message $( xs 1 ,^dd , ^xs n )$ is encoded as
.DS 2
.EQ (1.8)
s ~=~ smf j=1 to n ~ xs j ^as j ^.
.EN
.DE
The receiver, knowing $M$ and $W$,
computes
.DS 2
.EQ (1.9)
c ~==~ s ^W sup -1 ~( roman mod ~ M ) ^, ~~~~~ 0 le c ^<^ M ^,
.EN
.DE
where $W sup -1$ denotes the multiplicative inverse of $W$ modulo $M$.
By (1.6)-(1.8),
.DS 3
.EQ
c mark ~==~ smf j=1 to n ~ xs j ^as j ^W sup -1 ~( roman mod ~ M )
.EN
.sp
.EQ (1.10)
lineup ~==~ smf j=1 to n ~ xs j ^as {pi (j)} spr ^W sup -1 ~( roman mod ~ M )
.EN
.sp
.EQ
lineup ~==~ smf j=1 to n ~ xs j ^bs {pi (j)} ~( roman mod ~ M ) ^.
.EN
.DE
Since $M ^>^ SIGMA ^bs j$,
the condition $0^<=^c^<^M$ implies
.DS 2
.EQ (1.11)
c ~=~ smf j=1 to n ~ xs j ^bs {pi (j)} ^.
.EN
.DE
After these operations the receiver is faced with the knapsack problem (1.11), which is easy to solve, since the $bs j$ form an increasing sequence.
.P
The paragraphs above describe the basic, or \f2singly-iterated
Merkle-Hellman cryptosystem\f1.
A variation on it is the \f2multiply-iterated Merkle-Hellman cryptosystem\f1,
in which the easy (secret) knapsack is disguised through a series of modular multiplications;
we let $M sub 1 ^=^ M$, $W sub 1 ^=^W$,
$a sub j sup (0) ^=^b sub j$,
$a sub j sup (1) ^=^ a sub j sup prime$,
and construct a sequence of modulus, multiplier, and weight combinations by choosing iteratively $M sub k ,^W sub k$, to be positive integers such that
$(M sub k ,^W sub k )^=^1$,
.DS 3
.EQ
M sub k mark ~>~ sum from j=1 to n ~ a sub j sup (k-1)^,
.EN
.sp .5
.nr Eq 1
.EQ "and define"
~~
.EN
.sp .5
.nr Eq 0
.EQ
a sub j sup (k) lineup ~==~ a sub j sup (k-1) ^W sub k ~ ( roman mod ~ M sub k ) ^.
.EN
.DE
This kind of scrambling operation,
when performed a few times,
seems to conceal the original design
even more effectively than the basic (singly-iterated) scheme does.
.P
The Merkle-Hellman knapsack cryptosystems, as well as various other ones that were proposed,
have the attractive feature that they can be run at the high speeds.
Classical secret key cryptosystems, such as the Data Encryption Standard (DES), when implemented with special purpose chips, can be run at speeds
of tens of millions of bits per second, and even in software on modest size machines can encrypt on the order of $10 sup 5$ bits per second.
The RSA system is very slow by comparison.
It was thought for a long time that a modulus of about 500 bits was quite
secure. (The initial challenge cipher proposed by Rivest, Shamir, and Adleman involved a modulus of about 430 bits.)
At that size, though, even the best existing special purpose chips can only encrypt at the rate of $10 sup 4$ or
$2 ^times^10 sup 4$ bits per second, and software implementations are limited to something on the order of $10 sup 2$ bits per second.
Thus the RSA system is about
100 to 1000 times slower than classical cryptosystems.
.P
The Merkle-Hellman knapsack cryptosystems seemed to offer the possibility of much higher speed.
For $n ^approx^100$ (which seemed a reasonable parameter, since the best algorithms known for solving the knapsack problem require on the order of $2 sup n/2$ operations),
the singly-iterated Merkle-Hellman system can be more than 100 times
faster than RSA (with modulus of about 500 bits), whether
hardware or software implementations were used, and thus can rival
classical secret key systems in speed.
This speed advantage is due to a small extent to dealing with smaller numbers (200 vs. 500 bits) but mostly to having to do only one modular multiplication,
as opposed to over 500 for RSA.
There is a slight disadvantage in that twice the communication capacity is needed
($m$ bits is encoded into $approx ^2m$ bits, as against about $m$ bits for RSA), and the size of the public key is larger
($2n sup 2$ bits, which is about 20,000 for $n^approx^100$, as against 1000 bits for 500-bit RSA).
.P
The major question about knapsack public key systems has always concerned their security.
Some of the doubts have been very general, and apply to the RSA cryptosystem as well.
What if $P^=^NP$, and somebody discusses a wonderful new approach that solves all problems in $NP$ efficiently?
Even if $P^!=^NP$, what if most instances of the knapsack problem are easy to solve?
Since the theory of $NP$-completeness deals with the worst-case situation,
there is nothing to forbid this from happening, and many $NP$-complete problems are easy to solve on average, cf.\ [27].
Even if most instances of the general knapsack
problem are hard, how can one be certain that the cryptanalyst will not be able to deduce from the public knapsack what the construction method was?
.P
In addition to the general doubt about security of all public key
systems mentioned above,
several other doubts
were
raised that applied specifically to knapsacks and other systems based on $NP$-complete problems.
On the very abstract level, there was an interesting result of Brassard [2]
which says essentially that if breaking a cryptosystem is $NP$-hard, then
$NP^=^Co "-" NP$, which would be a very surprising complexity theory result.
Thus if $NP^!=^Co "-" NP$, then breaking the Merkle-Hellman cryptosystem cannot be $NP$-hard, and so is likely to be easier than solving the general knapsack problem.
.P
More specific concerns about the security of knapsack cryptosystems were based to the linearity of such schemes.
Reading Eq.\ (1.1) modulo\ 2, one obtains an equation for the $x sub j$ modulo\ 2, which provides a single bit of information about them.
(We can obviously assume that not all of the $a sub j$ are even, as in that case, which would correspond to a trivial equation, we could look at the knapsack with weights $a sub 1 fat / 2 ,^"...",^a sub n fat / 2$, etc.)
No one ever found a way to take advantage of this bit, but the fact that it could be determined was felt to be suspicious.
(Ideal cryptographic systems should reveal no information at all about the
plaintext message being transmitted.)
.P
In addition to the general suspicions mentioned above, a number of knapsack cryptosystems were broken
in the late 1970's.
The final fall of knapsack cryptosystems can be dated to Shamir's announcement
in the spring of 1982 of a polynomial time attack on the singly-iterated
Merkle-Hellman cryptosystem [26].
This was quickly followed by a string of attacks on other knapsack cryptosystems,
culminating in Brickell's attack on the multiply-iterated Merkle-Hellman system [4].
These attacks relied on the fact that the modular multiplication method does not disguise completely
the easy knapsack that is the basis of the construction.
.P
In addition to the attacks on specific knapsack systems that have been developed, there are two attacks on so-called
\f2low-density knapsacks\f1, namely those in which the weights $a sub j$ are large.
These attacks do not assume any particular structure in the knapsack.
They are due to Brickell [3] and Lagarias and Odlyzko [18], respectively.
As a result, both of the two basic fears about knapsack cryptosystems have been borne out;
their constructions can often be unraveled, and in addition,
many cases of the general knapsack problem can be solved efficiently.
.P
A large variety of knapsack cryptosystems have been shown to be insecure, most with the use of tools from
the area
of
diophantine approximation.
The paper [6] contains a survey of many of the systems that have been broken
as well as descriptions of some of the attacks.
For full details, the reader is advised to consult [6] and many
of the references contained there, such as [3,4,5,8,11,16,17,18,22,26].
The remainder of this paper is
devoted to a description of one each of the two kinds of basic attacks that have been used.
Section\ 2 describes the attack on the singly-iterated Merkle-Hellman cryptosystem.
This attack allows the cryptanalyst to read encrypted messages just about as fast as the designer of the
system can.
Section\ 3 describes one of the low-density attacks.
It is harder to carry out, but applies to a rich variety of knapsacks, not just the cryptographic ones.
.P
While most knapsack cryptosystems have been broken, there are a few that so far have resisted all attacks.
One of the most attractive of these is the Chor-Rivest system [7], which involves a combination of number theory
ideas and knapsacks.
It is described briefly in Section\ 4.
Other recent applications of knapsacks include [15].
The search for secure knapsacks continues both because of the attractively
high speed that knapsack systems offer, and because of the desire to have a wide
variety of cryptosystems available.
After all, factorization and discrete logarithm problems could turn out to be
efficiently solvable, and if that happened, it would be nice to have substitute systems available.
.H 1 "Basic Merkle-Hellman system"
This section shows how to break the basic Merkle-Hellman knapsack cryptosystem.
This attack was the first serious
cryptanalytic assault on knapsacks, and it led to the breaking of numerous other knapsack systems.
It is due to A. Shamir [26].
Many of the crucial observations about the weaknesses of the basic Merkle-Hellman system had been made earlier by Eier and Lagger [10] and
by Desmedt, Vandewalle, and Govaerts [9].
.P
Before describing the Shamir attack,
we will say a few words about the choice of parameters (1.4).
If some of the $b sub i$, and therefore also $M$, are large, then the knapsack will be inefficient, since $n$ bits of information will be
encoded into roughly $log sub 2 ^M$ bits.
On the other hand, it is dangerous to let any of the $b sub j$ be too small.
If we had $b sub 1 = 1$, say, then $a sub j = W$ for some $j$, and since the knapsack can be shown to be breakable if either $W$ or $M$ is revealed, one could try each of the $a sub j$ as a possible $W$ and thus compromise the system.
Therefore a reasonable compromise between efficiency and security seemed to be to select the parameters in (1.4).
.P
One could select $b sub i = c2 sup i-1$, $1^<=^i^<=^n$, for some
$c^approx^2 sup n$.
This choice would satisfy (1.4),
but it would yield a very insecure system.
The reason is that for $1^<=^j^<=^n-1$, we would have
.DS 2
.EQ
a sub j+1 sup prime ~=~ 2a sub j sup prime ~~~roman or ~~~
2 a sub j sup prime ^-^ M ^,
.EN
.DE
and each case would usually occur about $n/2$ times.
Therefore, by computing
.DS 2
.EQ
a sub i ^-^2a sub j ^, ~~~~1^<=^i,^j^<=^n ^,
.EN
.DE
we would obtain about $n/2$ occurrences of $-M$
among the $n sup 2$ differences, so we could deduce what $M$ is,
and this would
break the system.
Other approaches have also been preposed.
For example, one could take $b sub i = 2 sup i-1$, but hide this structure
by a double iteration of the modular multiplication method [14].
This construction, however, which is more secure than what was presented
above, was shown to be insecure by the author (unpublished) by the use of continued fractions.
The moral to be drawn from the above examples is that it is easy to construct knapsack cryptosystems
that seem attractive, yet are insecure.
This explains the generally high level of suspicion that experts have had
about knapsacks from the moment they were proposed.
.P
We now proceed to the description of the Shamir attack on the basic Merkle-Hellman system.
We assume that the secret knapsack weights $b sub 1 ,^"...",^b sub n$ satisfy (1.4), and that they are
transformed into the public weights $a sub 1 ,^"...",^a sub n$ via (1.6) and (1.7).
We let $U^==^ W sup -1~ ( roman mod~M )$, $0^<^U^<^M$.
By (1.6), we have
.DS 3
.EQ (2.1)
a sub j mark ~==~ b sub {pi (j)} ^W ~~~( roman mod ~ M ) ^,
.EN
.sp .5
.nr Eq 1
.EQ or
~~
.EN
.sp .5
.nr Eq 0
.EQ (2.2)
b sub {pi (j)} lineup ~==~ a sub j ^U ~~~ ( roman mod ~ M ) ^,
.EN
.DE
and this means that for some integer $k sub j$,
.DS 2
.EQ (2.3)
a sub j ^U ~-~ k sub j ^M ~=~ b sub {pi (j)} ^.
.EN
.DE
Hence
.DS 2
.EQ (2.4)
U over M ~-~ {k sub j} over {a sub j} ~=~ {b sub {pi (j)}} over {a sub j ^M} ^.
.EN
.DE
What this means is that all of the $k sub j / a sub j$ are close to $U/M$.
The cryptanalyst does not know $U,^M$, $pi$, the $k sub j$, or the $b sub j$, but does know the $a sub j$.
The problem now is to extract some information about all these unknowns
from the above remark about (2.4).
.P
From (1.4) we see, for example, that
.DS 2
.EQ (2.5)
b sub 1 ,~ b sub 2 ,~"...",~ b sub 5 ~<wig ~ 2 sup n ^.
.EN
.DE
Therefore, if we let $j sub i ^=^ pi sup -1 (i)$, then we obtain
.DS 2
.EQ (2.6)
left | ^U over M ^-^ {k sub j sub i} over {a sub j sub i} right | ~<wig~ {2 sup n} over {2 sup 4n} ~=~ 2 sup -3n ^, ~~~~1 ^<=^i^<=^5 ^,
.EN
.DE
and hence, subtracting the $i=1$ term from the others,
.DS 2
.EQ (2.7)
left | ^ {k sub j sub i} over {a sub j sub i} ^-^ {k sub j sub 1} over {a sub j sub 1} right | ~<wig~
2 sup -3n ^, ~~~~2 ^<=^i^<=^5 ^.
.EN
.DE
This, in turn, implies that
.DS 2
.EQ (2.8)
| k sub j sub i ^a sub j sub 1 ^-^ k sub j sub 1 ^a sub j sub i | ~<wig~ 2 sup n ^, ~~~~2^<=^i^<=^5 ^.
.EN
.DE
The inequalities (2.8) show just how unusual the $a sub j sub i$ and $k sub j sub i$ are.
After all, each of them is on the order of $2 sup 2n$, so $k sub j sub i ^a sub j sub 1$ is on the order of $2 sup 4n$.
For the difference of two such terms to be on the order of $2 sup n$ requires some very special
structure.
It cannot happen often, and (in most cases) the $k sub j sub i$, $1 ^<=^i^<=^5$, are determined uniquely by (2.8).
(Remember that the $a sub j sub i$ are public.)
The question is:
How do we determine the $k sub j sub i$ in practice?
Shamir's main contribution was to notice that this could be done in polynomial time by
invoking H.\ W. Lenstra's theorem that the integer programming
problem in a fixed number of variables can be solved in polynomial time [20].
This yields the $k sub j sub i$, $1^<=^i^<=^5$.
Once the $k sub j sub i$ are found, one obtains an approximation to $U/M$ from (2.6), and that lets one construct a pair $(U sup prime ,^M sup prime )$ with $U sup prime / M sup prime$ close to $U/M$ such that the weights $c sub j$ obtained by
.DS 2
.EQ (2.9)
c sub j ~==~ a sub j ^U sup prime ~~( roman mod ~ M sup prime ) ^, ~~~~~0^<^c sub j ^<^ M sup prime ^,
~~~~~1^<=^j^<=^n ^,
.EN
.DE
form a superincreasing sequence (after they are arranged in increasing order).
Note that this attack does not recover the $U$ and $M$ that were constructed by the original
designer of the system.
There are infinitely many pairs $U sup prime ,^M sup prime$ that yield a superincreasing
sequence $c sub j$, and any of them can be used to decrypt messages.
.P
One point that was glossed over in the above discussion is that of finding $j sub 1 ,^"...",^j sub 5$.
After all, the permutation $pi$ is secret, so how can the cryptanalyst be sure she has picked out the
right indices?
The answer to that is simple;
the cryptanalyst considers all possible choices of $j sub 1 ,^"...",^j sub 5$, and since there are only on the order of $n sup 5$ of them, this keeps the running time polynomial.
(In practice, one would use a different approach, choosing more than 5 weights at a time, but not requiring that they come from the 5 smallest
secret weights, but, say, from the half of the secret weights that are smallest.)
.P
The crucial tool that made the above attack succeed was Lenstra's result on integer programming in a fixed number of variables.
It was applied to solve (2.6), which is a typical problem in inhomogeneous diophantine approximation.
In the case of the basic Merkle-Hellman knapsack with parameters given by (1.4),
it turns out that the attack can also be carried out using continued
fractions, a much simpler (and more effective) tool than Lenstra's algorithm [6].
Continued fractions, while very useful, have unfortunately only limited applicability to
knapsacks.
Even for the basic Merkle-Hellman knapsack with the $b sub i$ larger than specified in (1.4) (say $b sub 1 ^approx ^2 sup 2n$,
$b sub n ^approx^2 sup 3n$) the continued fraction method fails.
The Lenstra result is powerful, but is of mostly theoretical interest, since its running time is given by a
high degree polynomial, and so it has never been implemented.
However, another tool, the
Lova\*'sz lattice basis reduction algorithm, which was motivated by Lenstra's method,
was soon applied to knapsacks,
and was crucial for the development of the low-density attacks
as well as for the breaking of other systems.
.H 1 "A low-density attack"
This section presents one of the two known approaches to solving general low-density knapsacks,
the one due to Lagarias and Odlyzko [18].
Compared to the
Brickell low-density attack [3],
it appears to break more knapsacks, and it can be rigorously proved to work, at least for extremely low-density knapsacks.
Most important for this paper, though, is the fact that this attack is conceptually much simpler, and so is very easy to present.
.P
Before discussing the low-density attack of [18], we introduce lattices and lattice basis reduction algorithms.
An \f2integer lattice\f1
$L$ is an additive subgroup of $Z sup n$ that contains $n$ linearly independent vectors over $RR sup n$.
A basis $( bold v sub 1 ,^"...",^bold v sub n )$ of $L$ is a set of elements of $L$ such that
$L^=^ Z bold v sub 1 ^ciplus ^...^ciplus^Z bold v sub n$.
A basis will be represented by the $n^times^n$ basis matrix
.DS 2
.EQ
V ~=~ left [ pile {bold v sub 1 above "" above 3dot above "" above bold v sub n} right ] ^.
.EN
.DE
Bases are not unique;
if $U$ is a unimodular $n^times^n$ matrix (matrix with integer entries and determinant $+- 1$) then $UV$ is another basis.
A very important problem is that of finding the shortest non-zero vector of a lattice,
given its basis.
This problem appears to be quite hard, although there is no proof that it is.
.P
An important concept related to that of the shortest non-zero vector is that of a
\f2reduced basis\f1.
There are several definitions of reduced bases, but the one we will deal with (but will
not define precisely) is that due to Lova\*'sz [19].
What we will use is the fact that the first vector in a Lova\*'sz-reduced basis is not too long.
The precise result is that if $bold v sub 1 ,^"...",^bold v sub n$
is a Lova\*'sz-reduced basis of a lattice,
then [19; Prop.\ 1.11]
.DS 2
.EQ (3.1)
|| bold v sub 1 || sup 2 ~<=~ 2 sup n-1 ~ min from {pile { bold x^member^L above bold x ^!=^fat 0}} ~ || bold x || sup 2 ^.
.EN
.DE
(Actually, one can get a slightly better bound by modifying the definition of Lova\*'sz reduction,
see [18,\|19].)
What's most important is that Lova\*'sz found a polynomial time algorithm that, given a basis for a lattice,
produces a reduced basis.
This algorithm thus has a good theoretical running time bound, but in addition turns out to be very fast
in practice [18], and usually finds a reduced basis in which the first vector is much shorter than is guaranteed by (3.1).
(In low dimensions, it has been observed empirically that it usually finds the shortest non-zero vector in a lattice.)
.P
The low-density attack of [18] is very easy to describe.
Suppose that we wish to find a solution to (1.1), where the $a sub j$ and $s$ are given.
We form the $(n+1)$-dimensional lattice with basis
.DS 2
.EQ (3.2)
V ~=~ left (
matrix {
ccol {1 above 0 above "" above 0 above 0}
ccol {0 above 1 above "" above 0 above 0}
ccol {0 above 0 above "" above 0 above 0}
ccol {cdot cdot cdot above cdot cdot cdot above 3dot above cdot cdot cdot above cdot cdot cdot}
ccol {0 above 0 above "" above 1 above 0}
ccol {- a sub 1 above - a sub 2 above "" above - a sub n above s}
}
right ) ^.
.EN
.DE
If $bold v sub 1 ,^dd ,^bold v sub n+1$ are the rows of $V$, and the $x sub j$ solve (1.1), then
.DS 2
.EQ (3.3)
sum from j=1 to n ~ x sub j ^bold v sub j ~+~ bold v sub n+1 ~=~ ( x sub 1 ,^x sub 2 ,^dd ,^x sub n ,^0) ^,
.EN
.DE
and since the $x sub j$ are 0 or 1, this vector is very short.
The basic attack of [18] consists of running the Lova\*'sz lattice basis reduction algorithm on the basis (3.2) and checking
whether the resulting reduced basis contains a vector that is a solution to (1.1).
.P
If the $a sub j$ are large, then one could expect that most vectors in the lattice generated by (3.2) would be large,
and so the vector (3.3) corresponding to a solution of (1.1) might be the shortest one.
It is possible to prove a rigorous result in this direction.
If the $a sub j$ are chosen at random with
.DS 2
.EQ
a sub j ~ approx ~ 2 sup {beta n} ^, ~~~~~~1^<=^j^<=^n ^,
.EN
.DE
where $beta$ is any constant $>^1.54725$ (the precise definition of the critical
constant is complicated and is given in [18]), then the vector (3.3) is the shortest
non-zero vector in most of these lattices,
as is shown in [18].
(Frieze [11] has obtained a simplified proof of this result.
Also, the claim above is valid only for $SIGMA ^x sub j ^<=^n/2$, but it is easy to reduce the
general problem to this case.)
Thus if we could efficiently find shortest non-zero vectors in lattices,
we could solve most low-density knapsacks.
.P
The rigorous analysis of [11,\|18] applies only to random knapsacks.
However, it appears that this same result also
applies to knapsacks that arise in cryptographic constructions.
Heuristically, there are even technical reasons to think that the above analysis would apply even more strongly to knapsack cryptosystems, since these are less likely
to have what are called small linear relations.
See [18] for a detailed discussion.
.P
The major deficiency of the rigorous analysis mentioned above is that it applies directly only when we have a way to compute the shortest non-zero vector in a lattice.
So far no efficient way to do this has been found.
If we have to rely on the rigorous bounds that have been obtained
on the performance of the Lova\*'sz algorithm,
then we can only assert that most knapsacks are solvable whose weights
are extremely large, on the order of $2 sup n sup 2$.
(See [18] for the precise statement.)
In practice, however, the Lova\*'sz algorithm performs
much better than the worst-case bounds that have been proved for it.
Furthermore, some improvements have been suggested, both in the
way it is implemented [18,\|23] and in the basic construction
of the algorithm [24,\|25], which yield significant advantages in either speed or success in finding short vectors.
Furthermore, these improvements suggest very strongly that one can obtain even better algorithms.
Thus in judging the security of knapsack cryptosystems it is probably
prudent to assume that shortest non-zero vectors in lattices can be found
efficiently.
.H 1 "The Chor-Rivest knapsack"
The Chor-Rivest cryptosystem [7] is one of the few knapsack systems that have not been broken, and is among the most attractive ones.
Let $GF ( p sup h )$ be a finite field such that $p sup h -1$ has only moderate
prime factors, so that it is fairly easy to compute discrete logarithms
in $GF ( p sup h )$.
One possible choice, suggested in [7], is $p = 197$,
$h = 24$.
Let $f(x)$ be a monic irreducible polynomial of degree $h$ over $GF( p)$,
so that $GF ( p sup h )$ can be represented as $GF (p) [x] / f(x)$.
Let $t$ be
the residue class of $x$ modulo $f(x)$,
so that $t$ is an element of $GF ( p sup h )$ and $f(t) = 0$.
Further, let
$g$ be
a generator of the multiplicative group of $GF( p sup h )$.
For $alpha ^member^GF (p)$, let $a sub alpha$ be an integer such that
.DS 2
.EQ (4.1)
g sup {a sub alpha} ^=^ t+ alpha ^,
.EN
.DE
and let $pi$ be a one-to-one map from $"{"0,^1,^dd ,^p-1 "}"$ to $GF (p)$.
We choose an integer $d$, and define
.DS 2
.EQ (4.2)
c sub i ~==~ a sub {pi (i)} ^+^ d ~~roman mod ~ p sup h -1 ^, ~~~~
0^<=^c sub i ^<=^ p sup h -2 ^.
.EN
.DE
Then $c sub 0 ,^c sub 1 ,^dd ,^c sub p-1$ are the public key.
Messages to be encoded are first transformed into $p$-vectors $(m sub 0 ,^dd ,^m sub p-1 )$ of non-negative integers such that
.DS 2
.EQ (4.3)
sum from i=0 to p-1 ~ m sub i ^=^ h ^.
.EN
.DE
(This transformation is easy to perform.)
The ciphertext that is transmitted is then
.DS 2
.EQ (4.4)
s ~=~ sum from i=0 to p-1 ~ m sub i ^c sub i ^.
.EN
.DE
The decryption is accomplished as follows.
First compute
.DS 2
.EQ
r~==~ s ^-^ hd ~~~roman mod ~ p sup h -1 ^, ~~~~0 ^<=^ r ^<=^ p sup h - 2 ^,
.EN
.DE
and then we have
.DS 2
.EQ
g sup r ~=~ prod from i=0 to p-1 ~
g sup {m sub i a sub {pi (i)}} ^.
.EN
.DE
Now $g sup r$ is represented as
a polynomial $G$ in $x$ of degree $<^h$, and $g sup {a sub {pi (i)}}$ is
represented as $x+ pi (i)$.
The product
.DS 2
.EQ
prod from i=0 to p-1 ~ g sup {m sub i a sub {pi (i)}}
.EN
.DE
is then representable as
.DS 2
.EQ
prod from i=0 to p-1 ~ (x+ pi (i)) sup {m sub i} ^,
.EN
.DE
and so we must have
.DS 2
.EQ
G ^+^ f(x) ~=~ prod from i=0 to p-1 ~ (x+ pi (i)) sup {m sub i} ^,
.EN
.DE
since the polynomial on the right side above is monic and of degree exactly $h$.
Now one can recover the $m sub i$ by factoring $G + f(x)$, and this can be done
efficiently.
.P
Chor and Rivest discuss several attacks on this system in this paper.
So far, though, none of them have been modified so as to break the full system when its parameters are chosen carefully.
This represents a nice challenge for future work.
.P 0
\f3Acknowledgement.\f1
The author thanks T.\ H. Foregger for his helpful comments on
an earlier version of this manuscript.
.bp
.ce
.B References
.sp 2
.nr P 1
.PH "''R-\\\\nP''"
.RL
.LI
L. M. Adleman, "On Breaking Generalized Knapsack Public Key Cryptosystems,"
\f2Proc. of the Fifteenth ACM Symposium on Theory of Computing, 1983\f1,
pp. 402-412.
.LI
G. Brassard, "A Note on the Complexity of Cryptography", \f2IEEE
Trans. on Inform. Theory\f1, vol. IT-25, 1979, pp. 232-233.
.LI
E. F. Brickell, "Solving low density knapsacks," 
\f2Advances in
Cryptology-Proc. Crypto 83\f1,
Plenum Press, New York, 1984, pp. 25-37.
.LI
E. F. Brickell, "Breaking Iterated Knapsacks," \f2Advances in
Cryptology-Proc. Crypto 84\f1,
Springer-Verlag, Berlin, 1985, pp. 342-358.
.LI
E.\ F. Brickell, "The Cryptanalysis of Knapsack Cryptosystems,"
\f2Applications of Discrete Mathematics\f1,
R.\ D. Ringeisen and F.\ S. Roberts, eds.,
SIAM, 1988, pp.\ 3-23.
.LI
E. F. Brickell and A. M. Odlyzko, "Cryptanalysis: A Survey of Recent Results,"
\f2Proc. IEEE\f1, vol. 76, 1988, pp. 578-593.
.LI
B. Chor and R. Rivest, "A Knapsack-Type Public Key Cryptosystem Based
on Arithmetic in Finite Fields," \f2Advances in Cryptology: Proceedings of CRYPTO 84\f1,
Springer-Verlag, 1985, pp. 54-65.  Revised version in
\f2IEEE Trans. Information Theory\f1, vol. IT-34, 1988, pp. 901-909.
.LI
Y. Desmedt, "What Happened with Knapsack Cryptographic Schemes?,"
\f2Performance Limits in Communication\f1,
\f2Theory and Practice\f1,
J.\ K. Skwirzynski, ed., Kluwer, 1988, pp.\ 113-134.
.LI
Y. G. Desmedt, J. P. Vandewalle and R. J. M. Govaerts," "A Critical Analysis
of the Security of Knapsack Public Key Algorithms," \f2IEEE Trans. Inform.
Theory\f1, vol. IT-30,
1984, pp. 601-611, also presented at
\f2IEEE Intern. Symp. Inform. Theory\f1, Les Arcs, France, June 1982,
Abstract of papers, pp. 115-116.
.LI
R. Eier and H. Lagger, "Trapdoors in Knapsack Cryptosystems,"
\f2Cryptography\f1, Burg Feuerstein, Germany, March 29 - April 2, 1982,
Lecture Notes in Computer Science, vol. 149, Springer-Verlag, New York,
1983, pp. 316-322.
.LI
A. M. Frieze, "On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem,"
\f2SIAM J. Comp.\f1, vol. 15, no. 2, May 1986, pp. 536-539.
.LI
M.\ L. Furst and R. Kannan,
"Succinct Certificates for Almost All Subset Sum Problems,"
\f2SIAM J. Comput.\f1, vol.\ 18, 1989, pp.\ 550-558.
.LI
M. R. Garey and D. S. Johnson,"\f2Computers and Intractability:  A Guide
to the Theory of NP - Completeness\f1," W. H. Freeman and Company,
San Francisco, 1979.
.LI
P.\ S. Henry,
"Fast Implementation of the Knapsack Cipher,''
\f2Bell System Tech. J.\f1, vol.\ 60, 1981, pp.\ 767-773.
.LI
R. Impagliazzo and M. Naor, "Efficient Cryptographic Schemes Provably as
Secure as Subset Sum,"
\f2Proc. 30th IEEE Symposium on Foundations of Computer Science\f1,
IEEE, 1989, pp.\ 236-241.
.LI
J. C. Lagarias, "Knapsack Public Key Cryptosystems and Diophantine
Approximation,"
\f2Advances in Cryptology, Proc. Crypto 83\f1,
Plenum Press, New York, 1984, pp. 3-23.
.LI
J. C. Lagarias, "Performance Analysis of Shamir's Attack on the
Basic Merkle-Hellman Knapsack Cryptosystem," \f2Proc. 11th Intern. Colloquium
on Automata, Languages and Programming (ICALP)\f1,
Lecture Notes in Computer Science, vol. 172, Springer-Verlag,
Berlin, 1984, pp.\ 312-323.
.LI
J. C. Lagarias and A. M. Odlyzko, "Solving Low Density Subset Sum Problems,"
\fIJ. Assoc. Comp. Mach.\fR, vol. 32, 1985, pp. 229-246.  Preliminary version in
\f2Proc. 24th IEEE Symposium on Foundations of Computer Science\f1,
IEEE,
1983, pp. 1-10.
.LI
A. K. Lenstra, H. W. Lenstra, Jr., and L. Lova\*'sz, "Factoring Polynomials
with Rational Coefficients," \f2Mathematische Annalen 261\f1, 1982, pp.
515-534.
.LI
H. W. Lenstra, Jr., "Integer Programming with a Fixed Number of
Variables,"\f2Math. Operations Research\f1, vol. 8,
1983, pp. 538-548. 
.LI
R. C. Merkle and M. E. Hellman, "Hiding Information and Signatures in Trapdoor
Knapsacks," \f2IEEE Trans. Inform. Theory\f1, vol. 24,
1978, pp.\ 525-530.
.LI
A. M. Odlyzko, "Cryptanalytic Attacks on the Multiplicative Knapsack
Cryptosystem and on Shamir's Fast Signature System," \f2IEEE Trans. Inform.
Theory\f1, vol. IT-30,
1984, pp. 594-601.
.LI
S. P. Radziszowski and D. L. Kreher,
"Solving Subset Sum Problems with the $L sup 3$ Algorithm," 
\f2J. Combin. Math. Combin. Comput.,\f1 vol. 3, 1988, pp. 49-63.
.LI
C. P. Schnorr, "A More Efficient Algorithm for a Lattice Basis Reduction,"
\f2Journal of Algorithms\f1, vol. 9, 1988, pp. 47-62.
.LI
C. P. Schnorr, "A Hierarchy of Polynomial Time Lattice Basis Reduction
Algorithms", \f2Theoretical Computer Science\f1, vol. 53, 1987, pp. 201-224.
.LI
A. Shamir, "A Polynomial Time Algorithm for Breaking the Basic
Merkle-Hellman Cryptosystem," \f2IEEE Trans. Inform. Theory\f1, vol. IT-30,
1984, pp. 699-704.
.LI
H. S. Wilf, "Backtrack: An $ O(1) $ Expected Time Graph Coloring Algorithm,"
\f2Inform. Proc. Letters\f1, vol. 18, 1984, pp. 119-122.
.LE
.ls 1
.CS