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

and its History point of view it is easy to understand that the

higher discussed knapsack schemes are not well

suited for this purpose. Indeed if the decryption

The so called multiplicative knapsack here uses

function is not “enough” (pseudo) invertible the

exactly the same encryption function as the

sender has to perform other trials in order to gen-

Merkle“Hellman additive knapsack scheme. How-

erate a signature. Such a scheme was presented in

ever the trapdoor is completely different in nature,

the original Merkle“Hellman paper [38]. Shamir

because it is mainly based on a transformation

suggested a more practical one [46] in 1978.

from an additive knapsack problem into a mul-

In 1982 Sch¨ bi and Massey proposed another

o

tiplicative one. It was presented by Merkle and

version of [45] as a fast signature scheme.

Hellman in their original paper [38].

In 1982“1983 Odlyzko broke [39] the Shamir™s

Let us ¬rst explain the construction of the public

fast signature and the Sch¨ bi-Massey one. Here

o

key. One chooses n relative prime positive num-

bers ( p1 , p2 , . . . , pn ), some prime number q, such also the LLL algorithm plays an important role.

that q ’ 1 has only small primes and such that

SOME DETAILS: A small encyclopedia is required

n

q> to discuss all schemes, weaknesses and attacks in

pi (10)

details. Only three issues are discussed in more

i=1

depth, these being: (i) why the Merkle“Hellman

and some primitive root b modulo q (see modu-

transformation leads to the possibility of more

lar arithmetic). One then ¬nds integers ai , where

than one decryption key to break, (ii) the LLL

1 ¤ ai ¤ q ’ 1, such that pi ≡ bai mod q. So, ai is

algorithm and (iii) its use in the low density at-

the discrete logarithms of pi base b modulo q. This

tack of Brickell.

explains why q ’ 1 was chosen as the product of

small primes, since the Pohlig“Hellman algorithm

The Existence of In¬nitely Many

(see discrete logarithm problem) can easily calcu-

Decryption Keys

late these discrete logarithms in that case [43].

To decrypt one calculates S = b S mod q, be-

Let us focus on the basic Merkle“Hellman scheme.

cause b S = b xi ·ai = b xi ·ai = pixi mod q. The

Suppose w ’1 and m correspond with the re-

last equality is a consequence of the condition in

verse Merkle“Hellman transformation and that

Equation (10). One can easily ¬nd the correspond-

ai was the used superincreasing sequence. We will

ing x starting from S , using the fact that the num-

demonstrate that other values allow to break (call

bers pi are relative prime. This last point is im-

these V, M, and ai ). In order to analyze for which

portant, because in the general case the subset

V and M Equations (3)“(5) (see also Equation (6))

product problem is NP-complete [24].

holds let us reformulate the Merkle“Hellman

This scheme can be cryptanalyzed by a low den-

transformation in terms of linear inequalities.

sity attack [5, 30]. However the disadvantage is

ai ≡ ai · V mod M and 0 < ai < M can be refor-

that it requires a separate run of the lattice reduc-

mulated into:

tion algorithm (which takes at least on the order

of n4 operations) to attack each n bit message. To 0 < ai = (ai · V ’ si · M) < M, si integer. (11)

overcome that problem, Odlyzko tried another at-

Note that si is equal to (ai · V)/M with · the

tack [39]. Herein he starts from the assumption

that some of the pi are known. He then tries to ¬‚oor function.

Knapsack cryptographic schemes 339

THEOREM 2. Let (v1 , . . . , vn ) be a basis of a lattice

Using Equation (11) the conditions in Equa-

L and let v i be the points

tions (3)“(5) (see also Equation (6)) and the

condition of superincreasing of a can be expressed

i

v= zijv j, for 1 ¤ i ¤ n

as linear inequalities on V/M:

j

1 + si

si V

1 ¤ j ¤ n,

< < ¤1 and

Equation (11) gives:

ai M ai

where zij are integers, then the set (v 1 , . . . , v n ) is

(12)

n also a base for the same lattice L, if and only if

1+ i=1 si

V

<

Equation (3) gives: (13) det(zij) = ±1. An integer matrix Z with det(zij) =

n

M ai

i=1

±1 is called an unimodular matrix.

the condition requiring a be superincreasing

gives for all j, with 2 ¤ j ¤ n: PROOF. See [12].

j’1

j’1

sj ’ i=1 si

V

if a j < < As a consequence of Theorem 2 | det(v1 , . . . , vn )|

