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.

Subscribe to:
Post Comments (Atom)

## 1 comment:

http://www.cafb29b24.org/docs/buyativan/#92780 ativan withdrawal length of time - ativan side effects withdrawal

Post a Comment