THE online message board is littered with enigmatic statements. “The DME system does not reach the claimed level of security,” says one. “We looked at the EdonK KEM and found an attack,” declares another.
If that sounds vaguely ominous, think again – it is even worse than it seems. The message board is a blow-by-blow account of an ongoing battle between humans and machines. At stake is nothing less than the cybersecurity that underpins modern society. If we lose, then everything from our WhatsApp chats and medical records to government secrets will be wide open to attack. Nothing will be safe.
Advertisement
The danger lies in the fact that, before long, someone will build a quantum computer that can crack our most powerful encryption methods – the mathematical tricks that turn data into unreadable secret code to hide it from prying eyes. The only way to defend ourselves is to build codes that even the most powerful machines conceivable cannot crack. Which is exactly why some of the world’s smartest mathematicians have been attempting to invent a whole new class of encryption algorithms.
Having submitted their best designs to the post-quantum cryptography group at the National Institute of Standards and Technology (NIST) in Maryland, scores of teams are now engaged in a global race to identify the most secure by trying everything they can think of to crack each other’s codes. If we find an algorithm that survives every attack, it will emerge as the 21st-century’s gold-standard digital padlock. But for all the competitors, an almost existential question lingers at the backs of their minds: is it even possible to outsmart a quantum computer?
Encryption is as old as civilisation. Although the techniques have moved on over the centuries, the core idea remains unchanged: convert plain text into some sort of code that only you and your confidantes can decipher. These days, the most widely-used digital encryption schemes, or cryptosystems, are based on a mathematical “trapdoor”: a function that is easy to calculate, but extremely difficult – impossible, ideally – to reverse without a cryptographic “key”.
“There’s a 50:50 chance all our secrets will be exposed before we can secure them”
Take the RSA cryptosystem, for example. We rely on it to protect vast reams of data, from credit card details online to state secrets, and it is based on a trapdoor known as factoring. This involves a large number that is made public and two secret prime numbers that multiply together to produce it. Anyone can make a secret message using the public number, but only those who know the two smaller numbers can then read it. If you’re not in the know, the only way to break this encryption is to pick a pair of numbers, multiply them together and see if the result matches your target. If it doesn’t, you pick another pair and try again – and again, and again. The sheer laboriousness of the process is what makes the RSA cryptosystem secure.
The exercise is akin to translating a text from an obscure language such as Volapük – devised by a German cleric in the 19th century – to English, says , a computer scientist at the Centre for Quantum Technologies at the National University of Singapore and an entrant to the NIST competition. “Having a Volapük-English dictionary makes this task relatively easy,” he says. “But if we only have an English-Volapük dictionary, even though the information is in there somewhere, the translation will take a lot more time.”
Ahead of the curve
Elliptic curve codes, another trapdoor scheme currently in use, are a little more abstract. Here you start with an equation that will create a particular kind of curve when plotted on a graph. The encryption capacity comes from having a series of simple operations that describe movement between points on the curve. If you know only the starting point and the final point, it is extremely difficult to work out what moves happened in between.
Cryptosystems based on factorisation and elliptic curves do the job – for now. The problem will come when we build computers that use the strange laws of quantum physics to bring an exponential leap in processing power. The first proper quantum computer is not yet up and running, but progress in recent years has been swift enough to persuade against complacency. And already there is a technique, known as Shor’s algorithm after its creator, the MIT mathematician Peter Shor, that would allow quantum computers to unleash their power on factorisation problems.
No one knows how long it will be before we see a computer with enough qubits, or quantum bits, to make use of Shor’s algorithm. But of the Institute for Quantum Computing in Waterloo, Canada, has estimated the odds. He reckons there’s a 1 in 6 chance that a quantum computer will be able to break RSA and elliptic curve cryptosystems by 2027, and a 1 in 2 chance this will happen by 2031. If he is right, there is at least a 50:50 chance that all our secrets will be exposed before the new standard is established (see “The waiting game“). All of this has moved the US National Security Agency to admit that it “must act now”.
“The rivals are meeting to pick over the carnage from their attempts at sabotage”
But how? How can anyone expect to design a quantum-computer-proof cryptosystem if we don’t yet have a fully functional quantum computer to put it through its paces? Well, we already have a good idea of what these machines will be capable of, so the solution is simple enough to state: you build an algorithm based on mathematics so fiendishly complicated that even a top-notch quantum computer couldn’t break it.
Broadly speaking, that will involve one of three strategies. The first, called code-based cryptography, is derived from the tricks that prevent errors creeping into our digital data. All computer systems contain a certain amount of noise, from heat or stray electrical signals, and once in a while this can flip a binary digit from 1 to 0 or vice versa. Error-correcting codes are designed to spot such anomalous flips, and reverse them. Cryptosystems based on such codes, on the other hand, deliberately put errors in – preferably enough to obscure the message. “If you know how it was constructed, you can remove the errors. But someone who doesn’t have that secret key can’t decrypt the message,” says , a mathematician in NIST’s post-quantum cryptography group.
There are also lattice-based cryptosystems, based on navigating through a multidimensional arrangement of points. The security comes from something akin to knowing the shortest route between A and B.
Then there is the multivariate approach, which entrusts its secrets to some of the basics of algebra. It uses equations called quadratic functions, but with lots of different variables. “It turns out that it’s really quick to evaluate a quadratic function if you stick in numbers for the variables,” says Moody. “However, if someone gives you the answer but doesn’t tell you the secret input, it’s hard to work backwards and figure out what the input was.” That’s why the HFEv-signature protocol, which is a multivariate-based cryptosystem, has been unbreakable since its creation in 1996.
We already know – as far as is possible – that these schemes potentially offer quantum-proof encryption because there are only a handful of ways in which a quantum computer can attack the underlying maths, and none of these methods can crack these new schemes. The trouble is that building a working cryptosystem from these mathematical tricks is maddeningly difficult.
As if the maths isn’t tricky enough already, it has to be implemented in ways that don’t inadvertently introduce weaknesses – bugs that can render the algorithm vulnerable even to classical computers. “Quantum-proof is not the only measure: the classical security is also extremely important,” says , a project leader in NIST’s cryptographic technology group.
Mike Hamburg, a senior security engineer at Rambus in Sunnyvale, California, knows how hard it is to tick all the boxes. He has entered an algorithm called into the NIST competition, but his journey into post-quantum cryptography began three years ago when he created his own elliptic curve algorithm. Its security derived from incorporating a prime number that has what he terms a “curious relationship” to the so-called golden ratio, an irrational number that crops up all over the natural world. In cryptography, it is useful because numbers that interact with it take on values that are difficult to compute. Hence, he called the algorithm Goldilocks.
His new algorithm, on the other hand, is a lattice-based system. “ThreeBears uses a much bigger prime number with the same property, and it uses some of Goldilocks’ code for the arithmetic,” says Hamburg.
Among the other entries are algorithms with more macho names such as Titanium, Locker, Falcon and Lizard. In the end, though, the name doesn’t matter. It is how the algorithms perform that will determine whether the months, years or, in some cases, decades of work were worth it.
at the University of Limoges in France, for instance, has been working on post-quantum cryptography for 15 years. His name is on eight of the 82 NIST submissions. Not that he is complacent: he knows that, despite having so much skin in the game, his efforts may come to nothing as the entries are put through their paces. “The fact that the problems have been there for a long time brings confidence,” says Gaborit, because no one has yet found a way for any computer to crack them. “But it is always possible that someone finds a new attack.”
Hamburg, too, is wary of the unknowns that could scuttle ThreeBears. It is based on longer-established algorithms, all of which have also been submitted to NIST, but it’s unclear which will perform best. “This version might have different security, for better or worse,” he says.
It won’t be long before he finds out. This April, all the researchers who have entered an algorithm will , Florida, to pick over the carnage from their attempts at sabotage. The good news is that many of the flaws exposed so far aren’t fatal. Relatively small tweaks can rehabilitate injured algorithms. So the meeting will be geared towards pointing out weaknesses and suggesting fixes.
Even if the algorithms emerge unscathed, however, there’s no guarantee that any of them will be truly quantum-proof. Ultimately, there will always be an element of doubt. “We don’t know there won’t be a new quantum algorithm that works against quantum-resistant cryptography,” Gaborit concedes. When we implemented RSA in 1976, he points out, no one could have foreseen Shor’s algorithm emerging two decades later. “There is never 100 per cent security.”
NIST’s experts have a positive outlook, nonetheless. Chen is confident that they have the tools needed to create a secure future. “Assessing quantum-proof strength has been a very active research area in recent years,” she says. It is now time to put that research to work.
To that end, NIST will select the strongest candidates and encourage everyone involved to sabotage them again. Moody reckons several of them look like they will survive scrutiny – although that might be wishful thinking arising from the widespread eagerness to get to grips with the problem. “We really do want to get something out of this,” he says, “because we need to have replacements ready.”
Quantum vs quantum
We already have a brand of cryptography that’s safe from the threat of quantum computers – it’s called quantum cryptography. Alas, there’s a catch.
This method ensures that no one eavesdrops on the process of exchanging a cryptographic key, the string of digital bits used to decode an encrypted message. The digits of the key are encoded in pairs of particles called photons. These photons are then entangled, establishing a quantum link between them. This means that any eavesdropper will disturb the entanglement, leaving a clear trace of their snooping. The idea has already been used to secure communications during a 2007 election in Switzerland, and a number of commercial systems are available. Sorted then?
Alas, practical implementations of quantum cryptography are still difficult, and often leaky. at the University of Waterloo, Canada, has demonstrated several hacks exploiting weaknesses that emerge when the theory is rolled out in the real world. Inefficient photon sources and detectors, or imperfections in optical fibres, mean that there are ways to siphon off some of the key’s digits without being detected.
Researchers are working on fixing these flaws, but widespread use of quantum cryptography is still a long way off, which is why cryptographers are racing to make quantum-proof encryption (see main story).
The waiting game
Even if we got new quantum-computer-proof cryptography systems tomorrow, it is likely that many secrets are already compromised.
It can take up to 20 years to implement a new cryptosystem. So if a computer with the vastly inflated processing power required to crack current codes arrives in the next 20 years, no data encrypted with the old system can be considered truly confidential. All someone needs to do is store today’s encrypted secrets and wait.
That’s a headache for governments. A quantum computer able to break today’s encryptions is likely to appear within the 30 years for which most states like to keep their secrets. And businesses are at risk too: many try to keep documents and records behind a veil for as long as possible.
According to a report issued by the European Union-funded research project PQCrypto, companies should be aware that information encrypted for safekeeping with our current best methods will be as easy to expose as those encrypted by the German Enigma code used in the second world war are today.
This article appeared in print under the headline “S.O.S. (Save Our Secrets)”
