Quantum computing

[Anders Breindahl]

Hi,

On 200704181956, Robert J. Hansen wrote:
> Please bear with me.  This is going to be long.

Introductory cryptography in the middle of the night. Why would I miss
it? :)

Thanks for answering.

> As mentioned, Grover's is the best we can do for quantum speedups to  
> brute-forcing.  Grover's algorithm is a technique for using quantum  
> mechanics to search through a database of N entries in time  
> proportional to the square root of N, using an amount of storage  
> proportional to the logarithm of N.
> 
> Now, that said, Grover's has limits.  Its first constraint is that it  
> doesn't make problems trivial.  It just increases our ability to deal  
> with them.  Brute-forcing a 128-bit cipher using a traditional  
> computer is a ridiculous proposition, but using Grover's, it becomes  
> as hard as brute-forcing a 64-bit cipher... hard, but possible.

The executive summary being that increases in key sizes makes
traditional symmetric cryptography keep up with advances in quantum
computing, such as Grover's algorithm for searching the keyspace.

> > Then... It would seem that quantum computers poses no threat to
> > traditional cryptography -- helped by increases in key sizes...?
> 
> Quantum computing poses no threat to symmetric cryptography.   
> Asymmetric cryptography, however, gets a little funky.
> 
> Shor's algorithm uses quantum mechanics to solve the integer  
> factorization problem (and, I believe, the discrete logarithm  
> problem) in extraordinary short time.  The downside of Shor's is it  
> requires an insane amount of memory--you need two qubits for each and  
> every bit of the number you're trying to factor.  So if you're trying  
> to factor a 2048-bit RSA key, you need over four _thousand_ qubits.
> 
> Our current largest quantum computer is about fifteen qubits.

Which I also remarked in the original post. However, when (if?)
commercial interests grab a hold of quantum computing, huge leaps in
cost of production perhaps could be achieved, making memory-rich quantum
computers abundant -- at least, from my chair, there's no obstruction to
this future. (?)

> If and when quantum computing develops to the point where a research
> lab gets a couple of hundred qubits together, the OpenPGP working
> group will almost certainly add asymmetric algorithms that are highly
> resistant to quantum computing.

Although this fight between attacking and defending computer security
measures is probably inevitable -- no final solution will probably be
found -- this pragmatism causes me to ponder the scenario in which
something like Rice' theorem could be established for quantum computers'
ability (or traditional computers' inability): Something that pops out
of the blue and shatters all hope for traditional cryptography...
Perhaps only in the long run, but still inevitably forces a move towards
other measures of security.

It's somewhat a political issue, too. Not that it can be solved
politically, but it has political consequences -- will cryptography (or
computer security in a more general sense) once again be for those who
can afford it?

-- But leave that be. For now, it's technical.

> You're asking a very, very detailed and technical question that  
> requires a ton of disciplined study just to learn the language needed  
> to describe the boundaries of the problem.  If you really want to  
> know this material, you need to take a graduate-level course in  
> computational theory and a strong undergraduate course in quantum  
> physics.  You'll also need enough background in mathematics not to go  
> running screaming from the room when people start talking about  
> Hadamard matrices and discrete Fourier transforms and everything else  
> that goes along with it.

I'm already on it.

Regards, skrewz.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : /pipermail/attachments/20070420/dccbc784/attachment.pgp