Revenge of the Knapsack

Bram Cohen describes a modified knapsack system and suggests it could be used as a public-key cryptosystem. My thoughts:

1. Let's call the elements of the public key a_i, for 1 \leq i \leq k. Consider the sets B_n = {b_i: b_i = a_i (mod n)} for arbitrary n.

2. Note that, if gcd(p,n) is sufficiently large (i.e., > p/2k), then the elements of B_n will follow a very specific distribution. Specifically, each will fall into one of the intervals [a*gcd(p,n), a*gcd(p,n)+p/2k) for some integer a.

3. For p << n << kp with gcd(p,n) large, there will necessarily be more than 1 residue in at least some of the intervals, and, with high probability, each interval will contain at least one residue.

4. Trivially: gcd(p,n) = gcd(p,n+p).

So let's posit a hypothetical function f(n) that will give us a good probabilistic estimate of whether the residues of the a_i (mod n) really do "clump together" in the intervals of size p/2k. This should be close to 0 when gcd(p,n) is low, larger when gcd(p,n) is greater than about p/k, and close to 1 when gcd(p,n) = p. Then f(n) is periodic (or "close to it") with period p. So if we can construct f as a quantum function, we may be able to use a QFT to estimate its period, which would recover the private key.

This is shaky on several levels; first, I don't know whether you can use a QFT to measure functions that are "close to periodic." However, this could perhaps be rectified by defining a new function g: N -> {0, 1/2, 1}, where g(n) is whichever of those three f(n) is nearest to. Then g(n) might be periodic with positive probability.

More crucially: Can we actually devise a function f with the properties outlined above? I would venture to say "yes," since humans can (with high probability) tell whether 300 numbers fall within just three separate, small intervals. And as humans can do, so can do computers. The problem is actually exhibiting a function which we can then prove to work.

Any thoughts on the matter would be appreciated.


Harrison