The quantum Y2K moment

03 Dec 2018 Margaret Harris

The advent of quantum computers threatens many of the encryption systems that keep online communications secure and make e-commerce possible. Margaret Harrisinvestigates plans to make the Internet safe for the quantum era

(Courtesy: Shutterstock/jijomathaidesigners )

Winfried Hensinger wants to build a computer the size of a football pitch. He’s aware that the idea may be a tough sell. Scientists and engineers have laboured for decades to transform the room-sized machines of the 1940s and 1950s into devices that fit on a desk, in the palm of your hand, and even – as with a chip unveiled at IBM last March – inside a grain of salt. Why would anyone take such a gigantic step backwards?

The answer lies in the architecture of Hensinger’s proposed machine. Instead of performing calculations with classical 0s and 1s, the computer he and colleagues at the University of Sussex in the UK hope to build would exploit the quantum properties of a billion ytterbium ions. Hensinger’s blueprint calls for these ions to be kept aloof from their environment with magnets and individually shuttled into interaction zones within a vast grid of microfabricated traps, using a field of microwave radiation to control their movements. The result, he says, would be a computer that can unravel “tremendously complicated problems that would take billions of years to solve on even the fastest supercomputers”.

Hensinger’s dream is exceptional in its scope, but his goal is far from unique. In recent years, governments and corporations such as IBM and Google have poured billions into quantum-computing research. Thanks to their investments, and the efforts of thousands of scientists worldwide, it is no longer absurd to think that a large-scale quantum computer will – somewhere, and in some form – become a reality. It won’t happen overnight, of course; today’s state-of-the-art devices boast no more than a few dozen qubits, and Hensinger acknowledges that it would take a “massive” amount of work (and around £100m) to scale his current prototype up to the billion-qubit level. But he insists that overcoming these challenges is a matter of “engineering, not physics”, and the mood among quantum physicists is generally buoyant. Few would bet against a universal quantum computer emerging sometime in the next 20 years.

There’s just one problem: when that happens, it may break the Internet.

A quantum problem…

To understand why quantum computers pose such a threat, consider the encryption systems that keep nefarious actors from eavesdropping on credit card details and other sensitive data sent over the Internet. Most of today’s encryption systems are built around “trapdoor functions”: mathematical problems that are easy to solve if you have a certain piece of knowledge, but hugely difficult if you don’t.

One example is RSA, a widely used public-key cryptography algorithm based on the factorization problem. The RSA algorithm begins by selecting two prime numbers at random and multiplying them to get a third number. This third number becomes part of the public key used to encrypt data. Decrypting those data, however, requires the private key, which derives from the prime factors themselves. But no efficient classical algorithm for calculating these prime factors has ever been found, so if the number to be factored is sufficiently large – the current RSA standard is 617 digits long – even the fastest computing clusters cannot break the encryption.

Quantum computers are different. In 1994 the mathematician Peter Shor devised an algorithm that allows quantum computers to factor large numbers much more efficiently. Hensinger estimates that his first-generation, football-pitch-sized machine could factor a 617-digit number in 110 days, and potentially as little as 10 days if the error rate of each quantum operation could be reduced. Other common public-key systems, such as those based on Diffie-Hellman or elliptic-curve cryptography, are similarly vulnerable. “[The Internet] is secure if you assume that these maths problems are hard,” explains Henry Semenenko, a final-year PhD student at the University of Bristol, UK. “With a quantum computer, they are no longer hard.”

There is one crucial difference between the quantum Y2K moment and its classical cousin. Whereas the original bug was well-localized in time, the quantum version is, appropriately, fuzzier. “It’s kind of annoying, because with Y2K it was pretty clear-cut that on 31 December 1999, you were going to have a problem in a couple of seconds,” Erven says. “This one is sort of nebulously spread over a number of years.”In Semenenko’s words, the impending failure of widely used encryption methods constitutes a “quantum Y2K moment” – a latter-day counterpart to the bug that, 20 years ago, left experts scrambling to fix systems and computer code that could not handle dates beyond the year 1999. The potential for disruption is certainly analogous. Asked for examples of organizations that would suffer if public-key cryptography suddenly became insecure, Chris Erven – Semenenko’s PhD supervisor at Bristol’s Quantum Information Institute – rattles off a list that includes banks, telecommunications firms and healthcare providers, as well as power plants, shipping facilities and other critical infrastructure systems. Rupert Ursin, a physicist at the Austrian Academy of Sciences in Vienna, concurs. “The usual suspects, ranging from health to governments and the military, are only the tips of the iceberg,” he warns.

