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Öaimod p, i.e. taking the rth root of aimod 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.