# Knapsack public-key encryption

Knapsack public-key encryption schemes are based on the subset sum problem, which is NP-complete (see §2.3.3 and §3.10). The basic idea is to select an instance of the subset sum problem that is easy to solve, and then to disguise it as an instance of the general subset sum problem which is hopefully difficult to solve. The original knapsack set can serve as the private key, while the transformed knapsack set serves as the public key.

The Merkle-Hellman knapsack encryption scheme (§8.6.1) is important for historical reasons, as it was the first concrete realization of a public-key encryption scheme. Many variations have subsequently been proposed but most, including the original, have been demonstrated to be insecure (see Note 8.40), a notable exception being the Chor-Rivest knapsack scheme (§8.6.2).

## Merkle-Hellman knapsack encryption

The Merkle-Hellman knapsack encryption scheme attempts to disguise an easily solved instance of the subset sum problem, called a *superincreasing subset sum problem,* by modular multiplication and a permutation. It is however not recommended for use (see Note 8.40).

8.34 Definition A *superincreasing sequence* is a sequence (bi, Ьг, ■ • • • *b _{n})* of positive integers with the property that i>; > X^=r

*h*for each

*i,2 < i < n.*

Algorithm 8.35 efficiently solves the subset sum problem for superincreasing sequences.

8.35 Algorithm Solving a superincreasing subset sum problem

INPUT: a superincreasing sequence (bi, i>2> ■ • • , *b _{n})* and an integer

*s*which is the sum of a subset of the 6*.

OUTPUT: *(xi,X**2**, ■ ■ ■ , x _{n})* where ж; € {0,1}, such that хД; =

*s.*

- 1. it—n.
- 2. While
*i**>*1 do the following: - 2.1 If ,s >
*b,*then*Xj*t— 1 and st-s -*b,.*Other-wise Xft-0. - 2.2 it—i - 1.
- 3. Retum((ari, x
_{2},.... x_{n})). - 8.36 Algorithm Key generation for basic Merkle-Hellman knapsack encryption
^{[1]}^{[2]}^{[3]}^{[4]}^{[5]}^{[6]}^{[7]}^{[8]}

8.37 Algorithm Basic Merkle-Hellman knapsack public-key encryption

SUMMARY: *В* encrypts a message *m* for A, which *A* decrypts.

- 1.
*Encryption. В*should do the following:- (a) Obtain
*A’s*authentic public key (ai,*a^, ■ ■ ■*,*a*_{n}). - (b) Represent the message
*m*as a binary string of length*n,*m = т^пг • ■ ■ m„. - (c) Compute the integer
*c =*mi«i + m2«2 + ■ • • +*m*_{n}a„. - (d) Send the ciphertext c to
*A.*

- (a) Obtain
- 2.
*Decryption.*To recover plaintext*m*from c,*A*should do the following:- (a) Compute
*d = W~*mod^{1}c*M.* - (b) By solving a superincreasing subset sum problem (Algorithm 8.35), find integers
*ri, Г**2**,...*,*r*_{n},*r**1*6 {0,1}, such that d = ribi + ггЬг H-----1*- r*_{n}b_{n}. - (c) Tlie message bits are m, =
*r*= 1,2,..._{n}^, i*,n.*

- (a) Compute

*Proof that decryption works.* The decryption of Algorithm 8.37 allows recovery of original plaintext because

Since 0 < *d < M, d = ^{m}iK(i)* mod

*M,*and hence the solution of the superincreas- ing subset sum problem in step (b) of the decryption gives the message bits, after application of the permutation tt.

- 8.38 Example
*(basic Merkle-Hellman knapsack encryption with artificially small parameters*)*Key generation.*Let*n =*6. Entity*A*chooses the superincreasing sequence (12.17,33,74, - 157.316) ,
*M =*737,*W =*635, and the permutation 7r of {1,2,3,4,5,6} defined by 7г(1) = 3,7r(2) = 6,7r(3) = 1,7r(4) = 2, 7t(5) = 5, and ?r(6) = 4.*A’s*public key is the knapsack set (319,196,250,477.200,559), while A’s private key is (7r,*M, W,*(12,17,33, - 74.157.316) ).

*Encryption.* To encrypt the message *m* = 101101, *В* computes
and sends this to *A.*

*Decryption.* To decrypt, *A* computes *d* = *W* ^{L}c mod *M* = 136, and solves the superincreasing subset sum problem