ai : (14)

j’1

M aj ’ i=1 ai is independent of a particular basis for the

i=1

lattice.

j’1

j’1

sj ’ i=1 si

V

if a j > > . For a lattice L there does not necessarily exist a

ai : (15)

j’1

M aj ’ i=1 ai set of n vectors that form an orthogonal basis for

i=1

the lattice. The Lenstra Lenstra Lovasz (LLL, see

Observe that the condition in Equation (4) does

shortest vector problem or [35, pp. 515“525]) algo-

not impose an extra condition on the ratio V/M.

rithm ¬nds in polynomial time a basis for a lattice

Indeed, for any V/M which satis¬es the conditions

L, which is nearly orthogonal with respect to a

in Equations (12)“(14) one can take coprime V, M

certain measure of non-orthogonality. The LLL al-

in order to satisfy Equation (4).

gorithm does however not ¬nd in general the most

orthogonal set of n independent vectors. As a con-

THEOREM 1. For each encryption key (a1 , a2 , . . . ,

sequence of Theorem 2 it ¬nds short (probably not

an ) constructed using Equations (3)“(5) from a su-

the shortest) vectors. A basis is called reduced if it

perincreasing sequence (a1 , a2 , . . . , an ), there exist

contains relatively short vectors.

in¬nitely many superincreasing sequences satisfy-

Let us brie¬‚y describe LLL. Let v1 , v2 , . . . , vn

ing the conditions in Equations (3)“(5).

belong to the n-dimensional real vector space. To

initialize the algorithm an orthogonal real basis

PROOF. The conditions Equations (3) and (5) and vi is calculated, together with µij (1 ¤ j < i ¤ n),

superincreasing reformulated as Equations (12)“ such that

(15) can be summarized as: L < M < U, where

V

i’1

L and U are rational numbers. Since there ex-

vi = vi ’ µijv j (16)

ists a superincreasing decryption key, which sat-

j=1

is¬es Equations (3)“(5) there exists an L and U

(vi , v j)

such that L < U. So, in¬nitely many (V, M) sat-

µij = , (17)

(v j, v j)

isfy the bound conditions and the condition that

gcd(V, M) = 1.

where (·, ·) denotes the ordinary inner (scalar)

It is easy to generalize Theorem 1 to knapsack se- product. In the course of the algorithm the vec-

tors v1 , v2 , . . . , vn will be changed several times,

quences a obtained by multiple Merkle“Hellman

transformations [16, 17, 20, 23]. but will always remain a basis for L. After ev-

ery change the vi and µij are updated using Equa-

The LLL Algorithm tions (16) and (17). A current subscript k is used

during the algorithm. LLL starts with k = 2. If

k = n + 1 it terminates. Suppose now k ¤ n, then

First we de¬ne a lattice (in the geometrical sense

we ¬rst check that |µk | ¤ 1/2 if k > 1. If this

of the word). k’1

does not hold, let r be the integer nearest to µk , k’1

DEFINITION 3. Let (v1 , . . . , vn ) be a linearly in- and replace vk by vk ’ r vk’1 , (do not forget the up-

dependent set of real vectors in a n-dimensional date). Next we distinguish two cases. Suppose that

real Euclidean space. The set {u1 v1 + · · · + un vn | k ≥ 2 and |vk + µk vk’1 |2 < (3/4)|vk’1 |2 , then we

k’1

u1 , . . . , un ∈ Z}, is called the lattice with basis interchange vk’1 and vk , (do not forget the update),

(v1 , . . . , vn ). afterwards replace k by k ’ 1 and restart. In the

340 Knapsack cryptographic schemes

j j j j j j

other case we want to achieve that gers (y1 , . . . , yn ) such that v1 = y1 and vi = yi na1 +

j j j j

y1 nai for 2 ¤ i ¤ n. Since n divides vi let ui = vi /n

|µk | ¤ 1 , for 1 ¤ j ¤ k ’ 1. (18)

j 2

j

for 2 ¤ i ¤ n. This implies evidently that 0 ≡ a1 y1

If the condition in Equation (18) does not hold, j j

and ui ≡ ai y1 for 2 ¤ i ¤ n. As a consequence of

then let l be the largest index < k with µl > 1/2,

k

the short enough property we have indeed the

let r be the nearest to µl and replace bk by bk ’ r bl

k

small sum property. The independence of the n ’ 1

