Quantum computing

[Robert J. Hansen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

I'm going to talk about Grover's algorithm and Shor's algorithm, plus  
a good bit on computational complexity theory.  The two algorithms  
are completely different and tackle completely different problems.   
When I talk about computational complexity theory I'll tie the two  
algorithms together to show how and when each one is used.

Please bear with me.  This is going to be long.

> So I take your word for it, that 256 bit keyspace searches are
> infeasible, even in the quantum-computer world. I assume that advances
> in factorization are comparably insignificant...?

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.

This is important because brute-forcing a key can be thought of as  
searching through an unsorted database trying to find the right  
entry.  In math we'd say these two problems are isomorphic to each  
other.  "Isomorphic", for the purposes of this email, just means that  
we can convert one problem into a different problem with some trivial  
transformation.  As with most things in math the real definition is a  
little more involved, but this one will work for our purposes.

For instance, multiplication and division are isomorphic to each  
other.  To divide by 3, just multiply by 1/3.  To multiply by 3, just  
divide by 1/3.  Etcetera.  That's isomorphism in a nutshell.  Please  
remember what isomorphism means; you're going to see it again later  
in this email.

Searching through an unsorted database and brute-forcing a key are  
isomorphic to each other.  So we do a trivial transformation on the  
brute-forcing math problem to convert it into a database search  
problem, and then we sic Grover's on it.

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.

So the best way to defend against exhaustive key search in a quantum  
world is to either (a) trust that quantum computing is going to  
remain "in just a couple of years" for the next few decades (which  
may very well be true), or (b) multiply your key sizes by a factor of 2.

The principal reason why AES supports a 256-bit key is because of the  
possibility of quantum computing and Grover's algorithm.  Brute- 
forcing a 256-bit cipher with Grover's is as hard as brute-forcing a  
128-bit cipher with a conventional computer... absolutely  
ridiculous.  :)

> 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.

When this monstrously huge quantum computer was demonstrated by IBM,  
it created a huge hue and cry in the press.  Most cryptographers  
dismissed this as much ado over nothing.  Schneier is apocryphally  
quoted as saying "yeah, any RSA modulus with fewer than eight bits is  
now truly fucked."

But wait, the good news doesn't stop there.  Not only is quantum  
computing a long way off from being able to tackle RSA and/or El  
Gamal, but Shor's algorithm is _only_ applicable against asymmetric  
systems built on the integer factorization problem and/or the  
discrete logarithm problem.

For instance, Lamport signatures are a perfectly valid asymmetric  
signature scheme that are secure even against quantum computing.  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.




Now for the real head-bending things.  Why is it there's such an  
efficient way to solve the integer factorization problem and the  
discrete logarithm problem, but such an inefficient way to brute- 
force a key?

Computational theory is the branch of mathematics that's concerned  
with the fundamental limits of what computers can do.  In  
computational theory, we have several different classifications of  
problems, depending on how much time and space are required to solve  
them.

There are _tons_ of different complexity classes.  The ones we're  
going to be talking about here are P, NP, and NP-COMPLETE.

A problem is said to be in P if and only if it can be solved in an  
amount of time proportional to its input.  For instance, the bubble  
sort runs in time proportional to the square of its input.   
Bubblesorting one hundred elements takes a hundred times larger than  
bubblesorting ten elements.

A problem is said to be in NP if and only if verifying the answer for  
the problem is in P.  For instance, factorization is clearly in NP.   
If I tell you that 37 and 73 are the two factors of 2701, you can  
easily multiply 37 and 73 together to prove it.  Since, once given an  
answer, proving the answer is in P, we know that the problem of  
finding the answer must be in NP.

NP-COMPLETE means "this problem is one of the hardest problems in  
NP".  "Hardest" here has a very precise meaning which I'm going to  
mostly gloss over.  You can think of it as "a problem is in NP- 
COMPLETE if it is isomorphic to another NP-COMPLETE problem".

(This raises the question of "so how do we find the first NP-COMPLETE  
problem?"  Ah, well, that's why we have so much respect for Stephen  
Cook, who thunked down a couple of hundred pages of mathematical  
proof establishing a problem called SAT as the hardest problem in  
complexity class NP.  Once Cook had done his heroic feat of  
mathematical hacking, all that us Johnny-Come-Latelies have had to do  
is show other problems are isomorphic to SAT.)

Finally, you can always punt a problem into a higher complexity  
class.  If you want to, you can convert a P problem into an NP- 
COMPLETE problem... but you can't convert an NP-COMPLETE problem into  
a P problem.  That would be a downward punt, and it's not allowed.

Got all that?  Great.  Now it should be easy to follow the rest.



When we brute-force a key, we are effectively punting the problem up  
into NP-COMPLETE.  That means it's _really, really hard_.

When we discover mathematical weaknesses or flaws in a cryptographic  
algorithm, if there's determinism we can exploit, then we're tackling  
the problem in a much lower complexity class.  That means it's much  
easier.

Shor's Algorithm applies to two specific problems that live in NP.

Grover's Algorithm applies to _every_ NP-COMPLETE problem.

Shor's Algorithm is as fast as it is because it's (a) highly  
specialized and (b) solves an easy problem.  Grover's Algorithm is as  
slow as it is because it's (a) highly general and (b) solves a very  
hard problem.







... One last word.  Computational theory purists will tear this email  
to absolute shreds.  After all, how can I talk about quantum  
computing without talking about complexity classes BQP or the P=NP  
problem or...?

The worst part about it is, _they're absolutely right_.

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.


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)

iQEcBAEBCgAGBQJGJr5QAAoJELcA9IL+r4EJn/YIAIxyk7mP5SH/rxOxjCe3M+AH
A8NOgKDMf8Ty9DtRRVedLVOjnZccHJaiK2IqHWu5IcvYQSMK4ljHkclqvtnp9QWq
VVquVUakq7gceG4R1BYukdsIoZJY9eatH6n8/wZTdG6V+mzw3RQQyrzuPA6azStr
iFaGuPraKXndnCVYqvsu3sMPq59ZBU4biAn0H59WGlZ8nr8a6GY8JFSu26aE3jUJ
QLJLj6xPU7cS2+a0v3bZYWdTdwjDp9vrc26QzIk1gnX51Ity9+fJb7SO1/ZKvban
LGXg6fKkKB0E5wDP8P6mLuSkm94a9oTAaQ+L0zHMVLtGJ+xP4FjbsrHoOiAF130=
=YkAE
-----END PGP SIGNATURE-----