At 05:52 PM 4/23/2002 Tuesday, Enzo Michelangeli wrote: >[...] And if the reason for the 256 bits is the possible deployment, >sometimes in the future, of quantum computers, well in that case we should >stop using PK cryptography altogether.
Hi Enzo! Disclaimer: I am not a quantum mechanic, and I find the whole subject, including quantum computation, deeply confusing. Also, the article I refer to -- an article in Science by the guy who came up with the original factoring result -- is an article that I haven't read, and wouldn't understand if I had. (Neither do I happen to know enough to give a proper citation.) Perhaps someone on this list can fill in some of these gaps, or let us know that I've badly misinterpreted the situation, which is quite possible. All that said, my understanding is that the plausible worst case news from quantum computing would probably not require us to give up PK crypto. My understanding is that the article I'd like to cite states something like the following: 1) Factoring is special because it's all pervasively about periodicities. The author's original factoring proposal took advantage of this in an essential way in order to show a potential exponential speedup. 2) For NP problems in general, since they are search trees with only polynomial depth to an answer but exponential fanout of choices, by using superposition, quantum computation may indeed be able to give an exponential speedup on the first phase of the search -- finding the answer. 3) The problem then is reporting the answer out. The superposition that found the answer co-exists with an exponential number of superpositions that don't. My understanding is that the paper is postulating an upper bound for search problems without peculiar special properties (like the periodicities of factoring) -- the most we can get is an order-of-square-root speedup on the problem as a whole. If the above description is approximately right, then the remaining question for PK is, can one design a PK system now whose trapdoor depends on a search problem that we can be confident cannot be transformed into one with the enabling peculiar properties? AFAIK, this question has not been examined. Btw, out of fear that quantum computation might destroy PK but not single-key, I worried about whether one could do cryptographic capabilities in such a world. http://www.erights.org/elib/distrib/captp/unibus.html is a protocol sketch of a distributed capability protocol that depends only on single-key cryptography. But I hope it will never be necessary. ---------------------------------------- Text by me above is hereby placed in the public domain Cheers, --MarkM --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]