Eliezer writes:
> hal@finney.org wrote:
> >
> > The largest key sizes in common use today are 256 bits. If quantum
> > computers become possible they effectively halve the key length, so it
> > would require 2^128 operations to brute force such a key.
>
> Are you sure about this? I know that in the general case it's been
> demonstrated that you can get at least an O(2^N) to O(2^(N/2)) speedup on
> generic searches. But I was under the impression that factoring was not a
> generic search, and that the problem required 3N qubits to directly crack
> an N-bit number (in constant time?). Unfortunately I cannot remember my
> source on this at all, so it could just be a figment of my imagination.
I was talking about symmetric-key algorithms like DES or AES, not public
key algorithms. For these the generic search results are the best you
can do.
With the public key algorithms in use today based on factoring and
discrete logs, the situation is worse, as you don't even get exponential
costs. However from what I have read it takes more like N^2 qubits once
you take into consideration quantum error correction, so it would take
something like a million qubits to crack a thousand bit key.
Hal
This archive was generated by hypermail 2b30 : Fri Oct 12 2001 - 14:40:58 MDT