(do not forget the update), repeat until the condi-

vectors so obtained with SSMM, is then easy to

tions Equation (18) hold, afterwards replace k by

prove.

k + 1 and restart. Remark that if the case k = 1

appears one replaces it by k = 2.

Arguments are given in [5] that the condition

in Theorem 3 are almost satis¬ed if the density is

The Use of the LLL Algorithm in Brickell™s low enough.

Low Dense Attack

CONCLUSION: The encryption in the Merkle“

In Section “The trials to avoid weaknesses and at- Hellman knapsack is based on NP-completeness,

tacks for the class of usual knapsacks” we brie¬‚y however, its trapdoor was not. In secure public

discussed Brickell™s low dense attack. We intro- key cryptosystems the encryption process must be

duced the concept of SSMM and have given a hard to invert but it must also be hard to ¬nd

sketch of Brickell™s low density attack. Remem- the original trapdoor or another trapdoor. Non-

ber also that if the density is not low enough public key use of knapsack was investigated, e.g.

(>1/ log2 n) it has to be arti¬cially lowered. We will in [18, 44].

only discuss the case that it is indeed low enough. For further details on the research on public key

This last part is always used as the main technique knapsack before 1992, consult [11].

of the breaking algorithm.

Yvo Desmedt

The breaking is based on Theorem 3. Hereto we

¬rst have to de¬ne short enough vector.

References

DEFINITION 4. A vector c in a lattice L is called

short enough related to a1 if

[1] Adleman, L.M. (1983). “On breaking the iterated

n Merkle“Hellman public-key cryptosystem.” Ad-

|ci | < a1 , vances in Cryptology”CRYPTO™82, Lecture Notes

in Computer Science, eds. D. Chaum, R.L. Rivest,

i=2

and A.T. Sherman, Santa Barbara, CA, August 23“

where c1 = 0 and ci = ci /n for 2 ¤ i ¤ n.

25. 1982, Plenum, New York, 303“308. More de-

tails appeared in “On breaking generalized knap-

THEOREM 3. If all vectors in the reduced basis for sack public key cryptosystems.” TR-83-207, Com-

the lattice, with basis vectors ti de¬ned in Equa- puter Science Dept., University of Southern Cali-

tion (19), are short enough related to a1 , then we fornia, Los Angeles, March 1983.

can ¬nd n ’ 1 independent SSMM for a1 , . . . , an . [2] Arazi, B. (1980). “A trapdoor multiple mapping.”

IEEE Trans. Inform. Theory, 26 (1), 100“102.

= ...

t1 (1 na2 na3 na4 nan ) [3] Brickell, E.F., J.A. Davis, and G.J. Simmons

= ...

t2 (0 na1 0 0 0) (1983). “A preliminary report on the cryptanaly-

= ...

t3 (0 0 na1 0 0) sis of the Merkle“Hellman knapsack cryptosys-

(19)

= ...

t4 (0 0 0 na1 0) tems.” Advances in Cryptology”CRYPTO™82, Lec-

. . . . . . ture Notes in Computer Science, eds. D. Chaum,

..

. . . . . .

.

. . . . . . R.L. Rivest, and A.T. Sherman, Santa Barbara,

tn = (0 ...

0 0 0 na1 ). CA, August 23“25, 1982. Plenum, New York, 289“

301.

[4] Brickell, E.F. (1983). “Solving low density knap-

PROOF. Call the vectors of the reduced basis

sacks in polynomial time.” IEEE Intern. Symp.

v1 , v2 , . . . , vn . We will ¬rst prove that a mod-

Inform. Theory, St. Jovite, Quebec, Canada,

j

ular mapping by v1 mod a1 has the small sum September 26“30, 1983. Abstract of papers, 129“

property (see Section “The trials to avoid weak- 130.

nesses and attacks for the class of usual knap- [5] Brickell, E.F. (1984). “Solving low density knap-

sacks”). Since v j is an integral linear combination sacks.” Advances in Cryptology”CRYPTO™83, Lec-

of the vectors in Equation (19), there exist inte- ture Notes in Computer Science, ed. D. Chaum,

Knapsack cryptographic schemes 341

Les Arcs, France, June 1982, Abstract of papers,

Santa Barbara, CA, August 21“24, 1983. Plenum,

115“116.

New York, 25“37.

[18] Desmedt, Y., J. Vandewalle, and R. Govaerts

[6] Brickell, E.F., J.C. Lagarias, and A.M. Odlyzko