One source of uncertainty is that nobody knows for sure when a cryptographically useful quantum computer will be built. Michele Mosca, an influential scientist and co-founder of the Institute of Quantum Computing at the University of Waterloo, Canada, has suggested that there is a 50% chance of it happening by 2031. Others in the field are bolder. John Prisco, chief executive of the US-based cybersecurity start-up QuantumXchange, thinks it could take as little as three years. Predictions of between five and 10 years are not uncommon.

A second complicating factor is that for some types of data, the quantum Y2K moment has already arrived. “The central argument has always been that if there’s a quantum computer, it could potentially decode these cryptographic keys,” says Rob Thew, a physicist at the University of Geneva, Switzerland. “But what we see now is that you can just store all those data, and in the future, when you’ve got your quantum computer, you can decrypt.” Hence, any encrypted information that needs to remain secure for more than (say) 10 years is already at risk, even though the computers that could decrypt it don’t yet exist.

Examples of such information abound. Medical records are meant to be kept confidential throughout patients’ lifetimes, and sometimes for 10 or 20 years after their deaths. Companies and, especially, governments have secrets they would like to protect indefinitely. You don’t have to be paranoid to think of further examples, and Prisco – whose own personal information was stolen in 2015 as part of a massive data breach at the US government’s Office of Personnel Management – believes that well-funded, determined eavesdroppers are harvesting some of these data already.

…with a classical solution?

The good news is that a massive information security crisis is far from inevitable. “The reason there was no Y2K disaster is because people put money into it and worked on it and fixed the problem,” notes Kenny Paterson, an information security expert at Royal Holloway, University of London, UK. “I think much the same is true here.”

Broadly speaking, approaches to the quantum Y2K problem fall into two categories. The more straightforward – advocated by Paterson and other cryptographers – would be to replace vulnerable cryptographic methods like RSA with alternatives that will resist attacks by eavesdroppers with quantum computers. To that end, in 2016 the US National Institute of Standards and Technology (NIST), launched a competition for a new “post-quantum” encryption standard. The first round of this competition closed in 2017, having garnered 69 submissions. Paterson (an author on two of the submissions) says that each proposed system has strengths and weaknesses. Some post-quantum methods, for example, use relatively short strings of data in their public keys, but require a lot of effort to compute. Others are computationally cheap at the expense of longer keys. The process of testing algorithms and weighing up their merits is expected to take another 5–7 years, but the outcome, Paterson says, will be “a portfolio of algorithms in which we have some reasonable level of confidence”.

For some applications, though, “reasonable confidence” may not be good enough. “Post-quantum cryptography tries to find [problems] that are difficult even for a quantum computer,” says Stephanie Wehner, a physicist at Delft University of Technology in the Netherlands. “But it is actually not proven that any of them really give quantum security.” Tim Spiller, a physicist at the University of York who also directs the UK’s Quantum Communications Hub, says that because we don’t have a large-scale quantum computer yet, it is hard to know what such a machine might be able to do, or what algorithms it might run. Erven notes that some algorithms once thought to be “safe” later turned out to have flaws. If you want your data transmissions to stay secure at a deep, fundamental level, he argues, you may need encryption that incorporates sophisticated physics as well as sophisticated mathematics.

Physics-based security

That’s where the second approach comes in. Like all the other physicists interviewed for this article, Erven, Spiller and Wehner are experts in quantum cryptography. In this type of cryptography, keys are not transmitted in the form of binary 0s and 1s. Instead, the keys in quantum cryptography consist of strings of photons in randomly generated quantum states. When a sender (Alice) transmits these photons to a receiver (Bob), anyone who tries to eavesdrop on their conversation will have to measure some property of the photons. But the principles of quantum physics state that if they do, they will change the photons in a way that alerts Alice and Bob to the attempted hack and renders the key useless. In principle, then, quantum key distribution (QKD) is secure against any type of eavesdropper, even one equipped with a powerful quantum computer and an infinite amount of patience. As Wehner puts it, “the eavesdropper can happily compute onwards until the heat death of the universe and nevertheless not learn the message.”

But despite its theoretical allure, QKD does have significant practical limitations. Chief among these is that quantum keys don’t travel well. As the distance between Alice and Bob increases, losses in the optical fibres connecting them reduce the rate at which they can exchange keys. After a couple of hundred kilometres, the number of usable photons becomes unmanageably small. So, to keep things running smoothly, QKD systems typically use links measuring between 100 and 150 km – long enough to build direct connections between users within metropolitan areas, or to link a company’s big-city headquarters to a data centre in the suburbs.

