If this is true (via Larry O'Brien), then security on the Internet is up for some serious rearchitecture.

I may be wrong because I don't know how long it takes for a quantum computer to run one iteration of Shor's algorithm, but they only need four to eight runs on a 1024-qubit machine to break a 512-bit RSA key. In a few years, it sounds like they will be able to break them. And once they have 1024-qubits, why couldn't they have 2048 or 4096 a few years down the road?

On the up side, as far as public key cryptography is concerned, it does look like the only way to access these quantum computers for the next decade or so will be to purchase services from a company that has one. Even so, it's going to be disconcerting to know that there will now be people on the net who will be able to forge any public key signature and decrypt any public key-encrypted communication, if they deem it expedient to do so.

Then perhaps in a decade or so, the first quantum computers are going to become readily available, and then public key cryptography is completely dead and done with. We're going to have to rely entirely on symmetric ciphers from then on - which means no signing, no certificates, and lots of passwords to keep confidential to ensure the security of every communication link you care for.

Does anyone know of any public key encryption or signing scheme that cannot be defeated by a quantum computer?

If one does not become known soon, then dark times are ahead for secure communication.

Oh, and don't you buy into the hype surrounding 'quantum cryptography' - the idea of quantum mechanics coming around to your protection by enabling you to securely transmit symmetric cipher keys. That's bollocks. This 'quantum secured' key transmission only works across limited distances because there can be no amplifiers on the way, and everyone who wants to exchange keys this way needs to have special equipment and be connected to everyone else by fibre-optic cables. A fibre-optic quantum key distribution network reaching every village? Perhaps the bank - but not your house.

Right now, public key algorithms allow you to communicate securely at any distance, across any network, across space and time, with anyone on Earth. This will be rendered impossible when quantum computers arrive, and 'quantum cryptography' is fundamentally too limited in its capability and unwieldy in its use to be a solution. People like you and me are going to have to either:
  • exchange our keys by meeting in person; or
  • trust someone else with carrying our keys (courier, telephone company).
Most significantly though, digital signatures are going to be impossible. There will be no way to sign a message, or an executable, and publish it. It will be impossible to verify the authenticity of information if it's communicated publicly. I think that's a loss.

Update 1: Then, this article indicates that what D-Wave has built is not a 'real' general-purpose quantum computer after all, but rather 'a special-purpose machine that uses quantum mechanics to solve problems'.

So, can it be used to break big RSA keys?

If it can't, will they be able to build one that can?

If they won't, will NSA?

(Have they? :-) )

Update 2: Scott Aaronson published a number of rebuttals to the D-Wave news (1, 2, 3).

Among the things I learned:
  • Quantum computers most probably cannot solve NP-complete problems in polynomial time, which is what most lay (read: journalistic) writing on the topic would lead you to believe. For the hardest problems there's at most quadratic speedup, which doesn't really help much when the task is exponential to begin with. So much for claims that quantum computers might one day allow us to calculate the answers to essentially anything.
  • However, integer factorization is probably not an NP-complete problem. Wikipedia says it's suspected to be outside of P, NP-complete and co-NP-complete classes. Furthermore, due to the Shor algorithm, it is known to be in BQP, the class of 'decision problems solvable by a quantum computer in polynomial time'.
  • The class of quantum computer apparently being built by D-Wave is an adiabatic one.
  • Barbara Terhal of IBM, or someone purporting to be her, claims to be unaware of any way to 'cast Shor’s factoring algorithm as a stoquastic adiabatic computation'.
So it looks like RSA is safe, at least, for another while. :-)