(1982). “A highly secure cryptographic algorithm

(1984). “Evaluation of the Adleman attack on mul-

for high speed transmission.” GLOBECOM™82,

tiple iterated Knapsack cryptosystems.” Advances

IEEE, Miami, FL, November 29“December 2,

in Cryptology”CRYPTO™83, Lecture Notes in

1982, 180“184.

Computer Science, ed. D. Chaum, Santa Barbara,

[19] Desmedt, Y., J. Vandewalle, and R. Govaerts

CA, August 21“24, 1983. Plenum, New York, 39“

(1983). “Linear algebra and extended mappings

42.

generalise public key cryptographic knapsack

[7] Brickell, E.F. (1983). “A new knapsack based

algorithms.” Electronics Letters, 19 (10), 379“

cryptosystem.” Presented at CRYPTO™83, Santa

381.

Barbara, CA, August 21“24, 1983.

[20] Desmedt, Y. (1984). “Analysis of the security and

[8] Brickell, E.F. (1985). “Breaking iterated knap-

new algorithms for modern industrial cryptog-

sacks.” Advances in Cryptology”CRYPTO™84, Lec-

raphy.” Doctoral Dissertation, Katholieke Univer-

ture Notes in Computer Science, vol. 196, eds.

siteit Leuven, Belgium.

G.R. Blakley and D. Chaum, Santa Barbara, CA,

[21] Dif¬e, W. and M.E. Hellman (1977). “Exhaustive

August 19“22, 1984. Springer-Verlag, Berlin, 342“

cryptanalysis of the NBS data encryption stan-

358.

dard.” Computer, 10 (6), 74“84.

[9] Brickell, E.F. (1985). “Attacks on generalized knap-

[22] Di Porto, A. (1985). “A public key cryptosystem

sack schemes.” Presented at EUROCRYPT™85,

based on a generalization of the knapsack prob-

Linz, Austria, April 9“11, 1985.

lem.” Presented at EUROCRYPT™85, Linz, Austria,

[10] Brickell, E. and A.M. Odlyzko (1988). “Cryptanaly-

April 9“11, 1985.

sis: A survey of recent results.” Proc. IEEE, 76 (5),

[23] Eier, R. and H. Lagger (1983). “Trapdoors in knap-

578“593.

sack cryptosystems.” Cryptography. Proc. Burg

[11] Brickell, E.F. and A.M. Odlyzko (1992). “Crypt-

Feuerstein 1982, Lecture Notes in Computer Sci-

analysis: A survey of recent results.” Contemporary

ence, vol. 149, ed. T. Beth. Springer-Verlag, Berlin,

Cryptology, ed. G.J. Simmons. IEEE Press, New

316“322.

York, 501“540.

[24] Garey, M.R. and D.S. Johnson (1979). Comput-

[12] Cassels, J.W.S. (1971). An Introduction to the Ge-

ers and Intractability: A Guide to the Theory of

ometry of Numbers. Springer-Verlag, Berlin.

NP”Completeness. W.H. Freeman, San Francisco,

[13] Chor, B. and R.L. Rivest (1985). “A knapsack type

CA.

public key cryptosystem based on arithmetic in ¬-

[25] Goodman, R.M. and A.J. McAuley (1985). “A new

nite ¬elds.” Advances in Cryptology”CRYPTO™84,

trapdoor knapsack public key cryptosystem.” Ad-

Lecture Notes in Computer Science, vol. 196, eds.

vances in Cryptology”EUROCRYPT™84, Lecture

G.R. Blakley and D. Chaum, Santa Barbara, CA,

Notes in Computer Science, vol. 209, eds. T. Beth,

August 19“22, 1984. Springer-Verlag, Berlin, 54“

N. Cot and I. Ingemarsson, Paris, France, April 9“

65.

11, 1984. Springer-Verlag, Berlin, 150“158.

[14] Cooper, R.H. and W. Patterson (1985). “Eliminat-

[26] Hellman, M.E. (1980). “A cryptanalytic time-

ing data expansion in the Chor-Rivest algorithm.”

memory trade-off.” IEEE Trans. Inform. Theory, IT-

Presented at EUROCRYPT™85, Linz, Austria, April

26 (4), 401“406.

9“11, 1985.

[27] Henry, P.S. (1981). “Fast decryption algorithm for

[15] Davio, M. (1983). “Knapsack trapdoor functions:

