Quantum computers could crack existing codes but create others much harder to break

Feb 12, 2014 by David Kielpinski, The Conversation
Cracking the code. Credit: Flickr/Lars O

The massive release of the US National Security Agency (NSA)'s classified documents by Edward Snowden continues to raise questions about security.

One of these documents deals with the NSA's classified research program in the exotic field of .

This research investigates ways to process information using the laws of , rather than the familiar physics underlying present-day computer processors.

Code breaking

Why should the NSA care? Because the single most famous application of quantum computing is in code-breaking.

During World War II, a team led by Alan Turing used a primitive computer to break the Nazis' Enigma code

The NSA document, which can be found online, deals with the excitingly named project "Penetrating Hard Targets".

An unknown portion of the US$80-million budget is devoted to building a small quantum processor, capable of counting up to four. (No, not four-million. Just four!) This doesn't sound like much, but one has to start somewhere.

Another portion supports research into , which offers new, higher-security secret codes based on quantum mechanics.

The news here is that the NSA had its own secret experimental program. It was already public knowledge that the NSA is interested in quantum computing.

The NSA has been financially supporting non-classified quantum computing research at universities since the 1990s, and many academic journal articles acknowledge NSA support.

Statue of Alan Turing at Bletchley Park. Credit: Flickr/Loz Flowers

In fact, my own PhD work on quantum computing with trapped ions was largely funded by the NSA. One day, our funding managers came to visit. They looked like my maths professors from undergraduate days – slightly nerdy men in sweaters.

I was a little disappointed until I came up with a theory that when they went back to the NSA building, they would tear off the sweaters to reveal the long trenchcoats of a typical spy drama.

Basic maths and cryptography

But iIt's no accident that our NSA funding managers looked like mathematicians. That's what they were. Modern cryptography is, in many ways, a branch of applied mathematics.

The Rivest-Shamir-Adleman (RSA) algorithm, which protects almost all e-commerce, relies on one fact that can be understood with primary-school maths (it can even be used to send love letters).

Multiplying two large prime numbers is easy – say, 547 × 617 = 337,499. There's a simple process that you can follow and making the numbers a little bigger only makes the process take a little longer. In the jargon of computer science, the problem "scales polynomially".

However, suppose someone just gives you a large number and asks you to work the process in reverse.

In our example, you are given the number 337,499 and asked to find out which numbers (the "factors") should be multiplied together to produce 337,499.

This video is not supported by your browser at this time.

You would just have to try factors, almost at random, until you hit on the correct factors by chance (547 and 617).

This would take an exceedingly long time since you would have to perform many multiplications. Making the numbers a little bigger makes the problem much harder – it "scales exponentially"!

The efforts of the world's mathematicians over decades have not been able to find an easy way to solve this problem, and they've certainly tried.

If an easy and practical solution were found, the RSA code would be broken and the prize is, well, most of the world's bank accounts.

In a less criminal frame of mind, you might want to feel secure about your next internet purchase, so you might want to convince yourself that RSA is unbreakable. Email encryption also relies on RSA, so trying to break RSA is core business for the NSA's mathematicians.

The quantum leap in code breaking

NSA headquarters in Maryland. Credit: US NSA

Quantum computers became big business in 1994, when Peter Shor demonstrated theoretically that a quantum computer could find the factors of a large number easily. Making the number bigger shouldn't faze the quantum computer – it's enough to add a little more computing capacity.

However, you needn't worry about your bank account. Translating Shor's algorithm into practice is tremendously difficult. No one has built a practical quantum computer that could break RSA, and that goal is still a long way off - decades, at the current rate of progress.

Remember, the NSA's current program, if successful, will handlenumbers up to four, not exactly the "large numbers" we were talking about earlier.

Quantum cryptography

It's quite likely that a quantum computer will be built eventually, but quantum mechanics can make codes as well as break them. The complementary part of the picture is the NSA's effort in quantum cryptography, which provides new security methods that are resistant even to quantum computers or any other kind of code-breaking.

Messages encoded in quantum systems have a perfect "tamper-proof seal". The Heisenberg Uncertainty Principle tells us that measuring one property of a quantum system must always change another property of the system.

A microchip for trapping atomic ions which could be the heart of a future quantum computer. Credit: Kielpinski lab

One can create a code based on this principle, such that if the coded message is intercepted and read, the process of reading the message actually changes it. The recipient can check parts of the message with the sender over an open line to make sure that there has been no tampering.

Even better news, quantum cryptography is much further advanced than quantum computing. There are already commercial ventures deploying quantum cryptography links for banks and governments. Australia's own Quintessence Labs, based in Canberra, is a major player in this area.

Quantum computing's roots may be in the cloak-and-dagger business, but it has great potential for civilian uses too. For instance, a quantum computer can efficiently simulate advanced materials, such as high-temperature superconductors, at the atomic level.

The ability to direct manufacturing efforts for these materials in a clever way could save tremendous effort. However, like all scientific advances, the uses of quantum computing will ultimately be determined politically and financially.

Explore further: NSA eyes encryption-breaking 'quantum' machine

Related Stories

NSA eyes encryption-breaking 'quantum' machine

Jan 03, 2014

The US National Security Agency is making strides toward building a "quantum computer" that could break nearly any kind of encryption, The Washington Post reported Thursday.

NSA pursues quantum technology

Jan 31, 2014

In this month's issue of Physics World, Jon Cartwright explains how the revelation that the US National Security Agency (NSA) is developing quantum computers has renewed interest and sparked debate on just how far ahead ...

Efficient distributed quantum computing

Feb 21, 2013

(Phys.org)—A quantum computer doesn't need to be a single large device but could be built from a network of small parts, new research from the University of Bristol has demonstrated. As a result, building ...

Physicists demonstrate that 15=3x5 about half of the time

Aug 19, 2012

Computing prime factors may sound like an elementary math problem, but try it with a large number, say one that contains more than 600 digits, and the task becomes enormously challenging and impossibly time-consuming. ...

Recommended for you

Enabling a new future for cloud computing

21 hours ago

The National Science Foundation (NSF) today announced two $10 million projects to create cloud computing testbeds—to be called "Chameleon" and "CloudLab"—that will enable the academic research community ...

Hacking Gmail with 92 percent success

Aug 21, 2014

(Phys.org) —A team of researchers, including an assistant professor at the University of California, Riverside Bourns College of Engineering, have identified a weakness believed to exist in Android, Windows ...

User comments : 1

Adjust slider to filter visible comments by rank

Display comments: newest first

triplehelix
not rated yet Feb 19, 2014
A computer powerful enough to crack a tough code will also be powerful enough to make tough codes.

Thank you captain obvious.