Preparing for the Quantum Storm

Whether or not they'll ever work, quantum computers pose a big enough threat to online security that cryptographers are already scrambling to adapt.

By Adam Hadhazy|Thursday, August 28, 2014
RELATED TAGS: COMPUTERS
quantum-storm
quantum-storm
Dan Bishop/Discover; background: R.T. Wohlstadter/Shutterstock; computer: Fenton One/Shutterstock

Try not to panic, but quantum computers stand poised to upend today’s information technology infrastructure. These revolutionary machines, though likely at least a decade off, could handily crack the encryption codes that protect everything from email to online shopping and banking, even classified government documents. 

“With quantum computers, there is a real danger that the encryption algorithms we use today may be compromised,” says quantum physicist Andrew Shields of Toshiba. It’s one of many large companies investing in quantum computer-related initiatives — not just quantum computers, but also quantum encryption and networks. “If that does happen, the consequences could be very bad indeed.” 

Online security today chiefly relies on two encryption schemes: RSA (named for its developers), based on factoring the product of two big prime numbers, and ECC (elliptic curve cryptography), rooted in the algebraic structure of points on a curve. These two methods create public keys and related private keys that encrypt data and create digital signatures (so your computer knows it really is Microsoft or McAfee sending you a software update). 

Cracking encryption codes based on either scheme could take normal computer processors thousands of years because they perform operations one after the other, using bits, either 0 or 1. 

Quantum computers, on the other hand, can do loads of operations simultaneously using “qubits.” These machines harness a quantum effect known as superposition, in which a qubit can somehow be both 0 and 1 at the same time. With enough qubits at its disposal, a quantum computer could slash through today’s encryption within minutes or seconds. 

computer
computer
Dan Bishop/Discover; background: R.T. Wohlstadter/Shutterstock; computer: Fenton One/Shutterstock

The tension from this looming threat ratcheted up in January with leaks from Edward Snowden reportedly about a secret $80 million National Security Agency program called “Penetrating Hard Targets,” which is focused on building a quantum computer. Although the NSA doesn’t appear closer to having one than anyone else, the revelation fueled worries over the secret construction of quantum computers. The NSA efforts also suggest that other deep-pocketed governments might go quantum first. 

Some scientists doubt that quantum computers powerful enough to threaten today’s systems will ever arise. It wouldn’t be for lack of trying, though, since the futuristic tech promises far more than mere code-busting. 

Quantum gizmos would process information and solve problems in novel ways, advancing fields such as drug development and weather forecasting. “Governments are going to want to have quantum computers flourish in their country,” says Michele Mosca, a mathematician at the Institute for Quantum Computing at the University of Waterloo in Canada. “They’re not going to want to wait for another country to make an industry out of it.” 

The promise of quantum code-cracking has sparked two trends in digital security. The first, quantum encryption, replaces today’s vulnerable codes with a system based on the kookiness of quantum mechanics. The second involves new encryption codes based on math problems that would stump even quantum computers.

Taking the Quantum Leap

Quantum encryption has made the jump from laboratory experiment to commercial reality. About a year ago, the nonprofit research and development firm Battelle partnered with Switzerland-based network encryption company ID Quantique to complete the first essentially unhackable commercial network in the United States. Connecting Battelle’s headquarters in Columbus, Ohio, to a satellite office in Dublin, Ohio, the network is secured by quantum key distribution (QKD). 

A QKD system ensures that anyone trying to hack into a secure connection to discover the encrypting key irrevocably alters that key, alerting the system to a break-in. Here’s how the Battelle system works: Say Alice wants to send information to Bob. Alice’s computer uses a laser to fire single particles of light, called photons, through two filters into a regular fiber optic cable to begin a transmission. The photons possess one of four polarizations, representing bits: Half the polarizations represent 0, the other half 1. Bob’s computer measures the photons’ polarization when they pass through identical filters at his end of the fiber optic line. Each filter only allows half of the polarizations through. 

By conversing “in the open” through a standard communication channel before establishing an encrypted line, Alice and Bob decide which filters they’re using. As a result, Bob’s computer will receive photons from Alice’s computer without openly announcing their exact polarization. Bob continues accepting Alice’s photons and the two parties home in on exactly which polarizations Alice sends and Bob receives. Ultimately, this exchange gives Alice and Bob a matching code of bits known only to them. That code can be used to create a standard, bit-based key for encrypting data sent between Alice and Bob, now or in the future. 

Then if an eavesdropper — we’ll call her Eve — attempts to snatch some of the exchanged photons to learn the key, the laws of quantum mechanics would trip her up. Bizarrely, the polarizations of Alice’s photons are not determined until Bob measures them, only then assigning them a distinct value. If Eve measures the photons’ polarization while they’re en route, she introduces errors, altering the shared key. “The idea is to use this principle to detect an interception” and abort a data transfer, says Gregoire Ribordy, CEO of ID Quantique. 

With enough quibits at its disposal, a quantum computer could slash through today's encryption within minutes or seconds.

These systems, however, are expensive: as much as 50 percent higher than standard encryption tech. Early adopters of QKD accordingly must be high-security, cash-loaded organizations like governments and banks. “But eventually, as this technique becomes cheaper — and it certainly will as the market gets larger and there is mass manufacturing — it could even roll out to the home,” says Toshiba’s Shields. In a Nature paper last year, Shields and colleagues demonstrated just such a cost-saving technique that could allow consumers to share a single, fancy QKD detector using simple equipment on their end.

Encryption 2.0

Alongside retrofitting the Internet’s security backbone with QKD, deploying new encryption codes also could stump would-be hackers. Four contenders have emerged for replacing RSA and ECC, according to Jintai Ding, a mathematician at the University of Cincinnati. These “post-quantum” cryptographical approaches would take quantum computers just as much time to crunch as normal computers. 

The first involves finding the nearest point to another given point in a lattice, or a set of points in a space, a surprisingly tricky computational task. The second uses theories on error-correction code to generate public key systems: A receiver would possess a code to correct purposefully introduced errors in data that make it unreadable in transit. The third is multivariate, which revolves around difficult-to-solve sets of algebraic equations. The fourth draws short, unique private and public keys out of long strings of bits. Again, our traditional computers are already capable of using such coding schemes, and they’re conveniently complicated enough that quantum computers won’t be better at cracking them.

Adopting any of these novel encryption standards will take time, Ding says, and people will debate which approach is the best. Plus, they’ll face the typical challenges of new technologies, reconfiguring new and existing devices to work with the new standards. Companies might balk at upgrading their hardware and software as long as quantum computers remain the stuff of fiction. Ding worries that reluctant CEOs will just kick the can down the road and let rivals splurge on quantum gear instead.

It’s this sort of procrastination that has security-minded folks nervous. “Planning and action need to start immediately to make our cryptography system robust against emerging quantum technology,” says Mosca, the University of Waterloo mathematician. “If we do so, we can essentially avoid catastrophe.”

Comment on this article
ADVERTISEMENT

Discover's Newsletter

Sign up to get the latest science news delivered weekly right to your inbox!

ADVERTISEMENT
ADVERTISEMENT
Collapse bottom bar
DSCDecCover
+

Log in to your account

X
Email address:
Password:
Remember me
Forgot your password?
No problem. Click here to have it emailed to you.

Not registered yet?

Register now for FREE. It takes only a few seconds to complete. Register now »