the knapsack cryptographic system.” Bell Syst.

An introduction.” Proceedings of CISM Summer

Tech. J., 60 (5), 767“773.

School on: Secure Digital Communications, ed.

[28] Karnin, E.D. and M.E. Hellman (1983). “The

J.P. Longo, CISM Udine, Italy, June 7“11, 1982.

largest super-increasing subset of a random set.”

Springer-Verlag, Berlin, 41“51.

IEEE Trans. Inform. Theory, IT-29 (1), 146“148.

[16] Desmedt, Y., J. Vandewalle, and R. Govaerts

Also presented at IEEE Intern. Symp. Inform. The-

(1982). “The use of knapsacks in cryptogra-

ory, Les Arcs, France, June 1982, Abstract of pa-

phy public key systems (Critical analysis of the

pers, 113.

security of Knapsack Public Key Algorithms).”

[29] Karnin, E.D. (1984). “A parallel algorithm for the

Presented at Groupe de Contact Recherche Op-

knapsack problem.” IEEE Trans. on Computers,

erationelle du F.N.R. S., Mons, Belgium, Febru-

C-33 (5), 404“408. Also presented at IEEE Intern.

ary 26, 1982. Appeared in Fonds National de la

Symp. Inform. Theory, St. Jovite, Quebec, Canada,

Rechereche Scienti¬que, Groupes de Contact, Sci-

September 26“30, 1983, Abstract of papers, 130“

ences Math´ matiques.

e

131.

[17] Desmedt, Y.G., J.P. Vandewalle, and R.J.M.

[30] Lagarias, J.C. and A.M. Odlyzko (1983). “Solving

Govaerts (1984). “A critical analysis of the se-

low density subset sum problems.” Proc. 24th An-

curity of knapsack public key algorithms.” IEEE

nual IEEE Symposium on Foundations of Com-

Trans. Inform. Theory, IT-30 (4), 601“611. Also

puter Science, 1“10.

presented at IEEE Intern. Symp. Inform. Theory,

342 Known plaintext attack

[44] Schaumuller-Bichl, I. (1982). “On the design and

[31] Lagarias, J.C. (1984). “Knapsack public key

analysis of new cipher systems related to the DES.”

cryptosystems and diophantine approximation.”

IEEE Intern. Symp. Inform. Theory, Les Arcs,

Advances in Cryptology”CRYPTO™83, Lecture

France, 115.

Notes in Computer Science, ed. D. Chaum, Santa

[45] Sch¨ bi, P. and J.L. Massey (1983). “Fast authenti-

o

Barbara, CA, August 21“24, 1983. Plenum, New

cation in a trapdoor knapsack public key cryptosys-

York, 3“23.

tem.” Cryptography, Proc. Burg Feuerstein 1982,

[32] Lagarias, J.C. (1984). “Performance analysis of

Lecture Notes in Computer Science, vol. 149, ed.

Shamir™s attack on the basic Merkle“Hellman

T. Beth. Springer-Verlag, Berlin, 289“306. See also

knapsack cryptosystem.” Proc. 11th Intern. Collo-

Proc. Int. Symp. Inform. Theory, Les Arcs, June

quium on Automata, Languages and Programming

1982, 116.

(ICALP), Lecture Notes in Computer Science, vol.

[46] Shamir, A. (1978). “A fast signature scheme.” Inter-

172, ed. J. Paredaens. Antwerp, Belgium, July 16“

nal Report. MIT, Laboratory for Computer Science

20, 1984. Springer-Verlag, Berlin.

Report RM-107, Cambridge, MA.

[33] Lagger, H. “Public key algorithm based on knap-

[47] Shamir, A. (1979). “On the cryptocomplexity of

sack systems.” Dissertation, Technical University

knapsack systems.” Proc. Stoc 11 ACM, 118“

Vienna, Austria (in German).

129.

[34] Lenstra, Jr., H.W., (1981). “Integer programming

[48] Shamir, A. and R. Zippel (1980). “On the

with a ¬xed number of variables.” Technical Re-

security of the Merkle“Hellman cryptographic

port, University of Amsterdam, Dept. of Mathe-

scheme.” IEEE Trans. Inform. Theory, 26 (3), 339“

matics, 81“03.

340.

[35] Lenstra, A.K., H.W. Lenstra, Jr., and L. Lo-

[49] Shamir, A. (1983). “A polynomial time algorithm

