Cryptographers fear prospect of quantum computing

Wired on Friday: Never believe anyone who says that mathematics - especially advanced mathematics - is useless

Wired on Friday: Never believe anyone who says that mathematics - especially advanced mathematics - is useless. At this point in history, we are helplessly dependent on the promises and the proofs of some of the most abstract and airy mathematics possible.

And not just that wielded by scientists to design spacecraft and plot nuclear power stations. The security of financial, business and political communications rely on these mathematical theorems. Even mathematicians admit that (easy come, easy go) one day that dependance could mean that all our privacy and our secrecy could come crushing down around us.

The trouble is: when it happens, will we know? Or will only China or the United States's top mathematicians know the world is open to their prying eyes again.

Here's the issue. Billions - probably trillions - of dollars worth of financial and other communications these days are kept private through the use of a mathematical technique called public key cryptography.

READ MORE

Public key encryption was such a godsend to secrecy that the US government desperately tried to keep the formulae behind it a secret: dissuading public discussion about them, and even at one point classing them as a munition too dangerous to export.

For a long time now, the public key cryptography cat has been out of the bag. And a good thing too - most of the secure communication you use on the internet (such as talking to your bank, or other websites where the little padlock lights up on your browser screen) takes advantage of public key cryptography. Public key cryptography lets you keep digital messages secret, even as you pass it down public interlinked networks such as the internet, where you never know whose machine your data is flowing through, and who might be peering at it.

You can talk securely to strangers, confident that, should you both choose, only you and they will be able to decode your transmission. You can even use public key cryptography to digitally "sign" documents, proving that it was you who sent them, or gave your consent to their contents.

Much of the privacy, and authentication systems we have in the real world - the secrecy of a sealed package, the reassurance of a signed letter - are currently reproducible in the online world. They may even be more secure in the virtual environment.

It's relatively easy to fake a signature after all, but it's impossible to fake a digital signature. In theory, that is.

The theory itself has both the confidence of rigorous mathematical proof behind it, and yet with that ever-nagging doubt mathematicians have that one day their world will be turned upside-down by a better, smarter way of doing things. We know exactly what public key cryptography depends upon; we're fairly sure that what it depends upon is currently safe from harm; but, sadly, we also have a good idea where the threat that might undermine it will arise. The secrecy of all these secure communications relies on a simple rule.

It's easy to multiply two primes together and get a larger number - but if you start out with the larger number, it's incredibly difficult to get back those two original primes. A process like that: easy one way, hard the other, is the foundation of public key cryptography. How tough the encryption is to crack depends on the trickiness of that last process.

Now, we know how to make it so hard as to be impossible - we can create primes big enough to ensure that it would take the lifetime of the universe for modern computers to unmultiply them. If computers get appreciably faster, we only need to add a few digits to the primes to outpace them again.

That's with modern computer technology, and most conceivable descendants of its principles. But, one day, computer scientists expect another model of processing data to become practical: quantum computing.

Quantum computing doesn't depend, as all contemporary computers do, on binary "bits", ones and zeros. Quantum computers use the fuzzy nature of quantum physics to create quantum bits or "qubits". Computers that use qubits instead of bits can process more than one number at the same time. A qubit can be one, or zero, or one and zero.

To give you an idea of how weird and unsettling a quantum computer is, let me just say that many computer scientists feel comfortable imagining them as ordinary computers that happen to operate in multiple universes simultaneously. And they only do that to feel comfortable about them.

Quantum computers are almost impossible to build - the largest built has less qubits in it than a single letter stored in a computer has bits.

But if we ever manage to work out how to build a larger machine, the security of the world's data would quickly come tumbling down. A sufficiently powerful and long-lived quantum computer could find the factors of a large number in minutes.

A few key targets for such a cracking effort could undermine all website communications online, or allow assailants to install lethal software on Microsoft machines undetected. Other targets would let them crack banks or stock market networks.

We're a long way from that point, however. Or are we? Recent revelations have shown that British intelligence knew about public key cryptography for a decade before it became public. The United States's National Security Agency has become remarkably liberal these days about the use of public key cryptography.

If a viable quantum key-cracker exists, we - and the world's financial institutions - may be some of the last to know. Successful quantum computing may truly be the last secret left on earth.

Danny O'Brien is activism co-ordinator of the Electronic Frontier Foundation