<< . .

. 4
( : 6)



. . >>

make the trapdoor is called the decryption key. It is
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

<< . .

. 4
( : 6)



. . >>