### Question 32. What are Knapsack Cryptosystems?

The Merkle-Hellman knapsack cryptosystem
[MH78] is a public-key cryptosystem
that was first published in 1978. It is commonly referred to as the *knapsack
cryptosystem*. It is based on the subset sum problem in combinatorics.
The problem involves selecting a number of objects with given weights from
a large set such that the sum of the weights is equal to a pre-specified
weight. This is considered to be a difficult problem to solve in general,
but certain special cases of the problem are relatively easy to solve,
which serve as the "trapdoor" of the system. The-single iteration
knapsack cryptosystem introduced in 1978 was broken by Shamir
[Sha84].
Merkle then published the multiple-iteration knapsack problem which was
broken by Brickell [Bri85]. Merkle offered a $100 reward for anybody able
to crack the single iteration knapsack and a $1000 reward for anybody able
to crack the multiple iteration cipher from his own pocket. When they were
cracked, he promptly paid up.

The Chor-Rivest knapsack cryptosystem was first published in 1984, followed
by a revised version in 1988 [CR88]. It is the only knapsack-like cryptosystem
that does not use modular multiplication. It was also the only knapsack-like
cryptosystem that was secure for any extended period of time. Unfortunately,
Schnorr and Hörner [SH95] developed an attack on the Chor-Rivest cryptosystem
using improved lattice reduction which reduced to hours the amount of time
needed to crack the cryptosystem for certain parameter values (though not
for those recommended by Chor and Rivest). They also showed how the attack
can be extended to attack Damgård's knapsack hash function
[Dam90].