**Next message:**DOC454: "Re: What is the Extropian answer to war? (was: Raisin Bombers over Afghanistan)"**Previous message:**Damien Broderick: "Re: Raisin Bombers over Afghanistan"**Next in thread:**hal@finney.org: "RE: Steganography"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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

**Next message:**DOC454: "Re: What is the Extropian answer to war? (was: Raisin Bombers over Afghanistan)"**Previous message:**Damien Broderick: "Re: Raisin Bombers over Afghanistan"**Next in thread:**hal@finney.org: "RE: Steganography"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b30
: Fri Oct 12 2001 - 14:40:58 MDT
*