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 be a set of numbers. Suppose we want to encode an -bit message with bits To encrypt , we compute
Observe that to recover the bits of the message given and amounts to solving a subset-sum problem, which is intractable for large . Note that for this scheme to work, the subset summing to a particular must be unique. Note that this property is satisfied if is superincreasing.
With this preparation, the construction proceeds as follows:
- Begin with some superincreasing sequence .
- Hide the superincreasing sequence using a linear modular transformation to produce a new sequence that is not superincreasing.
- Publish 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 to a subset-sum problem relative to the set that share the same solution. Since 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 be a superincreasing sequence of numbers. Choose values and such that and . Compute for all . The public key is the sequence and the secret key is the tuple
Encryption. To encrypt a binary-valued message , compute the ciphertext
Decryption. To decrypt a ciphertext , compute . Solve the subset-sum problem using the superincreasing set with target value to obtain the message
We show that the above scheme is correct. This is easy to see; simply observe the following:
The solution to the subset-sum problem over set with target is precisely the solution to the original subset-sum problem with set and target . Finally, observe that since is superincreasing,
by construction of . Thus, the statement holds over the integers, and not just modulo . This proves the correctness of the above scheme. As a final note, exists since we required 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.