Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 230

In the quest for trapdoor permutations, it is tempting to try to rely on some well-
known hard problems. Intuitively, the notion of trapdoor which makes computation easy
suggests that the decryption problem must be in the NP class. The hardest problems
in the NP class are NP-complete problems. One famous NP-complete problem is the
knapsack problem. So it is tempting to try to build a cryptosystem based on a knapsack
problem.

9.2.1 Knapsack Problem

Here is the description of the subset sum decision problem . 4

DSSP (Decisional Subset-Sum Problem)
Input : a set of integers { a 1 ,..., a n , s } (represented in binary).

Problem : does a subset of { a 1 ,..., a n } whose sum is s exist?

Intuitively, the a i represent the size of packets that we want to put in a knapsack of
size s . The question is whether a subset of packets which exactly fits into the knapsack
exists or not. This is why we often call this problem the knapsack problem .

Theorem 9.1 (Karp 1972). The language of subset sum problems which are solvable
is NP-complete.

Since deciding whether or not a subset sum problem has a solution is hard, finding
a solution to a solvable problem must be hard as well. Hence we can try to build a
cryptosystem based on the hardness to find a solution. The problem consists of hiding
a trapdoor for the legitimate decryptor.

9.2.2 The Merkle-Hellman Cryptosystem

The Merkle-Hellman cryptosystem is one of the first examples (or candidates) of a
public-key cryptosystem. It was published in 1978 as Ref. [132]. The main idea consists
in giving to the knapsack problem a particular form so that the problem becomes trivial,
and in hiding this particular form with a secret transformation.

Here, the particular form is super-increasing knapsacks . We say that ( b 1 ,...,

b n + 1 ) is super-increasing if we have b i > i − 1 b n ,

j = 1 b j for i

= 1 ,..., n + 1. We notice

that if ( b 1 ,..., b n , b n + 1 ) is super-increasing, and if we let M = b n + 1 , then any knapsack

problem ( b 1 ,..., s )

over the integers, which is itself quite trivial: we notice that b n is in the solution sum if
and only if b n ≤

b n , s ) modulo M is equivalent to the knapsack problem ( b 1 ,..., b n ,

s ) with s = s , and we then reduce to a subproblem ( b 1 ,..., b n − 1 , s

or s = s − b n .

4

For more information, see Ref. [72].