Knapsack Cryptosystems (Part 2)

In this post, I continue the discussion from the previous post on knapsack cryptosystems. As discussed before, knapsack cryptosystems base their hardness on the difficulty of the subset-sum problem. However, as we have seen, in the case where the set of integers is superincreasing, the subset-problem can be solved efficiently. We can exploit this fact to construct our cryptosystem. First, we describe how we can encode messages using the subset-sum problem.

Let X=(x_1,\ldots,x_n) be a set of numbers. Suppose we want to encode an n-bit message with bits b_1,\ldots,b_n. To encrypt m, we compute

c:=\sum_{i=1}^n b_i x_i.

Observe that to recover the bits of the message b_1,\ldots,b_n given m and X amounts to solving a subset-sum problem, which is intractable for large n. Note that for this scheme to work, the subset summing to a particular c must be unique. Note that this property is satisfied if X is superincreasing.

With this preparation, the construction proceeds as follows:

  1. Begin with some superincreasing sequence X.
  2. Hide the superincreasing sequence using a linear modular transformation to produce a new sequence X' that is not superincreasing.
  3. Publish X' as the public key to the scheme. Using the secret key (used to specify the transformation in step 2), we can transform the subset-sum problem relative to X' to a subset-sum problem relative to the set X that share the same solution. Since X is superincreasing, this is an easy problem to solve and we recover the original message.

Now, we describe the details of the scheme.

Key Generation. Let X=(x_1,\ldots,x_n) be a superincreasing sequence of numbers. Choose values A and B such that B>2x_n and \gcd(A,B)=1. Compute x'_i=A x_i\pmod{B} for all i. The public key is the sequence X'=(x'_1,\ldots,x'_n) and the secret key is the tuple (A,B,X).

Encryption. To encrypt a binary-valued message b \in \{0,1\}^n, compute the ciphertext c':=b^TX'.

Decryption. To decrypt a ciphertext c', compute c:=A^{-1}c'\pmod{B}. Solve the subset-sum problem using the superincreasing set X with target value c to obtain the message b\in\{0,1\}^n.

We show that the above scheme is correct. This is easy to see; simply observe the following:

c=A^{-1}c'=A^{-1}\sum_{i=1}^n b_i x'_i=\sum_{i=1}^n b_i A^{-1}(A x_i)=\sum_{i=1}^n b_i x_i=b^TX\pmod{B}.

The solution to the subset-sum problem over set X with target c is precisely the solution to the original subset-sum problem with set X' and target c'. Finally, observe that since X is superincreasing,

b^TX=\sum_{i=1}^n b_i x_i < 2\cdot b_n < B,

by construction of B. Thus, the statement c = b^T X holds over the integers, and not just modulo B. This proves the correctness of the above scheme. As a final note, A^{-1} \pmod{B} exists since we required \gcd(A,B)=1. Security of the scheme is based on the fact that the subset-sum problem is NP-complete.

The advantage of knapsack cryptosystems is their efficiency. For instance, in the scheme described here, encryption is effectively free while decryption requires a single modular multiplication followed by an efficient linear-time algorithm for solving the superincreasing subset-sum problem. Even in variants of the knapsack cryptosystems, decryption still requires only a few modular multiplications. In comparison to RSA of Diffie-Hellman, which require many expensive modular exponentiations, the Merkle-Hellman knapsack cryptosystem is much more computationally efficient. Unfortunately, however, there are efficient lattice-based attacks on knapsack cryptosystems. As a result, knapsack cryptosystems require the use of very large parameters in order to achieve security. Consequently, secure knapsack systems are quite impractical and not used in practice. Nevertheless, their construction is still remarkable in both simplicity as well as elegance.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s