to get 136 = 12 + 17 + 33 + 74. Hence, rj = 1, = 1, гз = 1, = 1, *гц =* 0, *гц =* 0,

and application of the permutation тг yields the message bits mi = гз = 1, m2 = r_{6} = 0,

m3 = n = 1, m_{4} = Г2 = 1, m_{5} = r_{5} = 0, m_{6} = r_{4} = 1. □

Multiple-iterated Merkle-Hellman knapsack encryption

One variation of the basic Merkle-Hellman scheme involves disguising the easy superincreasing sequence by a series of modular multiplications. The key generation for this variation is as follows.

8.39 Algorithm Key generation for multiple-iterated Merkle-Hellman knapsack encryption

SUMMARY: each entity creates a public key and a corresponding private key.

- 1. Integers
*n*and*t*are fixed as common system parameters. - 2. Each entity
*A*should perform steps 3-6. - 3. Choose a superincreasing sequence
*■ ■ ,*a»^{1}). - 4. For
*j*from 1 to*t*do the following: - 4.1 Choose a modulus
*Mj*with*Mj**>*a^^{-1)}+ a^^{-1}* H-----1- an^{-1}'. - 4.2 Select a random integer
*Wj,*1 <*W*_{}}*<**Mj**-*1, such that gcd(VU, ,*Mj)**=*1. - 4.3 Compute
*= af~^Wj*mod*Mj*for*г*= 1,2,... ,*n.* - 5. Select a random permutation тг of the integers {1,2,... ,n}.
- 6. ,4’s public key is (ai, аг,... ,
*a*where a, = for г = 1,2,... , n;_{n}),*A's*private key is (tv, Mi, ... ,*Mt, Wi,*... ,ИЪ,а[^{0)},4°... .A

Encryption is performed in the same way as in the basic Merkle-Hellman scheme (Algorithm 8.37). Decryption is performed by successively computing *d _{}}* =

*W~*

*mod*

^{l}dj..*Mj*for

*j = t, t*— 1,... .1, where

*d*Finally, the superincreasing subset sum problem

_{t}+ = c.*di*= ri<4

^{0)}+ Г2О2

^{0}* -I-----l-r

_{n}a^ is solved for

*r*and the message bits are recovered

_{it}after application of the permutation *n.*

- 8.40 Note (
*insecurity’ of Merkle-Hellman knapsack encryption)* - (i) A polynomial-time algorithm for breaking the basic Merkle-Hellman scheme is known. Given the public knapsack set, this algorithm finds a pair of integers
*U', M'*such that*U'/M'*is close to*UJM*(where*W*and*M*are part of the private key, and*U = W'*mod M) and such that the integers 6' =^{1}*U'a,*mod M, 1 <*i < n,*form a superincreasing sequence. This sequence can then be used by an adversary in place of (bi, £>2, • • • ,*b*to decrypt messages._{n}) - (ii) The most powerful general attack known on knapsack encryption schemes is the technique discussed in §3.10.2 which reduces the subset sum problem to the problem of finding a short vector in a lattice. It is typically successful if the density (see Definition 3.104) of the knapsack set is less than 0.9408. This is significant because the density of a Merkle-Hellman knapsack set must be less than 1, since otherwise there will in general be many subsets of the knapsack set with the same sum, in which case some ciphertexts will not be uniquely decipherable. Moreover, since each iteration in the multiple-iterated scheme lowers the density, this attack will succeed if the knapsack set has been iterated a sufficient number of times.

Similar techniques have since been used to break most knapsacks schemes that have been proposed, including the multiple-iterated Merkle-Hellman scheme. The most prominent knapsack scheme that has resisted such attacks to date is the Chor-Rivest scheme (but see Note 8.44).

- [1] SUMMARY: each entity creates a public key and a corresponding private key.
- [2] An integer n is fixed as a common system parameter.
- [3] Each entity A should perform steps 3-7.
- [4] Choose a superincreasing sequence (bl,i>2..... bn) and modulus M such that M > bi + + ■ ■ ■ + bn.
- [5] Select a random integer W, 1 < W < M - 1, such that gcd(IU, M) = 1.
- [6] Select a random permutation тг of the integers {1,2,... ,n}.
- [7] Compute a, = Wb^(q mod M for i = 1,2,... , n.
- [8] A’s public key is (ai, 02,... , an); A’s private key is (л, M, W, (b, 62,... , &„)).