The Clock Is Ticking On Encryption

CWmike writes "In the indictment that led to the expulsion of ten Russian spies from the US in the summer of 2010, the FBI said that it gained access to their communications after surreptitiously entering one of the spies' homes, during which agents found a piece of paper with a 27-character password. The FBI had found it more productive to burglarize a house than to crack a 216-bit code, despite having the computational resources of the US government behind it, writes Lamont Wood. That's because modern cryptography, when used correctly, is rock solid. Cracking an encrypted message can require time frames that dwarf the age of the universe. That's the case today. 'The entire commercial world runs off the assumption that encryption is rock solid and is not breakable,' says Joe Moorcones, vice president of information security firm SafeNet. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing."

What exactly is being broken by quantum computers?

[vadim_t]

People generally mention that quantum computing will spell the doom for current crypto, but from what I read on different sites, it seems that it's not exactly that. So I would really appreciate if somebody could clarify it. For instance, on Wikipedia there is this:

Integer factorization is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes).[5] By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to decrypt many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem.

It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case,[10] meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search

So, the problem is only for public key crypto, and for AES we just switch to 512 bit keys and no problem? Also if quantum computers don't do all that great against AES, wouldn't be it just a problem of finding somethinig else they have trouble with that could be used for public key crypto?

Not exactly

[betterunixthanunix]

For one, AES is designed to have fixed key sizes, so "just switching to 512 bits" is not as trivial as you may think. Also, not all public key cryptosystems are based on the RSA problem.

Quantum computers can factor the product of two prime numbers in polynomial time, so RSA would be broken. A modification of that algorithm allows certain cases of the discrete logarithm problem to be solved efficiently as well, so DH and ElGamal would be broken also. Luckily, quantum computers are not yet known to be able to solve NP complete problems in polynomial time, so cryptosystems based on NP complete problems (Polly Cracker systems, for example) would still be secure assuming that P != NP. There are also hard lattice problems which quantum computers are not known to be more efficient at solving, which can be used to construct cryptosystems, and there was an early public key cryptosystem based on a group theoretic problem which is known to be secure against quantum computing.

So basically, quantum computing is not really a problem at all, at least not in a theoretical sense. It throws a bit of a wrench into some standard hardness assumptions, but nothing too bad.

The FBI has vigilantes

[elucido]

And they'll break any law to accomplish the mission. The FBI has murderers and serial killers who are confidential informants. They also have thieves who are confidential informants.

It's a surprise to me that some Russian spies who you'd expect would be trained to deal with counter intelligence would be so careless.

no need for multi-million qubits

[Ignatius]

A couple of thousands do (about 5 times the lenght of the number you want to factor). But what you really need is the ability to perform multi-billion gate-operations (while the QFT itself is quadratic, Shor also uses modular exponentiation which makes it a cubic O(n^3) algorithm) within the decoherence time (usually measured in milliseconds or seconds) and with a technical accuracy to the tune of 99.9999999% - a quantum computer is, after all, an analogous device: qubits don't "lock in"; a NOT-gate e.g. thus has to be an exact 180 deg; rotation and neither 179.999 nor 180.001 deg (does not matter for a couple of gates in toy problems but those imperfections add up).

Quantum error correction can somewhat mitigate the former problem (at the cost of about one order of magnitude overhead in both space and time) but not the later. So if it's feasible at all (which is by no means certain as there might be hidden constraints on scalability), we probably won't live to see it.

ignatius