### What are
Knapsack Cryptosystems?

The Merkle-Hellman knapsack
cryptosystem 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. 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].