Is There a Quantum Mechanic in the House? (was: Lucky's 1024-bit post [was: RE: objectivity and factoring analysis])

[Mark S. Miller]

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 majordomo at wasabisystems.com