Robert J. Hansen
rjh at sixdemonbag.org
Thu Apr 19 02:56:48 CEST 2007
-----BEGIN PGP SIGNED MESSAGE-----
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
> 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
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
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
... 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
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)
-----END PGP SIGNATURE-----
More information about the Gnupg-users