Quantum Computing Chip

by Rich

Wednesday, September 23, 2009 at 11:07 PM EDT

“I think I can safely say that nobody understands quantum mechanics.”
— Richard Feynman, in The Character of Physical Law

Over the weekend, I posted a note about Mozilla Firefox getting an exemption from some eof the normal regulations on the export of strong cryptography. The cryptography in question is used to implement the TLS/SSL secure browsing (the https: protocol) between the Web site and the user’s computer. It employs a cryptographic technique called a public-key algorithm. Without going into the details, these algorithms rely for their security on the difficulty of factoring very large numbers. (By factoring, I’m referring to the unique factorization of any positive integer as a product of prime numbers — according to the fundamental theorem of arithmetic.) More specifically, there is no known algorithm that can compute factorizations in polynomial time.

The difficulty of factoring large integers using conventional algorithms and computers is fairly well understood. It is always, of course, possible that a breakthrough will be found tomorrow, but the problem has been extensively studied and such a breakthrough seems unlikely. However, there have been discussions of the use of quantum computing, which embodies principles from quantum mechanics, and in theory can solve problems like factorization much more rapidly than conventional computers. A technique called Shor’s algorithm can theoretically compute factorizations in polynomial time. It is difficult to explain how this works without actually digging into the mathematics, but the effect is similar to a massively parallel attack on the problem.

This is a very cool bit of mathematics. It has not had any practical application to date, because no one has yet figured out a way to build a quantum computer of reasonable scale. Now the IEEE Spectrum has a report that researchers at the University of Bristol in the UK have constructed a chip-scale quantum computer, and used it to factor a number using Shor’s algorithm.

There have been various dire and hyperventilating predictions about what this might mean for security, Internet commerce, and the future of Western civilization. I think we can relax for a while. First, the number that was actually factored was only four bits long: 15. And 15 is not just any four-bit number; it has the special form:

(2ⁿ + 1 ) (2ⁿ – 1) or

5 · 3 = 15

the binary forms of which make factoring easier. This is not to minimize the researchers’ achievement, just to say that you will probably not see this technology at Best Buy in time for Christmas. Current, readily available cryptography software can use 4096-bit keys, and the scaling problems of the quantum technology are formidable. Mordaxus, at the Emergent Chaos blog, has an essay on the likely near-term impact of this technology (answer: very little).

Perhaps more to the point, Bruce Schneier has pointed out that all of this is still many years away. Also, although the effects on current public-key cryptography would be severe, the impact on traditional, symmetrical (secret key) cryptography would be considerably less, amounting essentially to reducing the effective key length by half.

This is interesting and important research, but your browsing sessions and PGP-encrypted E-mails are probably safe for a while. And, as Schneier also points out, security is a chain, only as strong as its weakest link; there are many links in current security protocols much weaker than the cryptography they use.