vasz (1982). “Factoring polynomials with ratio-

for breaking the basic Merkle“Hellman cryptosys-

nal coef¬cients.” Mathematische Annalen, 261,

tem.” Advances in Cryptology”CRYPTO™82, Lec-

515“534.

ture Notes in Computer Science, eds. D. Chaum,

[36] Lenstra, Jr., H.W., (1983). “Integer programming

R.L. Rivest, and A.T. Sherman, Santa Barbara,

with a ¬xed number of variables.” Math. Oper. Res.,

CA, August 23“25, 1982. Plenum, New York, 279“

8 (4), 538“548.

288.

[37] McAuley, A.J. and R.M. Goodman (1983). “Mod-

[50] Shamir, A. (1982). “The strongest knapsack-based

i¬cations to the Trapdoor“Knapsack public key

cryptosystem.” Presented at CRYPTO™82, Santa

cryptosystem.” IEEE Intern. Symp. Inform. The-

Barbara, CA, August 23“25, 1982.

ory, St. Jovite, Quebec, Canada, September 26“30,

[51] Shamir, A. (1984). “A polynomial time algorithm

1983. Abstract of papers, 130.

for breaking the basic Merkle“Hellman cryptosys-

[38] Merkle, R.C. and M.E. Hellman (1978). “Hid-

tem.” IEEE Trans. Inform. Theory, IT-30 (5), 699“

ing information and signatures in trapdoor knap-

704.

sacks.” IEEE Trans. Inform. Theory, 24 (5), 525“

[52] Vaudenay, S. (1998). “Cryptanalysis of the chor-

530.

rivest cryptosystem.” Advances in Cryptology”

[39] Odlyzko, A.M. (1984). “Cryptanalytic attacks on

CRYPTO™98, Lecture Notes in Computer Science,

the multiplicative knapsack cryptosystem and on

vol. 1462, ed. H. Krawczyk, Santa Barbara, CA,

Shamir™s fast signature system.” IEEE Trans. In-

August 23“27, 1998. Springer-Verlag, Berlin, 243“

form. Theory, IT-30 (4), 594“601. Also presented

256.

at IEEE Intern. Symp. Inform. Theory, St. Jovite,

[53] Willett, M. (1983). “Trapdoor knapsacks without

Quebec, Canada, September 26“30, 1983. Abstract

superincreasing structure.” Inform. Process. Let-

of papers, 129.

ters, 17, 7“11.

[40] Odlyzko, A.M. (1985). “Discrete logarithms in ¬-

nite ¬elds and their cryptographic signi¬cance.”

Advances in Cryptology”EUROCRYPT™84, Lec-

ture Notes in Computer Science, vol. 209, eds. T.

Beth, N. Cot and I. Ingemarsson, Paris, France,

KNOWN PLAINTEXT

April 9“11, 1984. Springer-Verlag, Berlin, 225“

ATTACK

314.

[41] Odlyzko, A.M. Personal communication.

[42] Petit, M. “Etude math´ matique de certains

e Known plaintext attack is a scenario in which the

`

syst` mes de chiffrement: les sacs a dos” (Mathe-

e

attacker has access to pairs (Pi , Ci ), i = 1, . . . , N

matical study of some enciphering systems: The

of known plaintexts and their corresponding ci-

knapsack, in French). Doctorates Thesis, Univer-

phertexts. This attack is considered to be highly

sit´ de Rennes, France.

e

practical, especially if the amount of pairs N is

[43] Pohlig, S.C. and M.E. Hellman (1978). “An im-

not too large. This attack scenario is more prac-

proved algorithm for computing logarithms over

tical than the chosen plaintext attack. Probable

GF(p) and its cryptographic signi¬cance.” IEEE

word method which is a popular technique for

Trans. Inform. Theory, 24 (1), 106“110.

Known plaintext attack 343

solving classical simple substitution or transposi- cryptanalysis is a typical example of a known

tion ciphers is an example of a known-plaintext plaintext attack.

attack. Another example is the cryptanalysis of

Alex Biryukov

the German Enigma cipher (see cryptomachines

or [1]) using the so called bombs. It relied Reference

heavily on properly guessed opening words of

the cryptograms (which were at the time called [1] Deavours, C.A. and L. Kruh (1985). Machine Cryp-

cribs). One of the most popular cribs was “Noth- tography and Modern Cryptanalysis. Artech House,

ing to report”. In modern cryptography linear Boston, MA.

344