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-