To send keys over greater distances, though, these short links must be daisy-chained together via a system of “trusted nodes”. At each node, the quantum signal is measured and then re-transmitted. Several countries have developed such chains already; Quantum Xchange is currently rolling out a network of trusted nodes in the US north-east corridor (see image), while the UK is constructing a link between Bristol and Cambridge. In Paterson’s view, however, trusted nodes are an eavesdropper’s dream. “The reason we’re using cryptography in the first place is that we don’t trust the intermediate nodes on the network,” he observes. “People often talk about, ‘Oh, but the Chinese have built a 1000 km QKD network from Shanghai to Beijing’. Great! But it has these so-called ‘trusted nodes’ along the way. People who are using this network have to trust the Chinese government not to eavesdrop on their communication at these intermediate points. Well, good luck with that.”The first phase of Quantum Xchange’s planned QKD link uses a system of so-called “trusted nodes” to connect the island of lower Manhattan in New York City to New Jersey, over the Hudson River, where many financial institutions house their back-office functions. A planned second phase will extend the network up and down the US East Coast, to the cities of Boston and Washington, DC. (Image credit: Quantum Xchange)

Physicists are pursuing several strategies for improving QKD’s real-world security and extending its reach. Thanks to better detectors and photon sources, the maximum distance between QKD nodes keeps ticking upward; the latest record of 421 km was set in November 2018 by researchers at the University of Geneva, the US multinational Corning and a Swiss QKD firm, ID Quantique. Another strategy is to build “quantum repeaters” that perform the same function as a trusted node, but without turning the quantum signal into a classical one that an eavesdropper could read. Today’s quantum repeaters are laboratory devices at best, but Wehner, who co-ordinates a cross-European R&D effort called the Quantum Internet Alliance, thinks the technology could be ready for deployment in 10 years.

A third strategy is to distribute quantum keys via satellites rather than optical fibres. That wouldn’t address the cryptographers’ “trusted node” criticism, but it might make QKD possible in areas where it currently isn’t. Iain Monteath, a security innovation consultant at the telecommunications firm BT, notes that optical satellite technology has its own drawbacks. Daylight and cloud cover are, he says, “challenges”. However, he believes these problems can be overcome with good ground-station networks, and in some places there is little alternative. “Until someone lays a trans-Atlantic cable – other oceans are available — with quantum repeaters or trusted nodes every 150 km, it’s going to be hard work to do it any other way,” he says.

Joining forces

In the past, efforts to build a “quantum safe” Internet have foundered amid mutual distrust between quantum physicists and cryptographers. “The two communities didn’t know each other, they didn’t talk to each other, and that created some bad feelings,” says Grégoire Ribordy, co-founder and chief executive of ID Quantique. Some traces of that acrimony remain. Paterson denounces trusted nodes as “propaganda on the part of the physics community” and bemoans the “quantum factor” that makes QKD an easier sell than complex mathematical problems. But he is also collaborating with Erven, Spiller and others in the Quantum Communications Hub to understand how post-quantum cryptography and QKD could work together. “My job is to act as the recalcitrant voice of the classical cryptography community,” he says. “The people I’m criticizing are also my friends and they know that my job is to criticize what they’re doing.”

Spiller, for his part, is emollient about the merits of post-quantum cryptography. “I think the longer-term vision is that you’ll have secure communications in some combination of quantum-secure hardware and mathematical crypto, as long as it’s thought with good reason to be immune to attack by quantum algorithms,” he says. Wehner observes that, since QKD employs symmetric keys, rather than the public/private pairs used in RSA, post-quantum cryptography makes a better replacement for today’s public-key encryption systems. “I view these techniques as somewhat complementary,” she says. “They have different use cases and different levels of security and different situations where you might want to prefer one over the other.”

Security-conscious firms should investigate both options, Ribordy suggests. “The first question that each company should ask itself is, ‘Where am I at risk?’” he says. Organizations that process information with a lifetime of less than two years can probably afford to do nothing at all. Those holding information that needs to stay secure for 10 or 15 years may wish to make their current systems more “crypto-agile”, ready to accommodate a switch to post-quantum cryptographic methods or full-fledged QKD.

Making that transition won’t be easy. Since QKD requires changes to hardware, not just software, Paterson thinks it has “a much tougher hill to climb” than post-quantum cryptography. But even software-based solutions will require effort. As with the original Y2K bug, Ribordy says, “You understand the problem, but patching is difficult. If you run a fleet of thousands of ATMs that use old-type crypto, it’s not like you push a button and then there’s new software everywhere.”

In Monteath’s view, the “right” approach to the quantum Y2K problem also depends on the answer to a completely non-technical question: how paranoid are you about your data? “Parts of industries are saying, ‘Post-quantum crypto is fine, thank you very much; it looks like that will do the job,’” he says. “But there’s another side that’s saying, even if a quantum computer doesn’t come along, let’s have a look at some of the encryption schemes that have been shown to be flawed because they were written by a human being rather than sewn into the fabric of the universe. Which one would you trust?”

28/01/2019 from physicsworld.com