THE online message board is littered with enigmatic statements. 鈥淭he DME system does not reach the claimed level of security,鈥� says one. 鈥淲e 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鈥檚 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鈥檚 codes. If we find an algorithm that survives every attack, it will emerge as the 21st-century鈥檚 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 鈥渢rapdoor鈥�: a function that is easy to calculate, but extremely difficult 鈥� impossible, ideally 鈥� to reverse without a cryptographic 鈥渒ey鈥�.
鈥淭here鈥檚 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鈥檙e 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鈥檛, 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. 鈥淗aving a Volap眉k-English dictionary makes this task relatively easy,鈥� he says. 鈥淏ut 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鈥檚 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鈥檚 algorithm. But of the Institute for Quantum Computing in Waterloo, Canada, has estimated the odds. He reckons there鈥檚 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 鈥渕ust act now鈥�.
鈥淭he 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鈥檛 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鈥檛 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. 鈥淚f you know how it was constructed, you can remove the errors. But someone who doesn鈥檛 have that secret key can鈥檛 decrypt the message,鈥� says , a mathematician in NIST鈥檚 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. 鈥淚t turns out that it鈥檚 really quick to evaluate a quadratic function if you stick in numbers for the variables,鈥� says Moody. 鈥淗owever, if someone gives you the answer but doesn鈥檛 tell you the secret input, it鈥檚 hard to work backwards and figure out what the input was.鈥� That鈥檚 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鈥檛 tricky enough already, it has to be implemented in ways that don鈥檛 inadvertently introduce weaknesses 鈥� bugs that can render the algorithm vulnerable even to classical computers. 鈥淨uantum-proof is not the only measure: the classical security is also extremely important,鈥� says , a project leader in NIST鈥檚 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 鈥渃urious 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. 鈥淭hreeBears 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鈥檛 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. 鈥淭he 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. 鈥淏ut 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鈥檚 unclear which will perform best. 鈥淭his version might have different security, for better or worse,鈥� he says.
It won鈥檛 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鈥檛 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鈥檚 no guarantee that any of them will be truly quantum-proof. Ultimately, there will always be an element of doubt. 鈥淲e don鈥檛 know there won鈥檛 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鈥檚 algorithm emerging two decades later. 鈥淭here is never 100 per cent security.鈥�
NIST鈥檚 experts have a positive outlook, nonetheless. Chen is confident that they have the tools needed to create a secure future. 鈥淎ssessing 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. 鈥淲e really do want to get something out of this,鈥� he says, 鈥渂ecause we need to have replacements ready.鈥�
Quantum vs quantum
We already have a brand of cryptography that鈥檚 safe from the threat of quantum computers 鈥� it鈥檚 called quantum cryptography. Alas, there鈥檚 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鈥檚 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鈥檚 encrypted secrets and wait.
That鈥檚 a headache for governments. A quantum computer able to break today鈥檚 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 鈥淪.O.S. (Save Our Secrets)鈥�
