security will be surveyed in Section “The multi-

now the trapdoor technique which turns out to al-

plicative knapsack scheme and its history”.

low the breaking of the cryptographic public knap-

Most research on cryptographic knapsack

sacks.

schemes was related to public key encryption/

Most knapsack schemes differ only in the use of

decryption, i.e., to protect privacy. Cryptographic

other trapdoor techniques. However, some knap-

knapsack schemes which protect the authentic-

sack schemes allow the xi to have more values than

ity are brie¬‚y discussed in Section “The trap-

just binary. Others add some kind of noise to the

door knapsack schemes to protect signatures and

plaintext.

authenticity.”

THE CRYPTOGRAPHIC KNAPSACK SCHEME: THE MERKLE“HELLMAN TRAPDOOR: In the

AN INTRODUCTION: Except for x which is usu- Merkle“Hellman case, when Alice constructs her

ally binary and except when explicitly mentioned, public encryption key a she will ¬rst generate a

superincreasing sequence a1 of natural numbers

all numbers used are natural numbers or integers

(a1 , a2 , . . . , an ), which is de¬ned as follows:

1 1 1

(depending of the context).

334 Knapsack cryptographic schemes

DEFINITION 2. A vector a1 = (a1 , a2 , . . . , an ) is

1 1

Continue iteratively by subtracting xh ah from S 1 ,

1

with h decrementing from n to 1 during the iter-

said to be a superincreasing sequence if:

ations. In fact a rather equivalent process is used

i’1

to write numbers in binary notation. Indeed the

for each i (2 ¤ i ¤ n) : > a1.

ai1 j

sequence (1, 2, 4, 8, . . . , 2n’1 ) is superincreasing.

j=1

In Section “The decryption” we have seen that

(1, 2, 4, 8, . . . , 2n’1 ) is a superincreasing sequence. an important condition for the public key is that

As will be explained further on, a superincreasing it has to form a one-to-one system. This is the

sequence is an “easy” sequence. case for the Merkle“Hellman knapsack scheme

by applying the following Lemma as many times

To hide the superincreasing structure Alice as transformations were used, and by observing

transforms a j into a j+1 starting with j = 1. For that a superincreasing sequence forms a one-to-

each transformation j, she chooses an (w j, m j) one system.

such that Conditions 3 and 4 are satis¬ed

LEMMA 1. Suppose that (a1 , a2 , . . . , an ) is a one-

1 1 1

n

j

< mj

ai (3) to-one knapsack. If m > ai1 and gcd(w, m) = 1,

i=1

then any set (a1 , a2 , . . . , an ), such that ai ≡ ai1 · w

gcd(w j, m j) = 1 (4) mod m, is a one-to-one system.

and then computes:

PROOF. By contradiction: Suppose that (a1 ,

j+1 j j+1

≡ ai · w j (mod m j), where 0 < ai < m (5)

ai a2 , . . . , an ) does not form a one-to-one sys-

tem. Then there exist x and y such that x =

(see modular arithmetic). When Alice used k

xi ai = xi ai ≡

y and yi ai . Thus evidently,

transformations, her public key is given by: a =

’1

yi ai mod m, and also ( xi ai ) · w ≡ ( yi ai ) ·

ak+1 .

w mod m, because w ’1 exists (gcd(w, m) = 1).

’1

We will refer to the transformation de¬ned in

xi ai1 ≡ yi ai1 mod m. Since 0 ¤ xi ai1 ¤

So

Equations (3)“(5) as the Merkle“Hellman trans-

ai1 < m and analogously 0 ¤ yi ai1 ¤ ai1 <

formation. We call the condition in (3) the Merkle“

xi ai1 = yi ai1 . Contradiction.

m we have

Hellman dominance condition. In the case one

uses this transformation in the direction from a j+1

to a j, we call it the reverse Merkle“Hellman trans- A SURVEY OF THE HISTORY OF THE

formation: CRYPTOGRAPHIC KNAPSACK: We will mainly

survey (see Section “The trials to avoid weak-

· w ’1 (mod m j),

j j+1 j

ai ≡ ai where 0 < ai < m. (6)

j nesses and attacks for the class of usual knap-

sacks”) the additive knapsack public key systems

When a1 is superincreasing and only one trans-

protecting privacy and using the same encryption

formation is used, the resulting public key scheme

function as the Merkle“Hellman one. We will ab-

is called the basic Merkle“Hellman scheme, or

breviate this as the usual knapsack cryptographic

sometimes the single iterated Merkle“Hellman

schemes. (Our survey will not be exhaustive.)

scheme. The case that two transformations are

Then we will shortly discuss similar schemes but

used instead of one is called the doubly iterated

using different encryption functions (see Section

one.

“The case of usual knapsacks with other encryp-

Let us now explain the decryption for the

tion functions”). We very brie¬‚y discuss the his-

Merkle“Hellman scheme. When Alice receives the

tory of: the multiplicative knapsack schemes (see

ciphertext S, she iteratively computes S j from

Section “The multiplicative knapsack scheme and

S j+1 starting from j = k and Sk+1 = S as follows:

its history”), and the use of trapdoor knapsacks in

S j = S j+1 · w ’1 (mod m), where 0 ¤ S j < m j. signatures (see Section “The trapdoor knapsack

j

schemes to protect signatures and authenticity”).

(7)

j

n

It is trivial to understand that S j ≡ i=1 xi ai mod The Trials to Avoid Weaknesses and

m and, as a consequence of the inequality in Equa- Attacks for the Class of Usual Knapsacks

tion (7) and the Merkle“Hellman dominance con-

j

n

dition (see Equation (3)), S j = i=1 xi ai . So ¬- In 1979 Shamir found that a knapsack system

nally, Alice ends up with S1 . Finally, it is “easy” with a very high density can (probabalistically)

to ¬nd the message x from S1 . Indeed, start with easily be cryptanalyzed. The density of a knapsack

h’1

h = n. If S 1 > i=1 ai1 then xh has to be 1, else 0. system with public key a is equal to the cardinality

Knapsack cryptographic schemes 335

of the image of the encryption function (see Equa- called ED (where ED indicates that the property to

tion (2)) divided by ai . This result is indepen- ¬nd one bit xi is Easy based on a Divisibility prop-

j j

erty). If d divides all ai , except ar , then if S j =

dent of the trapdoor used to construct the public

j

n

i=1 xi ai , it is easy to ¬nd xr , by checking if d di-

key.

vides S j or not. The method discussed here to con-

To construct public keys in Graham“Shamir

struct the public key, together with the partially

[48] and Shamir“Zippel schemes one starts from

easy sequence already discussed will be called the

other easy sequences than the superincreasing

Desmedt“Vandewalle“Govaerts knapsack.

ones. Then one applies Merkle“Hellman trans-

In the beginning of 1982 Lenstra, Lenstra and

formations to obtain the public key. The case

Lovasz found some algorithm for factoring polyno-

that only one transformation is used is called the

mials with rational coef¬cients [35]. A part of this

basic Graham“Shamir and basic Shamir“Zippel

algorithm is an improvement of the lattice reduc-

scheme. For example in the Graham-Shamir

scheme a1 is not superincreasing but can be writ- tion algorithm (described in [34]). This improve-

ment is known in the cryptographic world as the

ten as:

LLL algorithm (see shortest vector problem). Note

a1 = a + 2q a , with an < 2q’1 that the LLL algorithm speeds up the algorithm

to solve the integer linear programming (with the

and a superincreasing.

number of variables ¬xed) [36]. Another applica-

tion of it is that it allows to ¬nd some simultaneous

It is trivial to understand that such a sequence is

Diophantine approximations [35].

easy.

In April 1982 Shamir broke the basic Merkle“

In the beginning of 1981, Lenstra [34] found

Hellman scheme [49, 51]. His attack uses the

a polynomial time algorithm to solve the integer

integer linear programming problem. Shamir was

linear programming problem, when the number

able to dramatically reduce the number of un-

of unknowns is ¬xed. The complexity of the algo-

knowns (in almost all cases) in the integer lin-

rithm grows exponentially if the size of the num-

ear programming problem. In fact, the cryptan-

ber of unknowns increases. A part of Lenstra™s al-

alyst ¬rst guesses the correct subsequence of the

gorithm uses a lattice reduction algorithm (more

public key corresponding with the smallest super-

details are given in Section “The LLL algorithm”).

increasing elements. The number of elements in

The importance of Lenstra™s work on the secu-

the subsequence is small. Because the Lenstra al-

rity of knapsack cryptosystems will be explained

gorithm (to solve the integer linear programming

later.

problem) is feasible if the number of unknowns is

When in 1981 Henry [27] found a method to

small, Shamir was able to break the basic Merkle“

speed up the decryption in knapsack schemes, Bell

Hellman scheme.

Laboratories started designing a VLSI chip for

A few months later Brickell et al. [3] found that

knapsack cryptosystems, boosting the perceived

by a careful construction of the public key (using

importance of cryptographic knapsack schemes.

the basic Merkle“Hellman scheme) the designer

In 1982 Desmedt, Vandewalle and Govaerts [16,

could avoid Shamir™s attack. This work clearly

17] and independently Eier and Lagger [23]

demonstrated that one has to be careful with at-

demonstrated that any public key which is ob-

tacks, which break systems in almost all cases.

tained from a superincreasing sequence using the

However, as a consequence of further research,

Merkle“Hellman transformation, has in¬nitely

this work has made a technical mark.

many decryption keys. In general, if some public

About the same time Davio came up with a

key is obtained using a Merkle“Hellman transfor-

new and easy sequence [15]. This easy sequence is

mation, then there exist in¬nitely many other pa-

based on ED, but it allows to ¬nd all xi at once. The

rameters, which would result in the same public

construction is similar to the proof of the Chinese

key when used to construct it. This has been called

Remainder Theorem.

“a key observation that led eventually to the com-

Adleman broke the basic Graham“Shamir

plete demise of these knapsack systems” [10].

scheme [1]. The main idea of Adleman was to treat

Desmedt et al. [17] also proposed a different

the cryptanalytic method as a lattice reduction

way to decrypt and build public keys. In previous

problem and not as a linear integer programming

schemes one can ¬nd all plaintext bits xi from the

same S1 . In their approach, the size of the knap- problem. This idea was one of the most in¬‚uential

in the area of breaking cryptographic knapsack al-

sack, n, grows during the construction of the public

gorithms. To solve the lattice problem he used the

key. Each transformation only allows to recover

LLL algorithm [35]. The choice of a good lattice

some bit(s) xi of the plaintext. Let us brie¬‚y ex-

plays a key role in his paper.

plain the other type of partially easy sequence,

336 Knapsack cryptographic schemes

In August 1982 Shamir presented a new knap- ti . To ¬nd x out of S1 , we ¬rst represent S1 binary,

sack scheme, known as Shamir™s ultimate knap- and we call these bits sh . As a consequence of the

sack scheme [50]. The main idea is that instead choice of li , the bits sti are not in¬‚uenced by Ti’1

of applying k Merkle“Hellman transformations, and Ci’1 . To ¬nd x we have to solve modulo 2:

Alice uses “exactly” n ’ 1 of such transforma- « « c1 cn « x1

... 1

st1

tions when constructing her public key. “Exactly” 1

¬.·¬. . ·¬ . ·

.. . ·¬ . ·

¬ . ·=¬ .

means here, that after each transformation (e.g. . .

·

. . .

mod 2,

n’1

jth) one checks if a j is linearly independent of . . . cn

n’1 xn’1

stn’1 c1

(a1 , . . . , a j’1 ), if not, one drops a j, makes a new ...

n n xn

stn c1 cn

one and tries again. The ¬nal result an is the

j

public key. To decrypt S, Alice applies her n ’ 1 where the ci are coef¬cients of Ci .

reverse secret transformations. She starts with McAuley and Goodman [37] proposed in

Sn = S and by calculating the other S j, similar as December 1982 a very similar knapsack scheme

in the Merkle“Hellman case (see Section “The de- as the one proposed by Davio (see higher). The

cryption”). So she obtains a set of linear equations: differences are that no Merkle“Hellman trans-

« 1 « a1 an « x1

formations are used and that the x can have

... 1

S 1 more values than binary (they have to be smaller

¬.·¬. . ·¬ . ·

..

¬ . ·=¬ . . ·¬ . · than a given value and larger than or equal to

. . .

· . (8)

. .

S n’1 n’1 n’1 x

. . . an zero). The trapdoor information consists only in

a1 n’1

Sn ... the secrecy of the primes which were used in the

n n xn

a1 an

construction.

After the discussed transformations to ¬nd x, Alice By the end of 1982 and the beginning of 1983

only has to solve a set of linear equations. It is Desmedt, Vandewalle and Govaerts [19] general-

important to observe that the obtained public key ized Shamir™s ultimate knapsack scheme by gener-

is one-to-one, even if a1 is not an easy sequence, or alizing the Merkle“Hellman transformation, call-

even if no partially easy sequences are used. This ing it the general knapsack scheme. All previously

follows from the nonsingularity of the matrix in discussed knapsack systems are special cases of

Equation (8). this one [20]. In Shamir™s scheme one can only

Other research continued, trying to obtain choose one vector and start the transformation,

other easy (or partially easy) knapsack sequences. while here n choices of vectors are necessary (or

Petit™s [42] de¬ned lexicographic knapsacks. Let are done implicitly).

w(·) be the Hamming weight function. a is called Around the same time Brickell cryptanalyzed

lexicographic, if and only if, aT x < aT y for all bi- low density knapsacks [4, 5]. A similar attack

nary x and y, with x = y and one of the two cases was independently found by Lagarias and Odlyzko

(i) w(x) < w(y) or (ii) w(x) = w(y) and x and y sat- [30]. To perform his attack, Brickell ¬rst gen-

isfy together xk yk = 1 and xi • yi = 0 for all i < k, eralized the Merkle“Hellman dominance condi-

with • the exclusive or. The construction of the tion. The integers he used may also be negative.

public key is as in the Merkle“Hellman case, us- Brickell called a modular mapping —w mod m

ing Merkle“Hellman transformations. from a into c to have the small sum property if ci ≡

Willett [53] also came up with another easy se- ai w mod m, and m > |ci |. He called mappings

quence and a partially easy sequence, which were satisfying this property SSMM. Given xi ai one

then used similar as in the Merkle“Hellman and can easily calculate xi ci . This is done exactly

in the Desmedt“Vandewalle“Govaerts knapsack. as in the reverse Merkle“Hellman case. If the re-

We will only discuss the easy sequence. It is not to sult is greater than ci >0 ci M is subtracted from

dif¬cult to ¬gure out how it works in the case of the it. He tries to ¬nd n ’ 1 such transformations

partially easy sequence. The i th row of the matrix all starting from the public key a. He can then

in Equation (9) corresponds with the binary rep- solve a set of equations similar as in the ultimate

resentation of ai1 . scheme of Shamir (remark the difference in ob-

Cn’1 . . . taining the matrix). To obtain such transforma-

(Tn Cn On’1 Tn’1

tions in order to break, he uses the LLL algorithm

O2 T2 C2 O1 T1 C1 ). (9)

choosing a special lattice. If all the reduced lattice

In Equation (9) the Ti are randomly chosen binary basis vectors are short enough, he will succeed.

matrices, the Ci are n — 1 binary column vectors This happens probably when the density is less

such that they (Ci ) are linearly independent mod- than 1/ log2 n. In the other cases he uses some

ulo 2, and the Oi are n — li zero binary matrices, trick to transform the problem into one satisfy-

where li ≥ log2 n. Let us call the locations of the Ci ing the previous condition. Arguments were given

Knapsack cryptographic schemes 337

that this will succeed almost always when the den- the lattice. This last information will allow to de-

sity is less than 0.39. The low density attack pro- cide whether the selected subset is “good.” If it

posed by Lagarias and Odlyzko is expected to work was not, one restarts at the beginning. If it was

when the density of the knapsack is less than a good set, one can calculate the number of iter-

0.645. These attacks break the ultimate scheme ations that were used by the designer during the

of Shamir, because the density of the public key is construction of the public key. Some calculation of

small as a consequence of construction method of determinants will then return an almost super-

the public key. increasing sequence. Proceeding with almost su-

Lagarias found a good foundation for the attacks perincreasing sequences was already discussed by

on the knapsack system, by discussing what he Karnin and Hellman [28] (remarkable is the con-

called unusually good simultaneous Diophantine tradiction in the conclusion of their paper and its

approximations [31]. Lagarias used similar ideas use by Brickell!).

[32] to analyze Shamir™s attack on the basic In October 1984, Odlyzko found an effective

Merkle“Hellman scheme. The main result is that method to cryptanalyze the McAuley“Goodman

Shamir overlooked some problems, but neverthe- and the Goodman“McAuley scheme, using mainly

less his attack almost always works. gcd™s [41].

Brickell, Lagarias and Odlyzko performed an Later on Brickell [9] was able to break, with

evaluation [6] of the Adleman™s attack on multiple a similar idea as in [8], a lot of other knap-

iterated Merkle“Hellman and Graham“Shamir sack schemes, e.g., the Desmedt“Vandewalle“

schemes. They concluded that his attack on the Govaerts, the Davio, the Willett, the Petit and

basic Graham“Shamir scheme works, but that the Goodman“McAuley. The attack affects also

the version to break iterated Merkle“Hellman or the security of the so-called general knapsack

Graham“Shamir scheme failed. The main rea- scheme.

son for it was that the LLL algorithm found so- At Eurocrypt 85 Di Porto [22] presented two

called undesired vectors, which could not be used new knapsack schemes, which are very close to

to cryptanalyze the cited systems. Even in the case the Goodman“McAuley one. However they were

that only two transformations were applied (to broken during the same conference by Odlyzko.

construct the public key) his attack fails.

The Case of Usual Knapsacks with other

In 1983 Karnin proposed an improved time-

Encryption Functions

memory-processor tradeoff [29] for the knapsack

problem. The idea is related to exhaustive key

search [21] and Hellman™s time-memory trade-off In 1979 Arazi proposed a new knapsack based ad-

[26], in which an exhaustive key search is used to ditive knapsack algorithm to protect the privacy

break the system using straightforward or more of the message [2]. The main difference with the

advanced ideas. The result has only theoretical Merkle“Hellman encryption is that random noise

value if the dimension of the knapsack system n is used in the encryption function. The param-

is large. eters which are chosen during the construction

In 1984 Goodman and McAuley proposed a of the public key have to satisfy some properties

small modi¬cation [25] to their previous system (see [2]).

[37]. In the new version some modulo transforma- In 1983 Brickell also presented a new knapsack

tion was applied. system [7], which is similar to the Arazi one.

In the same year Brickell proposed how to One year later Brickell declared his own new

cryptanalyze [8] the iterated Merkle“Hellman and scheme insecure, as a consequence of his attack

Graham“Shamir scheme. As usual no proof is pro- on iterated knapsacks [8].

vided that the breaking algorithm works; argu- Chor and Rivest proposed in 1984 another knap-

ments for the heuristics are described in [8]. Sev- sack based system [13]. The encryption process

eral public keys were generated by the Merkle“ is very close to the one in the Merkle“Hellman

Hellman and Graham“Shamir scheme and then scheme. The main difference in the encryption is

that xi ¤ h for some given h. The trapdoor tech-

turned out to be breakable by Brickell™s attack.

Again the LLL algorithm is the driving part of nique does not use a modular multiplication (as do

the attack. First the cryptanalyst picks out a sub- almost all other knapsack schemes). The trapdoor

set of the sequence corresponding with the pub- uses the discrete logarithm problem [40, 43] (see

lic key. These elements are entered in a special also Section “The multiplicative knapsack scheme

way in the LLL algorithm. A reduced basis for and its history”). A study of possible attacks was

that lattice is obtained. Then one calculates the done, but it turned out that by a good choice of

linear relation between the old and new basis for parameters all attacks known at that point of time

338 Knapsack cryptographic schemes

could be avoided. New attacks were set up by the ¬nd q and b. He also assumes that b, q and the

authors [13] but this did not change the above ai consist of approximately m bits. His attack will

take a polynomial time if m = O(n log n). Also in

conclusion.

In 1985 Brickell broke the Arazi knapsack sys- this attack the LLL algorithm is the driving force.

tem [9]. In 1985 Cooper and Patterson [14] also A special choice [39] of the lattice is used to attack

proposed some new trapdoor knapsack algorithm, the system. Once the b and q are found the crypt-

which can however be cryptanalyzed by Brickell analyst can easily cryptanalyze ciphertexts as the

[9]. The same attack of Brickell can break this receiver can decrypt them.

knapsack as well as the Lagger knapsack [33].

Since 1985 interest in public key knapsacks The Trapdoor Knapsack Schemes to

almost vanished completely. In 1998 the Chor“ Protect Signatures and Authenticity

Rivest scheme was ¬nally cryptanalyzed [52].

To make a digital signature the sender applies the

The Multiplicative Knapsack Scheme decryption function on the plaintext. From this