Y'arr! Cryptography and piracy.

Ahoy, me mathematical mateys. Seein' as how today be the International Talk Like a Pirate Day, I decided to make a piratey post. Y'arr.

Y'arr! Here be a rough formal definition o' what ye can use for public-key encryption. Arr. A function f:Zx(Z/nZ) -> Z/nZ be a trapdoor function if:

1. Ye may compute f(m,k) smartly (in polynomial time).
2. The problem o' findin' a preimage o' k \in Z/nZ, given fixed m, is in NP.
3. There be some t not dependin' on k so, given t, findin' a preimage o' k with fixed m is in P.

Aye, I claim that these be the functions from which ye can construct a public-key cryptosystem. If ye disagree with me, ye can walk the plank. Otherwise, we'll continue:

Call the complexity class which consists o' findin' preimages under trapdoor functions PK (for public-key. Or plank, which be like a trapdoor, but better suited for seafarin' folk.). Is PK contained in FBQP?

If the answer be "aye," then pirates rejoice! With a quantum computer, ye can crack any classical public-key system, which would allow ye to commandeer credit card information and much, much more, without the risks of scurvy and losin' limbs that make pirates' health-insurance premiums so #@#$in' high.

However, I believe that the answer be "nay." Since P is in BQP, this would imply P < NP, so I'm not expectin' any o' ye landlubbers to solve it. But if ye can give me evidence of why my hunch is correct, this ol' scurvy dog'll be forever indebted. Y'arr.

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