Count all the legs, divide by four
Summary: Secure web sites, encrypted email, even bank transfers all use ciphers that rely on an unproven mathematical assumption: that big numbers are, like, hard.
A farmer was showing a particularly smart kid around his fields, and frustrated by the child's endless demonstrations of cerebral aptitude, he decided to teach him a lesson. He brought the kid to a field that was packed with grazing sheep, hundreds of them all moving around, and challenged the boy: “If you can guess the exact number of sheep in this field, I'll give you all of them!”
The boy looked thoughtful for a moment, and his eyes darted back and forth rapidly. Presently he announced, “two hundred and fourteen.”
The farmer gaped, too stunned to calculate his loss yet, “how on Earth did you do that?”
“Oh it was simple,” the boy replied. “I just counted all the legs, and then divided by four.”
You can take it for granted that your name, address and credit card number travel secretly over the Internet every time you make a purchase online, all thanks to the wonders of encryption. In fact, it isn't just the transaction between you and the web site that relies on “unbreakable” digital secrecy, either: business-to-bank transactions all use the same ciphers at varying degrees of strength, but none so weak that it could take a supercomputer less than our Sun's lifespan to break. We put so much trust in the mathematical assumptions behind these encryption methods that we allow trillions of dollars to flow across the world's wires this way every year. But those assumptions have never been proven, and a breakthrough in the development of Quantum Computers by an Austrian team this year might make all of those ciphers useless within our lifetimes.
The mathematical assumption in question is all about the problem of finding the prime factors of a big number. To refresh memories, a prime number is any number that's only divisible by 1 and itself. So when we say we're looking for the factors of the number 15, for example, then we're looking for two prime numbers that give us 15 when multiplied. In this case, those prime numbers are 3 and 5. That example was easy because it was small, but modern encryption deals with numbers of a hundred digits or more, and the assumption is that these are much harder to factorise. Indeed, given a 100-digit number it would take a computer capable of a billion operations per second about 12 million years. Need to make it tougher? Just add more digits.
So without a shortcut, prime factors are used as the basis for making the cipher behind Public Key Cryptography (PKC) so difficult to crack. The first PKC system was invented in 1977 by the math trio Ronald L. Rivest, Adi Shamir and Leonard M. Addelman, who named their algorithm RSA after their last initials. RSA is the number-one PKC system in use today, and you'll find their code in your web browser and possibly also your email program. PKC's only weakness—that unproven assumption—is related to its biggest advantage: unlike so-called symmetrical ciphers, PKC doesn't require a secure channel to exchange a cipher key over. Your computer generates a special private key, and then uses that to generate a public key. The public key can be used to “lock” messages, but only the private key can unlock them.
It's assumed that you can't easily deduce the private key from the public key, so it doesn't matter if an eavesdropper gets her hands on it. Hence the name Public Key Cryptography; everybody gives away their public keys so anybody can lock a message only you can open. As it happens, a seamless exchange of public keys is going on in your browser's background every time you buy something over the web. Anybody who's managed to eavesdrop the conversation between you and the e-commerce site will see nothing but useless garbage, and being able to capture the public key doesn't help them.
(Since asymmetrical encryption is very slow, what actually happens is that your browser and the web server use PKC only long enough to exchange a key for symmetrical encryption, which is faster. The symmetrical key is called a “session key”, and it changes frequently during a session so an eavesdropper can't use cryptanalysis. This is not relevant to the issue, though, just a bit of trivia.)
The security of PKC has been durable for decades now, because no matter how fast computers get, you can just add another digit to the size of your key pair. But what if there really was a shortcut to those prime factors after all, and one that couldn't be put-off by adding more digits? Indeed, it's a disturbing prospect to know there is such a shortcut after all. It was invented in 1994 by Paul Shor, a researcher at AT&T Bell Laboratories in New Jersey. It works by simultaneously operating on all possible numbers that can be represented by the number of digits that make up the number you're trying to factorise, and employing some basic high-school math on the results. If the number you're trying to factorize is 6523, then that's four digits and the number space stretches from 0 to 9999. A hundred digit number means... er... an awfully big number space.
It's a bit like counting all the legs and dividing by four.
But before you throw away twenty years of reliable encryption, there's a catch to overcome first: Shor's algorithm only works when run on a theoretical machine called the Quantum computer, and until now there were serious doubts that it was even possible to build one. Yet recent developments coming out of the University of Innsbruck in Austria suggest it's not that far away. As reported in this month's Nature, an early type of quantum computer was recently built and successfully used to solve a simple, but foreshadowing problem.
What makes quantum computers unique is the ability to do calculations on more than one possible input at the same time. The first working quantum computer--built in Austria by Stephan Gulde and his collaborators and announced this January--demonstrated this behavior with the first ever execution of a quantum program: determining the fairness of a coin in a single step. It doesn't sound like much, but its enough to send shivers down the spine of anyone who depends on the durability of difficult math problems.
Let's say that a coin is fair only if it has a head and a tail. That means a coin with two heads or two tails would be considered unfair. Normally you'd figure this out in two steps: looking at one side and then turning it over to see the other, and a conventional computer would have to do the same. But according to a technique described by David Deutsch and Richard Jozsa—two pioneers of quantum computer theory—it's possible to see both sides at the same time.
The Deutsch-Jozsa algorithm exploits a property of sub-atomic particles known as superposition. It's based on the Heisenberg Uncertainty principleD, which states that you cannot know the position and speed of a particle at the same time. From that, mathematicians can conclude that a particle could store two pieces of information at the same time. We call particles in a state of superposition Qubits, or “quantum bits”, comparable to the bits in conventional computers, but able to store more than one value at the same time. Now this doubling-up of information sounds just like the kind of thing hard-drive makers would love, but what's even more profound is that with a qubit you can test two possible inputs at the same time. In this case, two possible inputs are a coin that's fair, or not fair.
In Gulde's quantum computer, the coin is represented by a calcium atom suspended in an ion trap and cooled to super-low temperatures by lasers. Its superpositioned state can be modified by lasers, too, which store two values that each represent either heads or tails. So “1,1” is heads and heads, “1,0” is heads and tails, “0,1” is tails and heads, and “0,0” is tails and tails. Once programmed with these superpositioned states, the coin's fairness can then be queried by laser again, and it only takes one step to do it. On a conventional computer, the coin's four possible states must be represented by at least two different bits, which means you need two steps to decide whether the coin is fair or not.
Nothing scary about that, it seems, but what it proves is that quantum computers using superposition can work, and that larger and more useful versions will come as quickly as hard work and ingenuity allow. Shor's algorithm needs a computer that can evaluate all possible numbers at once, and given enough Qubits superpositioned to represent them all, this is theoretically possible. It may only be a decade before the Shor algorithm for factorising large numbers can be run for the first time, too. And on that day, the security we've based our commerce on will evaporate.
Gulde's experiments show that the clock is ticking on the infrastructure we use to keep our communications private, and an alternative must be found soon. One possibility, ironically enough, also involves quantum particles. Quantum CryptographyD (QC), like PKC, is also meant to solve the problem of exchanging a cipher key securely, and like quantum computing it also relies on Heisenberg's uncertainty principle. The idea is to transmit your key as a series of encoded photons, and then use a non-revealing method of confirming that both sides of the transaction got the same key. Since the act of intercepting or observing a photon will change it, the legitimate parties in the transaction will know if the key exchange was eavesdropped, and try again with a different key until the eavesdropper gives up.
But alas, quantum cryptography won't be able to work over today's Internet without huge and expensive upgrades to its infrastructure. Since the photons used to exchange the key must travel without interruption, a conversion to all-optical networks may be needed. Non-trivial for most, and worse yet, there's a limit to how far you can transmit a photon through fiber-optic cable. In this case, signal boosters wouldn't help because they'd alter the state of the photons and look the same as an eavesdropper.
What quantum physics giveth it also seems to taketh away. Our conventional computers are based on a bit of quantum know-how, too, specifically the transistors that make up CPUs. Whatever solution comes to the aid of our security needs in the future, it's very likely to be as small as atoms themselves.
