Company claims working 16-qubit quantum computer today, 1024-qubit in 2 years

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


jason said…
Hey denis

I was wondering if/when you'd post about this. I've been following D-Wave now for a while and they are definitely sticking their necks out with the claims they are making but it's really cool to see a company pushing this technology as far as they have.

On the topic of quadratic speedup, I read somewhere that if your original problem is order of O(n^n) the speedup is (I may be incorrect here) O(sqrt(n^n)) = O(n ^(n/2)). This of course is for problems that scale well onto the architecture.

As far as public-key crypto goes, there are some schemes that are rumoured to be safe, or at least safe for a very long time. I don't think they've been proved as so however - just speculated to be.

Diffie-Lamport-(forget..Markle?) and McEliece spring to mind but I think there is another signing method and another scheme that are thought to perhaps be safe. I'm not very well versed in the way of crypto but I believe McElice has some major drawbacks. (Ok a quick check on Wikipedia says that ciphertexts are twice as long as plaintexts and the keys are 2^19 bits long. Yikes)

Here's a link to a blog by D-Wave's CTO himself, it's excellent and has some great resources (and the pictures, if you haven't seen them):

and here's a YouTube video of the presentation (check out the related videos as well):

Ugly YouTube link

This thing is cool. Like 'one of the coldest objects in the known universe' cool. I believe the heart is a superconducting nobium element chilled to thousands of a K from absolute zero. Awesome!

Popular posts from this blog

When monospace fonts aren't: The Unicode character width nightmare

Circumcision as an adult, part 1

Circumcision as an adult, part 2