After
this paper was completed, I discovered a paper “Yvo G. Desmedt. What Happened with Knapsack Cryptographic
Schemes? In J. K. Skwirzynski, editor,
Performance Limits in Communication – Theory and Practice. NATO ASI Series E: Applied Sciences, vol. 142. Kluwer Academic Publishers, Dordrecht, The
Netherlands, 1988, pp. 113-134.” that contains substantial materials on the
early development of the knapsack systems, that I did not include in this
paper. Readers are encouraged to read that.
Knapsack
Cryptosystems: The Past and the Future
Ming Kin Lai
Department of Information and
Computer Science
University of California
Irvine, CA 92717-3425, USA
Email: mingl@ics.uci.edu
March 2001
Abstract
This
paper attempts to analyze the knapsack encryption/decryption scheme, survey
major knapsack public-key cryptosystems developed in the past 20-some years,
chronicle their rise and fall, and hope-fully shed some light on the future of
the knapsack cryptosystems.
1. Introduction
Knapsack
cryptosystems, as a group, are one of a few major categories of public key
cryptosystems. Whitfield Diffie and
Martin E. Hellman published their landmark paper "New Directions in
Cryptography" [25] in 1976, invented the idea of public key cryptography
and proposed the fundamental technique of key agreement using the discrete log
problem. That paper brought up the
notion of a trap-door one-way function and the potential use of the knapsack
problem for cryptographic purposes (i.e. as the basis of a trapdoor one-way
function):
… We have already seen that public key cryptosystems imply the
existence of trap-door one-way functions. (p. 652)
… there is an NP complete problem known as the knapsack problem
which lends itself readily to the construction of a one-way function. (p. 653)
However,
Diffie and Hellman were unable to conceive an actual trapdoor one-way function
even though they knew of its existence.
Although they were aware that the knapsack is a one-way function, they
failed to find a trapdoor in it.
Inspired
by the idea of public key cryptography and trapdoor one-way function, Ronald L.
Rivest, Adi Shamir and Leonard M. Adleman [80] invented the first public-key
cryptosystem, which is based on integer factorization, but not on knapsacks. Then Ralph C. Merkle and Martin E. Hellman
[60] discovered a couple of trapdoors in the knapsack one-way function, and
thus they became the creators of the first knapsack scheme. Afterwards, many of the early cryptosystems
are based on the knapsack problem.
Therefore, knapsack cryptosystems are of historic interest, if nothing
else, in the development of cryptography.
As a matter of fact, new knapsack cryptosystems were still being
developed well into the 1990s. These
knapsack cryptosystems all have one thing in common: they are built upon the
perceived difficulty of solving the knapsack problem (or its variants). However, in one way or the other, they are
quite often different from each other.
For example, they use various types of trapdoors in their
construction. It is certainly
interesting to look at the various techniques that they employ.
A
review of literature reveals that few of past writings gives a relatively
comprehensive coverage of these knapsack cryptosystems, and most of them
discuss only a couple knapsack cryptosystems at a time. The most recent paper that has a moderately
detailed coverage on the knapsack cryptosystems was [12], published more than
ten years ago. In addition to describing
the knapsack scheme in somewhat detail, this paper attempts to offer a more
detailed survey of these cryptosystems, document their rise and fall, and
hopefully sheds some light on the future of the knapsack cryptosystems. This paper will not explain technical
details of each cryptosystem and its cryptanalysis; rather, it will provide an
overview and serve as a pointer to relevant materials.
2. Knapsack Problems
Knapsack
problem is the namesake of the type of cryptosystems of which Merkle-Hellman
scheme is the progenitor. However,
there is some confusion over this namesake.
Some writers feel that knapsack cryptosystem is a misnomer because the
cryptosystem is actually based on the subset sum problem. For example, Douglas R. Stinson points out that
a knapsack problem usually refers to one “involving selecting objects with given
weights and profits in such a way that a specified capacity is not exceeded and
a specified target profit is attained.” [96, p. 190]. That is, a knapsack problem, as he sees it, is to maximize Spi*xi
subject to Swi*xi £ c, where pi and wi
are the profit and the weight of object i respectively, xi is a
binary variable signifying whether object i is selected or not, and c is the
capacity. And the subset sum problem
usually is defined as one under which a finite set of natural numbers is given
and we are asked whether there is a subset of this set whose elements sum up to
a certain target, which is also a natural number. On the other hand, there are people (see [2], [32], and [39] for
example) who define a knapsack problem (or a form thereof) exactly as the
subset sum problem described above. And
it is exactly [32] and [39] that Merkle and Hellman cited in their paper as the
description of the knapsack problem on which they based their cryptosystem.
Interestingly,
on the other hand, there are also people (see [58] for instance) who view the
subset sum problem as a particular form of the knapsack problem as described by
Stinson. In this point of view, subset
sum problem is a knapsack problem, as described by Stinson, in which the
per-object profits and the per-object weights are equal for all objects.
Therefore,
whether it should be called knapsack problem or subset sum problem depends on
how these problems are defined and there appears to be no uniform
definition. In this paper, we would use
the term “knapsack problem” (the decision version) as Merkle and Hellman used
it, that is, as a problem in which given a set of integers A = {a1,
a2, …, an}, and an integer S, we are to decide whether
there is a subset of A that sums to exactly S.
There
is another twist to the definition of the knapsack problem. As it is defined by the sources quoted in
[60], the knapsack problem is a decision problem, which is NP-complete. But the version actually used in [60] is a
search problem, where we are asked what that subset of A is, rather than just
whether it exists or not. [60] properly
recognized this distinction and in effect stated correctly that this knapsack
search problem is NP-hard.
(NP-completeness is defined for decision problems only.)
Accordingly,
we would define the “knapsack problem” (the search version) as: Given a vector, the so-called cargo vector,
<a1, a2, …, an>, where ai is
an integer and is called a weight or size, find a binary vector <x1,
x2, …, xn> such that their dot product is exactly
equal to a given integer S, i.e. Sai*xi = S.
Still
another complication is that [60] extends the knapsack problem somewhat. In the basic knapsack problem, there is a
binary vector x, i.e. a vector of variables that can take on values of either 0
or 1; thus the problem is also referred to as a 0-1 knapsack problem. [60] generalizes it so that xi’s
can take on values in the set {0, 1, 2, …, 2b-1} where b is a
positive integer, rather than just in {0, 1}.
Some call this modified version “compact knapsack” or “general
knapsack.”
3. Analysis and Characteristics of
a Knapsack Cryptosystem
A
classic knapsack cryptosystem, e.g. the Merkle-Hellman scheme, is constructed
in the following way, as modeled by [83]:
1. Find
an easy (i.e. polynomially solvable) knapsack problem,
2.
Transform (shuffle or scramble) this easy knapsack into a hard knapsack
problem,
3.
Publish the hard knapsack, and
4.
Construct the cryptosystem such that decryption is essentially different for
the cryptanalyst and the legitimate receiver.
The former needs to solve the hard knapsack but the latter may use the
trapdoor information and solve the easy knapsack.
The
parameters (but not the algorithm) used in the easy knapsack and the parameters
used in the transformation form the private key, and the parameters used in the
hard knapsack form the public key.
Usually we use a vector to represent the weights in the easy knapsack
problem. Then this easy knapsack cargo vector
is transformed to a hard knapsack cargo vector. And we use a binary (or general) vector to represent the
plaintext message. These last two
vectors are “combined” (e.g. multiplied) to obtain a subset sum to form a hard
knapsack problem.
As the
trapdoor one-way function is the soul of a public-key cryptosystem, it is
essential to understand the trapdoor one-way function used in a knapsack
cryptosystem. Here we will make a
digression to computational theory. The
trapdoor one-way function in a classic knapsack scheme is f: N´{0,1}®N (assumed a 0-1 knapsack). The trapdoor one-way function corresponds to
the so-called trapdoor problem, namely, one that decides whether one can solve
the underlying mathematical problem upon which the cryptosystem is based.
Neal
Koblitz [42] defines a cracking problem and a trapdoor problem as follows:
Suppose we are trying to cryptanalyze a public key
cryptosystem. That is, we know the
public enciphering key E and the one-to-one function fE from the set
P of plaintext message units to the set C of ciphertext message units. We intercept some yÎC, and
we want to determine the unique xÎP such that fE(x) =
y. This is known as the cracking
problem for a public key cryptosystem.
That is, the cracking problem is as follows:
INPUT: E, fE:P®C, yÎC
OUTPUT: xÎP such
that fE(x)=y (p. 44)
… trapdoor problem [is a] problem that asks us to reverse the
basic mathematical construction of the trapdoor. If we can find an efficient algorithm for the trapdoor problem,
then we will also have an efficient algorithm for the cracking problem. The converse is not necessarily true, (and
even if true, it might be hard to prove).
That is, there might be ways of solving the cracking problem without
dealing directly with the underlying trapdoor problem. (p. 45)
In
complexity theory, a promise problem is a search or decision problem with a
condition (predicate) attached to it.
We call this condition the promise.
When analyzing an algorithm for a promise problem, we disregard what
happens when the algorithm runs on instances of the promise problem that do not
satisfy the condition: the algorithm could return the correct result, return an
erroneous result, or even fail to terminate.
The
trapdoor problem in a public key cryptosystem is a promise problem. In particular, the trapdoor knapsack problem
in the knapsack scheme:
INPUT: A vector of integers <a1, a2, …, an>
and an integer S
PROMISE: S is the dot
product of <a1, a2, …, an> and <x1,
x2, …, xn> where xiÎ{0,1}
OUTPUT: <x1, x2, …, xn>
is a
promise problem.
An
intriguing and important type of promise is that of uniqueness; that is, the
promise is that each valid instance of the promise problem admits at most one
solution. Such a uniqueness promise
arises naturally in applications to cryptology. We need to make sure that the ciphertext would be decrypted to a
unique plaintext. For example, if the
knapsack cargo vector is <1, 3, 4>, then both the binary vectors <1,
1, 0> and <0, 0, 1> would yield a subset sum of 4. If the binary vector represents the
plaintext and the subset sum the ciphertext, then we can decrypt the same
ciphertext to two different plaintext.
The way the Merkle-Hellman scheme ensures a knapsack problem instance
will have a unique solution is to take advantage of the following fact:
Assume that <a1’, a2’,
…, an’> is super-increasing and <a1, a2,
…, an> results from <a1’, a2’,
…, an’> by strong modular multiplication, then the
solution to <a1, a2, …, an> · x = S is
unique. (See [83, pp. 79-80] for a
proof.)
Strong
modular multiplication refers to modular multiplication in which the modulus is
larger than the sum of all ai’’s, not just larger than
the largest ai’.
As an example to demonstrate the “inadequacy” of non-strong modular
multiplication, let’s say there is a superincreasing knapsack cargo vector
<1, 3, 9> and we generate another knapsack cargo vector <4, 1, 3>
by using non-strong modular multiplication: 1*4 mod 11 = 4, 3*4 mod 11 = 1, 9*4
mod 11 = 3. (Note that the modulus, 11,
is larger than 9, the largest ai’, but less than 13, the
sum of all ai’’s.)
Both <0, 1, 1> and <1, 0, 0>, when multiplied with <4, 1,
3>, would yield a subset sum of 4.
Let’s
go back to the one-way function in the classic knapsack problem. The trapdoor is the algorithm 1. to
transform the subset sum in the hard knapsack problem to a subset sum in the
easy knapsack problem, and 2. to solve that easy knapsack problem (and thus to
recover the binary vector). The
trapdoor information is the easy knapsack weights and the parameters used in
the transformation (between the easy and the hard knapsacks).
It is
important to note that the above is just the way a classic knapsack scheme is
set up. Many knapsack schemes do not
have an easy knapsack in their construction.
That is, they use something other than an easy knapsack problem to
represent the trapdoor. Nevertheless,
they all use the hard knapsack problem (but see below for a discussion as to
whether at all this knapsack problem is a knapsack problem as defined above) to
make deciphering (without the trapdoor information) difficult. In other words, a knapsack cryptosystem
uses, in its construction, a (presumably) hard knapsack, but not necessarily an
easy knapsack. As we will see later,
both the Merkle-Hellman and the Goodman-McAuley cryptosystems, for example,
have a hard knapsack problem and an easy knapsack problem in their
construction. While Merkle-Hellman uses
a superincreasing sequence in the easy knapsack, Goodman-McAuley does not and
instead uses the factorization of a large integer as its trapdoor information.
And
even in the Merkle-Hellman scheme, the easy knapsack problem may not be a
knapsack problem, as defined earlier, at all.
The knapsack problem defined earlier is an additive knapsack. The easy knapsack needs not be an additive
knapsack problem; it can be a multiplicative knapsack problem. And the number, to which the subset sum of
the hard knapsack problem is transformed, will be a subset product if and when
an easy multiplicative knapsack problem is used. Multiplicative knapsacks will be explained in greater detail
later.
Some
cryptosystems, like the Morii-Kasahara cryptosystem and the Naccache-Stern cryptosystem, go one step further by using
multiplicative knapsack not as, or not just as, the easy knapsack but also as
the hard knapsack. The natural question
to ask is then: Is the multiplicative knapsack (decision) problem
NP-complete? In fact, the
multiplicative knapsack (subset product) decision problem, namely, finding x
such that Õai*xi = S, is NP-complete [61, p. 304].
(It
should be noted that some people refer to a cryptosystem with an easy
multiplicative knapsack and a hard additive knapsack, rather than one with a
hard multiplicative knapsack, as a multiplicative knapsack cryptosystem.)
There
are certain characteristics of a knapsack cryptosystem that distinguish one
scheme from another. One of them is the
trapdoor one-way function it uses. One
of the most important contribution of Diffie and Hellman [25] to cryptography
is their discovery of trapdoor one-way function, which allows someone in
possession of secret information to go backwards and compute the (one-way)
function’s inverse. Making use of this
idea, the designer of a cryptosystem needs to find not only a one-way function,
but also a trapdoor. Different knapsack
cryptosystems use different one-way functions (i.e. some use additive knapsacks
and some use multiplicative knapsacks), and maybe different trapdoors if the
same one-way function is used.
The
method by which the trapdoor information (e.g. the easy knapsack cargo vector)
is incorporated into a hard knapsack is an important characteristic of the
cryptosystem. This is the way an easy
knapsack problem is “disguised” as a hard knapsack problem. Some systems use modular multiplication,
some use modular exponentiation, and some use modular root-taking for example.
Another
characteristic is the density of the cryptosystem. The density is defined as d = (n * b) / log2A or some
form thereof, where n is the size of the knapsack cargo vector, b is an integer
such that xi Î {0, 1, 2, …, 2b-1} in a compact knapsack, and A =
max{a1, a2, …, an} where ai is a
weight in the knapsack cargo vector. If
b = 1, then each xi is either 0 or 1, and the density is
approximately the information rate, which is the ratio of number of bits in
plaintext message over average number of bits in ciphertext message. A cryptosystem’s density has a great effect
on its vulnerability and whether it can be used to generate digital signatures
for data origin authentication purposes.
Still
another way to distinguish one knapsack cryptosystem from another is whether
the knapsacks used are additive or multiplicative. For example, we can have an additive knapsack in which a cargo
vector <2, 3, 7> is to multiply with a message <1, 0, 0> to get 2*1
+ 3*0 + 7*0 = 2. And we know that if
the cargo vector is a superincreasing sequence, the additive knapsack is easy
to solve. On the other hand, we can
have a multiplicative knapsack in which a cargo vector <2, 3, 7> is to be
raised to the power of a message <1, 0, 0> to get 2^1 * 3^0 * 7^0 =
2. We know that if the elements of the
cargo vector are relatively prime, the multiplicative knapsack is easy to
solve. A multiplicative knapsack can be
transformed into an additive one by taking logarithms.
The
domain of the parameters in the knapsack problem can be used to distinguish one
cryptosystem (knapsack or not) from another.
The domain used in the Merkle-Hellman scheme, as well as in many others,
is Zn, while that used in the Pieprzyk
cryptosystem is polynomials over GF(2).
Some
modified the knapsack problem so that the cargo vector is an n´m
matrix of integers modulo a prime number, the message vector is an m-element
binary vector, so the subset sum is an n-element vector of integers mod a prime
number. This modified knapsack problem
is called a modular knapsack.
Goodman-McAuley cryptosystem and Niemi cryptosystem, for example, are
based on modular knapsacks.
It
should be clear now, and it should be noted, that many of the so-called
knapsack cryptosystems are not based on the knapsack problem as defined above,
namely, Sai*xi = S, where ai, xi,
and S are integers. As another example,
the Pieprzyk cryptosystem [75] generalizes the knapsack problem so that its
encryption function is based on the search problem Sai(p)*xi(p)
= S(p) where ai(p), xi(p), and S(p) are all polynomials
in p over GF(2). That is, the integers
in the knapsack problem are replaced by polynomials. On the other hand, the Webb cryptosystem can be viewed as putting
constraints on the knapsack problem, so that the encryption function is based
on the search problem SSaij*xij = si [100]. Inevitably, as a result of the knapsack
problem being modified in various ways to construct a cryptosystem, there will
be question as to whether a cryptosystem should be properly classified as a
knapsack cryptosystem. For instance,
the Lu-Lee cryptosystem [57]’s encryption function is based on a one-way
function E(m1, m2) = c1*m1 + c2*m2 mod r.
There may not be consensus as to whether this problem looks like the
knapsack problem closely enough that this cryptosystem could be described as a
knapsack cryptosystem. Therefore, there
is no universal definition of a knapsack cryptosystem and different authors may
classify different cryptosystems, as to their knapsacklike-ness,
differently. Perhaps only those cryptosystems
that have their encryption functions based on the original additive knapsack
should be called knapsack cryptosystems, others should be called knapsack-like
or generalized knapsack cryptosystems.
4. History of the Development of
Knapsack Cryptosystems and their Cryptanalysis
Several
months after Rivest, Shamir, and Adleman [80] published the first public-key
cryptosystem, the RSA cryptosystem, Merkle and Hellman [60] proposed their
knapsack cryptosystem in 1978, in which they described a singly-iterated
version and a multiply-iterated version.
Merkle was certain that the singly-iterated version was secure enough
and offered US$100 to anyone who could break it. In 1982, Shamir [89, 90, 91] discovered an attack against it and
Merkle paid the $100 as promised.
Shamir's attack was somewhat narrow and soon after there were ways
announced to modify the original scheme to prevent the attack. Even after paying Shamir $100, Merkle was
certain that the multiply-iterated system was secure, and he offered US$1000 to
anyone who could break it. In the
summer of 1984, Ernest F. Brickell [9] broke a system of 40 iterations in about
an hour of Cray-1 time. In addition to
the approaches proposed by Shamir and Brickell, other techniques were
subsequently suggested to break the Merkle-Hellman cryptosystem and they are
covered later in this paper.
Between
the time when the Merkle-Hellman knapsack cryptosystem was invented and when
its multiply-iterated version was broken, there were many other knapsack
cryptosystems invented ([4] and [29], for instance), and broken. As described in [52, 94], Ron Graham and Adi
Shamir independently discovered a way to enhance the Merkle-Hellman
scheme. The resulting Graham-Shamir
cryptosystem was broken by Adleman [1] in 1983.
The
Chor-Rivest knapsack cryptosystem was proposed by Benny (Ben-Zion) Chor and
Ronald L. Rivest [15] in 1984, after the multiply-iterated Merkle-Hellman
cryptosystem was broken. (In 1988, Chor
and Rivest [16] published a updated paper on their cryptosystem.) In their papers, Chor and Rivest described
some known ways to attack their system and concluded that they were at most as
good as careful brute-force attacks. In
1995, Claus-Peter Schnorr and H. H. Horner [86] introduced ways to break it
when certain parameters were used, but those parameters were not recommended by
Chor and Rivest. In 1998, Serge
Vaudenay [97, 98] showed a new attack “which definitely breaks the system for
all the proposed parameters in Chor-Rivest’s final paper.”
In
1985, Rodney M. F. Goodman and A. J. McAuley [28, 29] published a general
modular knapsack cryptosystem with the trapdoor based not on a superincreasing
sequence but the transformation between the radix and modular representations
of the subset sums via the Chinese Remainder Theorem. Subsequently it became clear that it was vulnerable to attacks on
the trapdoor.
Józef P.
Pieprzyk [75] designed a knapsack-type cryptosystem in 1985 based on
polynomials over GF(2). Like the
Goodman-McAuley cryptosystem, it can be broken by a so-called GCD attack [12],
in which the cryptanalyst takes the greatest common divisor of certain
components of the public key.
In
1986, Harald Niederreiter [70] published a knapsack cryptosystem using
algebraic coding theory. It can be
broken as described in [12].
In
1987, Jozef Vyskoc [99] proposed a couple of schemes that are based on the
knapsack problem. The cryptosystem
encrypts each message bit with two integers, each of which is the sum of a set
of randomly chosen elements of the knapsack cargo vector.
In 1988, Masakatu Morii and Masao Kasahara [62] designed a cryptosystem using discrete log with a hard multiplicative knapsack. It is not known to have been broken so far.
In
1989, Chi-Sung Laih, et al [47] published a new cryptosystem by improving on
the Merkle-Hellman scheme, specifically, by transforming a superincreasing
sequence to a “high density” knapsack sequence and by using a linearly shift
method to improve the security of the cryptosystem.
In
1990, Valtteri Niemi [71] proposed a cryptosystem based on modular
knapsacks. It was promptly broken next
year by Yeow Meng Chee, and Antoine Joux and Jacques Stern [14, 37]
independently, with slightly different methods.
Hendrik W. Lenstra Jr. [55] in 1991
modified the Chor-Rivest cryptosystem so that the computation of discrete
logarithms in a finite field, which is used by the Chor-Rivest scheme and is a
formidable task, is not required. This
modified scheme, which uses directly the multiplicative structure of the field,
is called the powerline system and is not a knapsack system. Vaudenay’s 1998 paper [97] gives some
directions to break it.
In
1991, Hussain Ali Hussain, Jafar Wadi Abdul Sada, and Saad M. Kalipha [33]
published a multistage trapdoor knapsack cryptosystem. There is a hard knapsack cargo vector at
each stage, and the output (ciphertext) of each stage is treated as input
(plaintext) to the next stage. There
has not been known a specific successful attack against this scheme.
William
A. Webb [100] in 1992 published a cryptosystem based on complementing
sets. The trapdoor problem can be
viewed as a constrained knapsack.
In
1992, Minghua Qu and Scott A. Vanstone [77] invented a hybrid cryptosystem
which is primarily based on a knapsack problem but also involves logarithmic
signatures. The Qu-Vanstone
cryptosystem is based on group factorizations in the additive group of integers
modulo n that generalizes Merkle-Hellman cryptosystems. In 1994, Simon R.
Blackburn, Sean P. Murphy, and Jacques Stern [5] showed that a simplified
variant of the Qu-Vanstone cryptosystem is insecure. The Qu-Vanstone cryptosystem was more thoroughly cryptanalyzed by Phong Nguyen and Jacques
Stern [69] in 1997.
In 1994, Glenn Orton [74] proposed a modification to the multiply-iterated Merkle-Hellman cryptosystem based on dense compact knapsacks. In 1996, Harald Ritter [79] presented an efficient depth first search enumeration of l¥-norm short lattice vectors based on Hoelder's inequality and applied this algorithm to break the Orton cryptosystem.
It is
reported that Z. F. Cao and G. Zhao [13] published a knapsack cryptosystem in
1995 but not much is known about it probably partly because it was published in
Chinese and partly because the researchers in mainland China do not tend to
post their publication on the Internet.
Chu-Hsing
Lin, Chin-Chen Chang, and R. C. T. Lee [56] published in 1995 a cryptosystem
based on Diophantine equations, but the encryption function is the same as that
of compact knapsack cryptosystems.
Almost immediately, Chi-Sung Laih [46], and Blackburn, Murphy and S. G.
Paterson [6] independently showed that this cryptosystem is insecure. Also independently, Mun-Kyu Lee and Kunsoo
Park [48] showed how to use the low-density attack to break this
cryptosystem.
In 1995,
David Naccache and Jacques Stern [64, 65] proposed a cryptosystem based on the
multiplicative knapsack problem. This
cryptosystem, not to be confused with another cryptosystem invented by the same
people [66] but based on higher residues, has not yet been broken,
according to Naccache [63]. Naccache and Stern offered
DM(Deutsche Mark) 1024 to whoever will decrypt a given ciphertext [65] but so
far no one has claimed that prize.
In
1996, K. Kobayashi and M. Kimura [40] proposed an improved knapsack cryptosystem
based on a new concept that a sender can choose encryption keys from a given
encryption-key set. In 1998 it was
shown to be insecure by Hidenori Kuwakado and Hatsukazu Tanaka [44].
In
1997, Kouichi Itoh, Eiji Okamoto and Masahiro Mambo [36] proposed a public-key
cryptosystem in which the decryption could be viewed as a multiplicative
knapsack problem. Nguyen and Stern [68]
mounted an effective attack against it and claimed that, in practice, the
private key can be recovered from the public key “in less than 10 minutes for
the suggested choice of parameters.”
In 2001, Shinya Kiuchi, Yasuyuki Murakami, and Masao Kasahara [41] proposed improvement of the Morii-Kasahara multiplicative knapsack cryptosystem using the Schalkwijk algorithm.
5. History of the Development of
Cryptanalysis Against Knapsack Cryptosystems
After
Merkle and Hellman published their cryptosystem, many people investigated it
and laid the foundation of its eventual breaking. Among those are Giles Brassard [7], Tore Herlestam [31], Adi
Shamir [87, 88], Hamid R. Amirazizi, E. D. Karnin, and J. M. Reyneri [3], Adi
Shamir and Richard E. Zippel [94], Ingemar Ingemarsson [35], Richard Eier and
H. Lagger [26], and Yvo G. Desmedt, Joos Vandewalle and René Govaerts [22]. At last, Shamir [89, 90, 91] completed the
cryptanalysis of the Merkle-Hellman singly-iterated additive knapsack
cryptosystem in early 1982 using Hendrik W. Lenstra’s polynomial time algorithm
[54] for the integer programming problem when the number of variables is fixed. At the CRYPTO ’83 conference, Adleman used
an Apple II computer to demonstrate the breaking using Shamir’s method.
Since
then, Lenstra’s polynomial time algorithm was made obsolete in cryptanalysis
applications by the lattice reduction algorithm invented by Arjen K. Lenstra, Hendrik W. Lenstra Jr., and L. Lovász
[53]. This algorithm is referred to as
L3 or LLL algorithm, which is easy to program and whose running time
is polynomial in the total size of the problem. It was first applied by Adleman [1] in 1982, a few months after
Shamir broke the singly-iterated version, to break the Graham-Shamir
cryptosystem. In the same paper,
Adleman also sketched how to use the LLL algorithm to attack the
multiply-iterated version of the Merkle-Hellman cryptosystem – but later Ernest
F. Brickell, Jeffrey C. Lagarias, and Andrew M. Odlyzko [10] showed that
Adleman’s method worked only on the singly-iterated version of the
Graham-Shamir cryptosystem, but not on the multiply-iterated version of the
Merkle-Hellman cryptosystem and the Graham-Shamir cryptosystem. Adleman treated the cryptographic problem in
the knapsack scheme as a lattice problem rather than a linear programming
problem. This technique was studied by
Brickell, Lagarias, and Odlyzko [10] and Lagarias [49, 50], and was later used
in 1984 by Brickell [9] to break the multiply-iterated Merkle-Hellman
cryptosystem.
Further
refinements of this LLL algorithm were proposed in Schnorr [84, 85]. Using the LLL algorithm, Brickell [8] and
Lagarias and Odlyzko [51] developed algorithm to solve knapsacks of low
density. Numerous other efforts have
been made to improve Adleman’s method (see [9], [18] for example). Odlykzo [73] uses the LLL algorithm to break
a multiplicative knapsack scheme which uses the multiplicative knapsack
suggested by [60] as the hard knapsack.
Lattice reduction was also applied to attack modular knapsacks – Chee,
Joux, and Stern [13, 37] used it to break the Niemi cryptosystem [67], for
instance. (In addition, lattice
reduction was also used to break cryptographic schemes other than those of
knapsack-type.)
[45]
explains the power of lattice reduction in cryptography for those who do not
wish to or are unable to understand the actual mechanisms involved. Both published in 1991, [72] reviews a few
knapsack cryptosystems and summarizes Shamir’s method to break the
singly-iterated Merkle-Hellman and a lattice reduction method to attack
low-density knapsacks, [12] reviews several more knapsack cryptosystems and
according to which, the so-called usually good simultaneous diophantine
approximation (UGSDA), constructed by the LLL algorithm, was able to break all
knapsack cryptosystems that had been proposed and that relied on modular
multiplication as a disguise technique.
It
should be noted that the traditional lattice reduction method is effective to
break the so-called low-density knapsacks.
Therefore, a few high-density knapsack cryptosystem had withheld these
so-called low-density attacks for some extended time. Among them was the Qu-Vanstone cryptosystem. Nguyen and Stern [69] adopted a new use of
lattice reduction, using the notion of an orthogonal lattice, to break the
Qu-Vanstone cryptosystem. Chor-Rivest
cryptosystem is another high-density knapsack cryptosystem. Vaudenay [97, 98] broke it in 1998.
In
1993, Richard Spillman [95] offered genetic algorithm as a new method to crack
knapsack ciphers. Subsequently, Frank
Rubin [81] doubted its effectiveness; and Andrew Clark, et al [17] concluded
that genetic algorithm provides little improvement over an exhaustive search.
6. Description of Selected Knapsack
Cryptosystems
Merkle-Hellman Cryptosystem
Merkle
and Hellman [60] describe two basic methods to construct a knapsack
cryptosystem:
1. The
easy knapsack is an additive knapsack whose weights form a superincreasing
sequence. This easy knapsack is
transformed into a hard (additive) knapsack whose weights are the results of
the modular multiplication of the easy knapsack weights. Using the same example as in [60], the easy
knapsack vector is <171, 196, 457, 1191, 2410>, the message is <1, 1,
0, 1, 0>, the transformation is ai = ai’ *
w mod m, where ai and ai’ are the weights in
the hard and easy knapsack cargo vectors respectively, w=2550 and m=8443 are
integers such that gcd(w,m) = 1 and m > åai’, and the
hard knapsack cargo vector is <5457, 1663, 216, 6013, 7439>. (The reason for ensuring gcd(w,m) = 1 is
that it guarantees w-1 exists.
The reason for ensuring m>åai’ is that
we need a unique solution in x.) The
subset sum S of the hard additive knapsack problem is 5457*1 + 1663*1 + 216*0 +
6013*1 + 7439*0 = 15115. Using the
inverse transformation, S’ = S * w-1 mod m, where w-1
= 3950, we get S’ = 3797, where S’ is the subset sum of
the easy additive knapsack problem. Then
we proceed to use a polynomial-time algorithm to solve the easy knapsack
problem <171, 196, 457, 1191, 2410> * x = 3797, to recover the message
vector x = <1, 1, 0, 1, 0>. If ai’s
are large numbers, solving Sai*xi = S is hard but solving Sai’*xi
= S’ is easy.
2. The
easy knapsack is a multiplicative knapsack whose weights are relatively
prime. This easy knapsack is
transformed into a hard (additive) knapsack whose weights are the results of
the modular logarithm of the easy knapsack weights. Using the same example as in [60], the easy knapsack cargo vector
is <2, 3, 5, 7>, the message is <0, 1, 1, 0>, the transformation is
ai’ = b ^ ai mod m, where ai and ai’
are the weights in the hard and easy knapsack vectors respectively, b=131 and
m=257 are integers such that m is prime, m > Pai’, and the
hard knapsack vector is <80, 183, 81, 195>. The subset sum S of the hard additive knapsack problem is 80*0 +
183*1 + 81*1 + 195*0 = 264. Using the
inverse transformation, S’ = bS mod m, we get S’
= 15, where S’ is the subset product of the easy multiplicative
knapsack problem. Then we proceed to
use a polynomial-time algorithm to solve the easy knapsack problem <2, 3, 5,
7> ^ x = 15, i.e., 2x1 * 3x2 * 5x3 * 7x4
= 15, to recover the message vector x = <0, 1, 1, 0>. If ai’s are large numbers,
solving Sai*xi = S is hard but solving Pai’^xi
= S’ is easy.
[60]
offers two options to complicate the cryptanalyst’s task: “scrambling the order of the ai
and … adding different random multiples of m to each of the ai.” (p. 526)
In
addition to these two options, in order to “improv[e] the security and utility
of the basic methods,” [60, p. 528], [60] offers an iterative method by which
multiple modular multiplication is applied to the ai’s in the first
basic method (that uses an additive knapsack with weights forming a
superincreasing sequence). At each
iteration, a new modulus m and a new multiplier w are chosen. The resulting scheme is known as the
multiply-iterated version. And the
basic scheme is known as the singly-iterated version.
As we
have seen, [60] actually discusses two basic methods, one using an additive
knapsack, another a multiplicative knapsack, as the easy knapsack. For some reason, the second method has sort
of lost out to the first in the subsequent literature, in the sense that the
Merkle-Hellman cryptosystem is usually associated with the first method. And the first one became the Merkle-Hellman cryptosystem in some
literature. However, the second method
– involving an easy multiplicative knapsack, was not totally neglected. The technique would be used in some future
cryptosystems like the Naccache-Stern cryptosystem.
This
Merkle-Hellman cryptosystem is not suitable for generating digital signatures,
as recognized by Merkle and Hellman in the very beginning. [60] suggests some ways to improve it but
they are not very successful. Shamir
[92] designed a signature scheme based on the Merkle-Hellman cryptosystem, but
Odlyzko [73] quickly broke it.
As
mentioned in greater detail above, Shamir broke the singly-iterated version of
the Merkle-Hellman scheme (that uses the additive easy knapsack) by peeling off
the disguise that transforms the easy knapsack to the hard knapsack. At first, Shamir felt that the
multiply-iterated version of the Merkle-Hellman cryptosystem was more secure
than the singly-iterated version.
Actually he wrote later that “after sufficiently many modular
multiplication any knapsack system becomes a trapdoor system that can be used in
public-key cryptography” [93, p. 77]. That
is, the easy knapsack does not have to have the superincreasing structure, and
thus the cryptanalyst cannot expose the trapdoor by looking for this kind of
structure. He called his invention
“random knapsack cryptosystem.” When
Brickell used the LLL algorithm to break the multiply-iterated version,
Shamir’s random knapsack cryptosystem became of historic curiosity only. Odlyzko [72] also showed how to break the
Merkle-Hellman cryptosystem when a multiplicative knapsack is used as the easy
knapsack.
Graham-Shamir Cryptosystem
The
purpose is to eliminate the potential weakness of the Merkle-Hellman
cryptosystem represented by the small values of the easy knapsack vector
weights. “The idea is to use structured
numbers, whose low-order parts are a superincreasing sequence and whose higher
order parts are strings of random bits” [94, p. 340] which represent “noise.”
Let’s
say we pick a superincreasing sequence <2, 3, 6>:
2 = 010
in binary,
3 = 011
in binary,
6 = 110
in binary.
The
easy knapsack cargo vector weights are then:
a1’
= 101 010 in binary, where the prefix 101 are random bits = 42
a2’
= 011 011 in binary, where the prefix 011 are random bits = 27
a3’
= 111 110 in binary, where the prefix 111 are random bits = 62
Of
course, the number of the random bits added becomes part of the secret
key. Because the value of each weight
in the easy knapsack <42, 27, 62> is larger than the corresponding value
in <2, 3, 6>, the superincreasing nature of the original vector <2, 3,
6> is obscured and thus the scheme is perceived to be safer.
The
Graham-Shamir cryptosystem was
broken by Adleman [1] using lattice reduction.
Morii-Kasahara
Cryptosystem
The Morii-Kasahara cryptosystem has a strong
resemblance to the Merkle-Hellman scheme that uses an easy multiplicative
knapsack. While that version of
Merkle-Hellman uses a multiplicative knapsack as the easy knapsack and an
additive knapsack as the hard knapsack, the Morii-Kasahara cryptosystem uses two
multiplicative knapsacks respectively as easy and hard knapsacks. It also incorporates the discrete log
problem in its construction.
[62] in
its example uses the same cargo vector of the easy multiplicative knapsack a’
= <2, 3, 5, 7> and the same modulus m=211 (where m > Pai’=
2*3*5*7 = 210) as offered in [60].
Then, we pick a prime p=211 (p=m in this scheme) and e=19 such that
gcd(e, p-1)º1 (mod p-1). And we
compute d=199 by r*d º 1 (mod p-1). The
transformation of the cargo vector of the easy multiplicative knapsack to that
of the hard multiplicative knapsack is achieved by modular exponentiation: ai
= ai’ ^ e mod p.
Thus the cargo vector of the hard multiplicative knapsack is <164,
39, 14, 85>. Assumed that the
message vector is <1, 1, 0, 1>, then we form the hard knapsack problem Pai*xi=S
as 1641 * 391 * 1140 * 851 = 124
(mod 211). To decipher, we transform S
to S’: S’ = Sd mod p = 124199 mod
211 = 42. Now the easy knapsack is 2X1
* 3X2 * 5X3 * 7X4 = 42 and we can recover x
easily because 2, 3, 5, and 7 are relatively prime.
As
such, the public key is a and p (p=m), and the private key is a’, e
and d.
Chor-Rivest Cryptosystem
The
Chor-Rivest cryptosystem had withheld attacks for a number of years, longer
than many other knapsack cryptosystems.
It does not use modular multiplication to disguise an easy knapsack
problem. The mathematics used is more
involved than that used in other knapsack cryptosystems here and thus we will
briefly give some simplified explanation of how it works.
Let q =
ph be a power-prime. We
consider a public numbering a’ of the subfield GF(p) of the field
GF(q), i.e. {a1’, a2’, …, ap’}
= GF(p) Í GF(q). The secret keys
consist of
- an
element t Î GF(q) with algebraic degree h
- a
generator g of GF(q)*
- an
integer d Î Zq-1
The
public key is a hard knapsack cargo vector whose element is
ai
= d + logg(t + ai’) mod (q–1)
Similar
to other additive knapsack schemes, the ciphertext is a subset sum S= åaixi
mod q-1. To decrypt, we compute
p(t)=gS-h*d as a polynomial in terms of t over GF(p) with degree at
most h-1, which must be equal to Õ(t+ai’) in
GF(q). Thus, if we consider m(y)+p(y),
where m(y) is the minimal polynomial of t, we must obtain the formal
polynomial Õ(y+ai’), whose factorization leads to x, the
message vector.
[15,
16] suggests the following parameters to use with the scheme:
p=197,
h=24
p=211,
h=24
p=256,
h=25
p=243,
h=24
Schnorr
and Horner [86] refined lattice reduction tools to break an implementation of
the Chor-Rivest cryptosystem with parameters p=151 and h=16. Vaudenay [97, 98] showed how to break it
with its suggested parameters: GF(p24) and GF(25625).
Goodman-McAuley Cryptosystem
This
scheme uses modular multiplication to transform an easy additive knapsack into
a hard additive knapsack but does not use a superincreasing sequence as the
cargo vector in the easy knapsack. It
is a general modular knapsack cryptosystem in the sense that it is based on the
general modular knapsack equation Sai*xi = S mod
p, where p is a published modulus and x is no longer a binary vector but a
vector of numbers of a certain bit-length.
The scheme relies on the difficulty of integer factorization, like the
RSA cryptosystem. The trapdoor
information is the factorization of a large integer.
Before
showing how it actually works, we define the radix form and the modular form (in
respect of a modulus) of a number. If
we have a product of primes p=2*3*5=30 and a number a=17, then we can compute
a1
= 17 mod 2 = 1
a2
= 17 mod 3 = 2
a3
= 17 mod 5 = 2
17 is
the radix form the number a, and <1, 2, 2> is the modular form of a. Based on the Chinese remainder theorem, 17 «
<1, 2, 2> is a bijective mapping (for a given p=30).
We will
use the following numeric example, simplified from one in [28, 29], to
illustrate how this scheme works.
We pick
primes 37, 41, and 43, and their product is p=65231. We pick <125174, 151664, 122509> as the cargo vector of the
easy knapsack, but note that it is not superincreasing. The way we find this cargo vector is that we
first determine an integer r, which is in turn determined by the length (in
bits) of each elements of the message vector x (recall that x is not a binary
vector but a general vector). We will
not go to details but if the length of each elements of the message vector x is
2 bits, then r is found to be 3. We
then construct a square matrix such that the sum of its elements in each column
is less than 2r. If we
choose the matrix size to be 3×3 then the following matrix would satisfy our
requirements because 3+1+2=6<8, 1+5+1=7<8, 1+3+2=6<8:
3 1 1
1
5 3
2
1 2
Then we
find the modular representation of <3, 1, 1>, <1, 5, 3>, and <2,
1, 2> by solving the following three systems of congruences:
a1’ ≡ 3 (mod 37)
a2’
≡ 1 (mod 37) a3’
≡ 2 (mod 37)
a1’ ≡ 1 (mod 41)
a2’
≡ 5 (mod 41) a3’
≡ 1 (mod 41)
a1’ ≡ 1 (mod 43)
a2’
≡ 3 (mod 43) a3’
≡ 2 (mod 43)
and we
get a1’ = 125174, a2’ = 151664, and
a3’ = 122509.
And we
pick an integer w=6553, which needs to be relatively prime to 65231, and
compute, using modular multiplication, the cargo vector of the hard knapsack:
a1
= 125174 * 6553 mod 65231 = 50628
a3
= 151664 * 6553 mod 65231 = 59907
a3
= 122509 * 6553 mod 65231 = 3560
So we
obtain the cargo vector of our hard knapsack: <50628, 59907, 3560>.
The
public key is p and a (in radix form). The private key is a’ (in modular form). The multiplier w and the factorization of p
is kept secret.
To
transmit a 6-bit message <1, 2, 3> (i.e. 011011 in binary), we encrypt it
in the same way as in the Merkle-Hellman scheme, except that the subset sum is
now modulo p: 50628*1 + 59907*2 + 3560*3 = 181122 ≡ 50660 (mod
65231). To decrypt, also as in
Merkle-Hellman, we transform S=50660 into S’: S’ =
50660*w-1 mod 65231 = 13257.
The easy knapsack is now 125174* x1 + 151664* x2 +
122509* x3 = 13257 (mod 65231).
Note that the “easiness” of this knapsack does not rely on the
superincreasing nature of the cargo vector, because there is no such
nature. Rather, we resort to the
modular representation of the cargo vector a and of the subset sum S, and recover
x by solving:
3 1 2 x1
11
1
5 1 x2 = 14
1
3 2 x3 13
(Note
that the modular representation of 13257 is <11, 14, 13>.)
If the
size n of the matrix is small, this cryptosystem can be broken by the Lenstra
[54] or Kannan [38] linear programming algorithms (the GCD attack). If n and r are chosen large enough, the
cryptosystem can be broken using lattice basis reduction.
Naccache-Stern Cryptosystem
This
cryptosystem uses a multiplicative version of the basic additive knapsack
problem by combining two techniques: the multiplicative Merkle-Hellman knapsack
[60] and Pohlig-Hellman’s secret-key cryptosystem [76]. The Naccache-Stern cryptosystem is based on the following search problem:
Given a
prime number p, a subset product S, and a cargo vector <a1, a2, …, an>, where ai is relatively prime to each other,
find a binary vector <x1, x2, …, xn>
such that Pai^xi mod p = S.
As
observed in [60], this problem is easy to solve if ai’s are relatively prime and much
smaller than S. Therefore, the cargo
vector of an easy multiplicative knapsack is <a1’, a2’,
…, an’>, where gcd(ai’,aj’)=1
for i¹j. And the cargo vector
element of a hard multiplicative knapsack is obtained by ai = rÖai’
mod p, i.e. taking the rth root of ai’ mod
p. The secret key r < p-1 is a
random integer such that gcd(p-1,r)=1 and the public key is the vector <a1,
a2, …, an>. To
encrypt a message <x1, x2, …, xn>, we
compute S = PaiXi mod p.
To recover x, we compute xi = (gcd(ai,Sr
mod p) – 1) / (ai – 1).
As
such, the transformation between the cargo vectors of the easy and the hard
knapsacks is not by modular multiplication, but by modular root-taking, and the
easy knapsack problem, if we can call that a knapsack at all, is ∑(ai–1)*xi
= gcd(ai,Sr mod p) – 1.
Using
the example in [65], let the easy knapsack cargo vector be <2, 3, 5, 7, 11,
13, 17, 19>, p be 9700247, and r be 5642069.
a1
= 5642069Ö2 mod 9700247 = 8567078
a2
= 5642069Ö3 mod 9700247 = 5509479
a3
= 5642069Ö5 mod 9700247 = 2006538
a4
= 5642069Ö7 mod 9700247 = 4340987
a5
= 5642069Ö11 mod 9700247 = 8643477
a6
= 5642069Ö13 mod 9700247 = 6404090
a7
= 5642069Ö17 mod 9700247 = 1424105
a8
= 5642069Ö19 mod 9700247 = 7671241
To
encrypt <1,1,0,0,1,0,1,0>, we compute the subset product of the hard
knapsack which is PaiXi mod p = 7202882.
To
decrypt, we compute the subset product of the easy knapsack which is 72028825642069
mod 9700247 = 6783. Then we proceed to
factorize 6783 = 191 * 171 * 130 * 110
* 71 * 50 * 31 * 20. Therefore the message
<1,1,0,0,1,0,1,0> is recovered.
7. Evaluation of Knapsack
Cryptosystems
We can
evaluate knapsack cryptosystems, like any other cryptographic schemes, in terms
of their security and efficiency.
Security: As we have seen, most of the knapsack
cryptosystems were broken. Despite
this, unlike integer factorization and discrete logarithm, the general knapsack
(decision) problem is a proven NP-complete problem [27]. Some think that one day a polynomial-time
algorithm may be invented to solve integer factorization and discrete logarithm
problems, while the knapsack problem will still stand as an NP-complete
problem. However, it should be
cautioned that, first, the NP-completeness is based on worst-case analysis,
second, NP-completeness is the characteristics of the general problem, not of a
particular instance. That means that if
average-case complexity is considered, the knapsack problem may not be
difficult (some even argue that it is not strong enough that the problem is
hard on an average-case basis, the problem should be hard in almost all cases
and that the possibility of even 1% of the problem instances being able to be
solved polynomially compromises the security of the cryptosystem) and a
particular instance of the knapsack problem also may not be difficult. In this regard, further analysis requires
advance in average-case complexity and instance complexity analysis, which is
still an emerging research area.
Sticking with the NP-completeness argument, notwithstanding the above
caution, some believe that those broken knapsack cryptosystems were cracked
because their construction (e.g. the use of modular multiplication) does not
disguise completely the easy knapsacks, or their densities are too low. The dilemma for the cryptosystem designer is
that the trapdoor is easy to be discovered if the knapsack density is high. (Also, in general, if density is greater
than 1, some ciphertexts will not be uniquely decipherable.) In other words, if someone invents a
knapsack cryptosystem that fully exploits the difficulty of the knapsack
problem, with a high density and a difficult-to-discover trapdoor, then it will
be a system "better" than those based on integer factorization and
discrete logarithm, because the latter problems are not proven to be
NP-complete. On the other hand,
designing such a cryptosystem appears to be easier said than done.
Efficiency:
In addition to benefiting from the proven (yet cautioned) NP-completeness of
the general knapsack problem, knapsack cryptosystems in general offer
attractively high speed. According to
[72], for the number of knapsack weights n»100, “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.”
There
is no question that knapsack systems still warrant continued research, as a
result of the NP-completeness nature, the faster speed, and a desire to have a
wide variety of cryptosystems available.
8. The Future
In 2000, IEEE adopted P1363:
Standard Specifications For Public Key Cryptography [34], in which three families of
cryptographic functions (discrete logarithm in the group of
remainders modulo a prime, discrete logarithm in the group of points on an
elliptic curve over a finite field, and integer factorization) are discussed. Notably missing is the cryptosystems using
knapsacks. This sort of demonstrates
the cryptographic community’s opinion on and the reality about knapsack
cryptosystems: they are no longer important, at least they are too vulnerable
and the number of unbroken knapsack cryptosystems are too few to worth the
efforts to develop standards for them.
Researchers also seem to focus their efforts on the cryptosystems on
integer factorization, discrete log and elliptic curves. As said above, knapsack cryptosystems still
justify research for various reasons.
However, given the fate of so many knapsack cryptosystems, it is
understandable that people are not willing to develop yet another one waiting
to be broken, unless there are some theoretical breakthroughs. So far, there have not been clear directions
as to how a knapsack cryptosystem should be constructed to avoid known
attacks. When new types of
cryptosystems like NTRU (see www.ntru.com) are emerging, knapsack schemes are
simply hard to attract researchers’ attention.
As a result, it is reasonable to conclude that the future of knapsack
cryptosystems is dim.
References
[1]
Leonard M. Adleman. On Breaking
Generalized Knapsack Public Key Cryptosystems.
In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. ACM, New York, 1983, pp. 402-412.
[2]
Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, MA, 1974.
[3] Hamid R. Amirazizi, E. D. Karnin, and J. M. Reyneri. Compact Knapsacks are Polynomially Solvable. (extended abstract), CRYPTO ’81 Abstracts, Santa Barbara, 1981. Reprinted in ACM SIGACT News, vol. 15, 1983, pp. 20-22.
[4]
Benjamin Arazi. A Trapdoor Multiple
Mapping. IEEE Transactions on
Information Theory, vol. IT-26, no. 1, January 1980, pp. 100-102.
[5]
Simon R. Blackburn, Sean P. Murphy, Jacques Stern. The Cryptanalysis of a Public-Key Implementation of Finite Group
Mappings. Journal of Cryptology, vol.
8, no. 3, 1995, pp. 157-166. Available
at http://www.cs.rhbnc.ac.uk/~sean/fgmrevise.ps
[6]
Simon R. Blackburn, Sean P. Murphy, K. G. Paterson. A Comment on “A New Public-Key Cipher System Based upon the
Diophantine Equations”. IEEE
Transactions on Computers, vol. 46, no. 4, 1997, p. 512. Available at http://www.cs.rhbnc.ac.uk/~sean/cr_dio.ps
[7]
Gilles Brassard. A Note on the
Complexity of Cryptography. IEEE
Transactions on Information Theory, vol. IT-25, 1979, pp. 232-233.
[8]
Ernest F. Brickell. Solving Low Density
Knapsacks. In David C. Chaum, editor,
Proceedings of CRYPTO ’83. Plenum, New
York, 1984, pp. 24-37.
[9]
Ernest F. Brickell. Breaking Iterated
Knapsacks. In G. R. Blakley, David C.
Chaum, editors, Advances in Cryptology – CRYPTO ’84, Lecture Notes in Computer
Science, vol. 196. Springer, Berlin,
1985, pp. 342-358.
[10]
Ernest F. Brickell, Jeffrey C. Lagarias, and Andrew M. Odlyzko. Evaluation of the Adleman Attack on Multiple
Iterated Knapsack Cryptosystems. In
David C. Chaum, editor, Proceedings of CRYPTO ’83. Plenum, New York, 1984, pp.
39-42.
[11]
Ernest F. Brickell, Andrew M. Odlyzko.
Cryptanalysis: A Survey of Recent Results. Proceedings of the IEEE, vol. 76, no. 5, 1988, pp. 578-592.
[12]
Ernest F. Brickell, Andrew M. Odlyzko.
Cryptanalysis: A Survey of Recent Results. In Gustavus J. Simmons, editor, Contemporary Cryptology: The
Science of Information Integrity. IEEE
Press, New York, 1992, pp. 501-540.
Available at
http://www.research.att.com/~amo/doc/arch/cryptanalysis.surv.ps
[13] Z.
F. Cao, G. Zhao. Some New MC Knapsack
Cryptosystems. CHINACRYPT ’94, Xi’an,
Shaanxi, China, Nov 11-15, 1994, pp. 70-75.
[14]
Yeow Meng Chee, Antoine Joux, Jacques Stern.
The Cryptanalysis of a New Public-Key Cryptosystem Based on Modular
Knapsacks. In Joan Feigenbaum, editor,
Advances in Cryptology – CRYPTO ‘91, Lecture Notes in Computer Science, vol.
576. Springer, Berlin, 1992, pp.
204-212.
[15] Benny Chor and Ronald L. Rivest. A Knapsack Type Public Key Cryptosystem
Based on Arithmetic in Finite Fields.
In G. R. Blakley, David C. Chaum, editors, editors, Advances in
Cryptology – Proceedings of CRYPTO ‘84, Lecture Notes in Computer Science, vol.
196. Springer, Berlin, 1985, pp. 54-65. Available at
http://link.springer.de/link/service/series/0558/papers/0196/01960054.pdf
[16] Benny Chor and Ronald L. Rivest. A Knapsack Type Public Key Cryptosystem Based on Arithmetic in Finite Fields. IEEE Transactions on Information Theory, vol. 34, no. 5, September 1988, pp. 901-909.
[17]
Andrew Clark, Ed Dawson, Helen Bergen.
Combinatorial Optimization and the Knapsack Cipher. Cryptologia, vol. XX no. 1, January 1996, p.
85-93.
[18]
Mattijs J. Coster, Antoine Joux, Brian A. LaMacchia, Andrew M. Odlyzko,
Claus-Peter Schnorr, Jacques Stern.
Improved Low-Density Subset Sum Algorithms. Computational Complexity, vol. 2, 1992, pp. 111-128. Available at
http://www.research.att.com/~amo/doc/arch/better.low.density.ps
[19]
Richard A. DeMillo, George I. Davida, David P. Dobkin, Michael A. Harrison,
Richard J. Lipton. Applied Cryptology,
Cryptographic Protocols, and Computer Security Models. Proceedings of Symposia in Applied
Mathematics. American Mathematics
Society, Providence, RI, 1983.
[20]
Dorothy Elizabeth Robling Denning.
Cryptography and Data Security.
Addison-Wesley, Reading, 1982.
[21]
Yvo G. Desmedt. What Happened with
Knapsack Cryptographic Schemes? In J.
K. Skwirzynski, editor, Performance Limits in Communication – Theory and
Practice. NATO ASI Series E: Applied
Sciences, vol. 142. Kluwer Academic
Publishers, Dordrecht, The Netherlands, 1988, pp. 113-134.
[22]
Yvo G. Desmedt, Joos Vandewalle, René Govaerts. A Critical Analysis of the Security of Knapsack Public Key
Algorithms. IEEE Transactions on
Information Theory, vol. IT-30, no. 4, July 1984, pp. 610-611.
[23]
Yvo G. Desmedt, Joos Vandewalle, René Govaerts. The Most General Cryptographic Knapsack Scheme. Proceedings, 1984 Carnahan Conference on
Security Technology. IEEE Press, New
York, 1984, pp. 115-120.
[24]
Whitfield Diffie. The First Ten Years
of Public Key Cryptology. In Gustavus
J. Simmons, editor, Contemporary Cryptology: The Science of Information
Integrity. IEEE Press, New York, 1992,
pp. 135-176.
[25]
Whitfield Diffie, Martin E. Hellman.
New Directions in Cryptography.
IEEE Transactions on Information Theory, vol. IT-22, no. 6, November
1976, pp. 644-654.
[26]
Richard Eier and H. Lagger. Trapdoors
in Knapsack Cryptosystems. In Thomas
Beth, editor, Cryptology, Lecture Notes in Computer Science, vol. 149.
Springer, Berlin, 1982, pp. 316-322.
Available at
http://link.springer.de/link/service/series/0558/papers/0149/01490316.pdf
[27]
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness. W.H.
Freeman & Co., San Francisco, 1979.
[28]
Rodney M. F. Goodman, A. J. McAuley.
New Trapdoor-Knapsack Public-Key Cryptosystem. In Thomas Beth, N. Cot, Ingemar Ingemarsson, editors,
Advances in Cryptology – Proceedings of EUROCRYPT ‘84, Lecture Notes in
Computer Science, vol. 209. Springer, Berlin, 1984, pp. 150-158. Available at
http://link.springer.de/link/service/series/0558/papers/0209/02090150.pdf
[29]
Rodney M. F. Goodman, A. J. McAuley.
New Trapdoor-Knapsack Public-Key Cryptosystem. IEE Proceedings, vol. 132, Pt. E, No. 6, November 1985, pp.
289-292.
[30] P.
S. Henry. Fast Implementation of the
Knapsack Cipher. Bell Labs Technical
Journal, vol. 60, May/June 1981, pp. 767-773.
[31]
Tore Herlestam. Critical Remarks on
Some Public Key Cryptosystems. BIT,
vol. 18, 1978, pp. 493-496.
[32]
Ellis Horowitz, Sartaj Sahni. Computing
Partitions with Applications to the Knapsack Problem. Journal of the ACM, vol. 21, no. 2, April 1974, pp. 277-292.
[33]
Hussain Ali Hussain, Jafar Wadi Abdul Sada, Saad M. Kalipha. New Multistage Knapsack Public-Key
Cryptosystem. International Journal of
Systems Science, vol. 22, no. 11, 1991, pp. 2313-2320.
[34] IEEE. P1363: Standard Specifications For Public Key Cryptography. Available at http://www.manta.ieee.org/groups/1363/P1363/index.html.
[35] Ingemar
Ingemarsson. A New Algorithm for the
Solution of the Knapsack Problem. In
Thomas Beth, editor, Cryptology, Lecture Notes in Computer Science, vol.
149. Springer, Berlin, 1982, pp. 309-315. Available at
http://link.springer.de/link/service/series/0558/papers/0149/01490309.pdf
[36]
Kouichi Itoh, Eiji Okamoto, Masahiro Mambo.
Proposal of a Fast Public Key Cryptosystem. Presented at the 4th annual International Workshop on
Selected Areas in Cryptography ’97 at Carleton University in Ottawa, Canada. Available at
http://www.scs.carleton.ca/~sac97/program/FinalPapers/paper10.ps
[37]
Antoine Joux, Jacques Stern.
Cryptanalysis of Another Knapsack Cryptosystem. Advances in Cryptology – ASIACRYPT ‘91,
Lecture Notes in Computer Science, vol. 739.
Springer, Berlin, 1991, pp. 470-476.
[38] R.
Kannan. Improved Algorithms for Integer
Programming and Related Lattice Problems.
Proceedings of the 15th ACM Symposium on Theory of Computing,
1983, pp. 193-206.
[39]
Richard M. Karp. Reducibility among
Combinatorial Problems. In Raymond E.
Miller, James W. Thatcher, editors, Complexity of Computer Computations. Plenum, New York, 1972, pp. 85-104.
[40] K.
Kobayashi, M. Kimura. A Consideration
of the Security Improvement of the Knapsack Cryptosystem. IEICE Transactions, Fundamentals, vol.
J79-A, no. 8, 1996, pp. 1339-1343.
[41] Shinya
Kiuchi, Yasuyuki Murakami, Masao Kasahara.
New Multiplicative Knapsack-Type Public Key Cryptosystems. IEICE
Transactions, Fundamentals, vol. E84-A, no. 1, 2001, pp.188-196.
Available at
http://search.ieice.or.jp/2001/pdf/e84-a_1_188.pdf
[42]
Neal Koblitz. Algebraic Aspects of
Cryptography. Springer, Berlin, 1998.
[43]
Donald L. Kreher, Douglas R. Stinson.
Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press, Boca Raton, 1999.
[44]
Hidenori Kuwakado, Hatsukazu Tanaka. On
the Security of the Improved Knapsack Cryptosystem. IEICE Transactions on Fundamentals of Electronics, Communications
and Computer Sciences, vol. E81-A, no. 10, October 1998, pp. 2184-2185. Available at
http://search.ieice.or.jp/1998/pdf/e81-a_10_2184.pdf
[45]
Antoine Joux, Jacques Stern. Lattice
Reduction: A Toolbox for the Cryptanalyst.
Journal of Cryptology, vol. 3, 1984, pp. 161-185.
[46]
Chi-Sung Laih. Cryptanalysis of a
Diophantine Equation Oriented Public Key Cryptosystem. IEEE Transactions on Computers, vol. 46, no.
4, 1997, pp. 511-512.
[47]
Chi-Sung Laih, Jau-Yien Lee, Lein Harn, Yan-Kuin Su. Linearly Shift Knapsack Public-Key Cryptosystem. IEEE Journal on Selected Areas in
Communications, vol. 7, no. 4, May 1989, pp. 534-539.
[48]
Mun-Kyu Lee, Kunsoo Park. Low-Density
Attack of Public Cryptosystems Based on Compact Knapsacks. Journal of Electric Engineering and
Information Science vol. 4, no. 2, 1999, pp. 197-204.
[49]
Jeffrey C. Lagarias. Knapsack Public
Key Cryptosystems and Diophantine Approximation. Advances in Cryptology, Proceedings of CRYPTO ’83. Plenum, New York, 1984, pp. 3-23.
[50]
Jeffrey C. Lagarias. Performance
Analysis of Shamir’s Attack on the Basic Merkle-Hellman Knapsack
Cryptosystem. Proceedings of the 11th
International Colloquium on Automata, Languages and Programming, Lecture Notes
in Computer Science, vol. 172.
Springer, Berlin, 1984.
[51]
Jeffrey C. Lagarias, Andrew M. Odlyzko. Solving Low-Density Subset Sum Problems. Journal of the ACM, vol. 32, 1985, pp. 229-246.
[52]
Abraham Lempel. Cryptology in
Transition. Computing Surveys, vol. 11,
no. 4, December 1979, pp. 285-303.
[53]
Arjen K. Lenstra, Hendrik
W. Lenstra Jr., L. Lovász. Factoring
Polynomials with Rational Coefficients.
Mathematische Annualen, vol. 261, 1982, pp. 513-534.
[54] Hendrik W. Lenstra Jr. Integer Programming with a Fixed Number of
Variables. Mathematics and Operations
Research, vol. 8, no. 4, November 183, pp. 538-548.
[55] Hendrik W. Lenstra Jr. On the Chor-Rivest Knapsack
Cryptosystem. Journal of Cryptology,
vol. 3, 1991, pp. 149-155.
[56]
Chu-Hsing Lin, Chin-Chen Chang, R. C. T. Lee.
A New Public-Key Cipher System Based upon the Diophantine
Equations. IEEE Transactions on
Computers, vol. 44, no. 1, 1995, pp. 13-19.
[57]
Shyue-Ching Lu, Lin-Nan Lee. A Simple
and Effective Public-Key Cryptosystem.
COMSAT Technical Review, 1979, pp. 15-24.
[58]
Silvano Martello, Paolo Toth. Knapsack
Problems: Algorithms and Computer Implementations. John Wiley, Chichester, England, 1990.
[59]
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, Boca Raton, 1997.
[60]
Ralph C. Merkle, Martin E. Hellman.
Hiding Information and Signatures in Trapdoor Knapsacks. IEEE Transactions on Information Theory,
vol. IT-24, 1978, pp. 525-530.
[61]
Bernard M. Moret. The Theory of
Computation. Addison-Wesley, Reading,
1997.
[62] Masakatu Morii, Masao Kasahara. New public key cryptosystem using discrete logarithm over GF(p). IEICE Transactions, vol. J71-D, 1988-02, pp. 448-453, and also Memoire of the Faculty of Engineering, Ehime University (Japan), vol. XII, no. 2, 1991-02, pp. 433-439. Available at
http://baltan.is.tokushima-u.ac.jp/~morii/21.html
[63]
David Naccache. Private electronic mail
communication. Message-Id:
<ISSMTP.2000.1_18_.20010226133841.4293074825H@gemplus.com> February 26, 2001.
[64]
David Naccache, Jacques Stern. A New
Public-Key Encryption Scheme. Presented
at a conference in Luminy, France, September 1995.
[65]
David Naccache, Jacques Stern. A New
Public-Key Cryptosystem. In Walter Fumy, editor, Advances in Cryptology - EUROCRYPT
’97, Lecture Notes in Computer Science, vol. 1233. Springer, Berlin, 1997, pp. 27-36. Available at
http://www.gemplus.fr/smart/r_d/publications/download/pk03.ps
[66]
David Naccache, Jacques Stern. A New
Public-Key Cryptosystem on Higher Residues.
Proceedings of the 5th ACM-Computer Science Conference. ACM Press, 1998, pp. 59-66. Available at http://www.gemplus.fr/smart/r_d/publications/download/pk04.ps
[67]
James Nechvatal. Public Key
Cryptography. In Gustavus J. Simmons,
editor, Contemporary Cryptology: The Science of Information Integrity. IEEE Press, New York, 1992, pp. 177-288.
[68]
Phong Nguyen, Jacques Stern.
Cryptanalysis of a Fast Public Key Cryptosystem Presented at SAC
’97. In Stafford Tavares, Henk Meijer,
editors, Selected Areas in Cryptography, Lectures Notes in Computer Science,
vol. 1556. Springer, Berlin, 1999, pp.
213-218.
[69]
Phong Nguyen, Jacques Stern.
Merkle-Hellman Revisited: A Cryptanalysis of the Qu-Vanstone
Cryptosystem Based on Group Factorizations.
In Burt S. Kaliski, editor, Advances in Cryptology - CRYPTO ’97, Lecture
Notes in Computer Science, vol. 1294.
Springer, Berlin, 1997, pp. 198-212.
[70]
Harald Niederreiter. Knapsack-type
Cryptosystems and Algebraic Coding Theory.
Problems of Control and Information Theory, vol. 15, 1986, pp. 159-166.
[71] Valtteri
Niemi. A New Trapdoor in
Knapsacks. In Ivan Bjerre Damgård, editor, Advances in Cryptology -
EUROCRYPT ’90, Lecture Notes in Computer Science, vol. 473. Springer, Berlin, 1991, pp. 405-411.
[72]
Andrew M. Odlyzko. The Rise and Fall of
Knapsack Cryptosystems. In Carl
Pomerance, editor, Cryptology and Computational Number Theory, Proceedings of
Symposia in Applied Mathematics, vol. 42.
American Mathematics
Society, Providence, RI, 1990, pp. 75-88. Available at
http://www.research.att.com/~amo/doc/arch/knapsack.survey.ps
[73]
Andrew M. Odlyzko. Cryptanalytic
Attacks on the Multiplicative Knapsack Cryptosystem and on Shamir’s Fast
Signature Scheme. IEEE Transactions on
Information Theory, IT-30, 1984, pp. 594-601.
Available at http://www.research.att.com/~amo/doc/arch/knapsack.attack.ps
[74]
Glenn Orton. A Multiple-iterated
Trapdoor for Dense Compact Knapsacks.
In A. De Santis, editor, Advances in Cryptology – EUROCRYPT ’94, Lecture
Notes in Computer Science, vol. 950.
Springer, Berlin, 1995, pp. 112-130.
[75] Józef
P. Pieprzyk. On Public-key Cryptosystems Built Using
Polynomial Rings. In Franz Pichler,
editor, Advances in
Cryptology – EUROCRYPT ’85, Lecture Notes in Computer Science, vol. 219. Springer, Berlin, 1985, pp. 73-80. Available at
http://link.springer.de/link/service/series/0558/papers/0219/02190073.pdf
[76] S.
C. Polig, Martin E. Hellman. An
Improved Algorithm for Computing Logarithms over GF(q) and its Cryptographic
Significance. IEEE Transactions on
Information Theory, vol. 24, 1978, pp. 106-110.
[77]
Minghua Qu, Scott A. Vanstone. The
Knapsack Problem in Cryptography. In Gary L. Mullen, Peter Jau-Shyong Shiue, editors, Finite Fields: Theory,
Applications, and Algorithms.
Contemporary Mathematics, vol. 168.
American Mathematics Society, 1994, pp. 291-308.
[78] Stanislaw P. Radziszowski, D. L.
Kreher. Solving Subset Sum Problems
with the L3 Algorithm. Journal of
Combinatorial Mathematics and Combinatorial Computing, vol. 3, 1988, pp. 49-63.
[79]
Harald H. Ritter. Breaking Knapsack Cryptosystems by l¥-Norm Enumeration.
1st International Conference
of the Theory and Applications of Cryptology - Pragocrypt '96, 1996, pp.
480-492. Available at
http://www.mi.informatik.uni-frankfurt.de/research/papers/
ritter.knapsack_cryptosystems.1996.ps
[80]
Ronald L. Rivest, Adi Shamir and Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems. Communications of the
ACM, vol. 21, no. 2, February 1978, pp. 120-126.
[81]
Frank Rubin. Comments on “Cryptanalysis
of Knapsack Cipher Using Genetic Algorithm”.
Cryptologia, vol. XVIII, no. 2, April 1994, pp. 153-154.
[82] Kouichi Sakurai. A Progress Report on Lattice Based Public-Key Cryptosystems - Theoretical Security versus Practical Cryptanalysis. IEICE Transactions, Fundamentals, vol. E83-D, no.3, pp.570-579. Available at http://search.ieice.or.jp/2000/pdf/e83-d_3_570.pdf
[83]
Arto Salomaa. Public-Key
Cryptography. Second Edition. Springer, Berlin, 1996.
[84]
Claus-Peter Schnorr. A Hierarchy of
Polynomial Time Lattice Basis Reduction Algorithm. Theoretical Computer Science, vol. 53, 1987, pp. 201-224.
[85]
Claus-Peter Schnorr. A More Efficient
Algorithm for Lattice Basis Reduction.
Journal of Algorithms, vol. 9, 1988, pp. 47-62.
[86]
Claus-Peter Schnorr, H. H. Hörner.
Attacking the Chor-Rivest Cryptosystems by Improved Lattice
Reduction. In Louis C. Guillou,
Jean-Jacques Quisquater, editors, Advances in Cryptology – EUROCRYPT ’95,
Lecture Notes in Computer Science, vol. 921.
Springer, Berlin, 1995, pp. 1-12.
Available at http://www.mi.informatik.uni-frankfurt.de/research/papers/
schnorr.chor_rivest.1995.ps
[87]
Adi Shamir. The Cryptographic Security
of Compact Knapsacks. MIT/LCS/TM-164,
MIT report, 1980.
[88]
Adi Shamir. On the Cryptocomplexity of
Knapsack Systems. Proceedings of the 11th
ACM Symposium on Theory of Computing, 1979, pp. 339-340.
[89]
Adi Shamir. A Polynomial-time Algorithm
for Breaking the Basic Merkle-Hellman Cryptosystem. Proceedings of the IEEE Symposium on Foundations of Computer
Science. IEEE, New York, 1982, pp.
145-152.
[90]
Adi Shamir. A Polynomial Time Algorithm
for Breaking the Basic Merkle-Hellman Cryptosystem. In David Chaum, Ronald L. Rivest, Alan T. Sherman. editors, Advances in Cryptology –
CRYPTO ’82. Plenum, New York,
1983.
[91]
Adi Shamir. A Polynomial-time Algorithm
for Breaking the Basic Merkle-Hellman Cryptosystem. IEEE Transactions on Information Theory, vol. IT-30, no. 5,
September 1984, pp. 699-704.
[92]
Adi Shamir. A Fast Signature
Scheme. MIT, 1978.
[93]
Adi Shamir. Embedding Cryptographic
Trapdoors in Arbitrary Knapsack Systems.
Information Processing Letters, vol. 17, no. 2, August 23, 1983, pp.
77-78.
[94]
Adi Shamir, Richard E. Zippel. On the
Security of the Merkle-Hellman Cryptographic Scheme. IEEE Transactions on Information Theory, vol. IT-26, no. 3, May
1980, pp. 339-40.
[95]
Richard Spillman. Cryptanalysis of
Knapsack Ciphers using Genetic Algorithm.
Cryptologia, vol. XVII, no. 4, October 1993, pp. 367-377.
[96]
Douglas R. Stinson. Cryptography Theory
and Practice. CRC Press, Boca Raton,
1995.
[97]
Serge Vaudenay. Cryptanalysis of the
Chor-Rivest Cryptosystem. In Hugo
Krawczyk, editor, Advances in Cryptology – CRYPTO ’98, Lecture Notes in Computer
Science, vol. 1462. Springer, Berlin,
1998, pp. 243-256.
[98]
Serge Vaudenay. Cryptanalysis of the
Chor-Rivest Cryptosystem. Journal of
Cryptology, 2001, to appear. Available
at http://link.springer-ny.com/link/service/journals/00145/contents/00/10005/paper/10005.pdf
[99]
Jozef Vyskoc. Knapsack in
Cryptography. Computers and Artificial
Intelligence, vol. 6, no. 6. Veda,
Bratislava, Czechoslovakia , 1987,
pp. 535-540.
[100]
William A. Webb. A Public Key
Cryptosystem based on Complementing Sets.
Cryptologia, vol. XVI, no. 2, April 1992, pp. 177-181.
[101]
Herbert S. Wilf. Backtrack: An O(1)
Expected Time Graph Coloring Algorithm.
Information Processing Letters, vol. 18, 1994, pp. 119-122.