The future of privacy online begins and ends with the demise of public key cryptography. Mathematical riddles shared between two nodes in a network, modern encryption techniques would take trillions of years for your everyday ‘classical’ computer to crack. Quantum computers, meanwhile, will make short shrift of these conundrums. Machines capable of harnessing the mysteries of quantum mechanics to achieve feats of computation vastly superior to its silicon-based antecedents, the announcement that a quantum computer had broken RSA, DES or AES would render vast swathes of the internet insecure overnight.
This moment is often referred to by cryptographers as ‘Q-Day,’ though when it’ll arrive is anyone’s guess. Some predict it’ll take as little as eight years before conventional cryptography will be broken by a quantum computer, while others insist we still have a few decades before any quantum advantage well and truly breaks the internet. According to mathematicians like Dustin Moody, however, we may not even know the precise moment when conventional encryption is cracked. “It could be that it’s happening behind the scenes and we don’t know it for a while,” says the mathematician and expert in all things quantum at the US National Institute for Standards and Technology (NIST.)
It’s the reason why Moody and his colleagues at NIST have been holding a competition since 2016 to source new standards for encryption algorithms that, in theory, should be able to withstand the codebreaking abilities of mature quantum computers. “We wanted to make sure we have standards ready as soon as possible, even though a quantum computer is still off in the future,” says Moody. After multiple rounds of testing, both inside the organisation and at the hands of external cryptographers, NIST announced its approval in July of four algorithms it believes are quantum-safe for the purposes of encryption and digital signatures, with another four placed ‘under consideration’.
Eventually, these post-quantum encryption algorithms will supplant their RSA and DES equivalents – a more elegant solution, experts like IBM’s Scott Crowder argue, than quantum key distribution (QKD), which harnesses the mysteries of quantum mechanics to physically secure communications but requires massive investment in new ground infrastructure and satellites. “From our perspective, it’s not necessary or sufficient to really make you secure against quantum computers,” says the firm’s vice-president for quantum adoption.
There’s only one problem: post-quantum encryption algorithms keep being broken by classical computers. This happened as late as this summer, when one of the algorithms under consideration by NIST was broken by two Belgian cryptographers in just a couple of hours using only a laptop. Moody is well aware of the consequences in taking a wrong turn on these standards, even though a quantum computer capable of breaking RSA is arguably decades away from being built. Even so, he says, the threat posed by ‘harvest now, decrypt later’ attacks, wherein encrypted data is trawled by hackers and stowed away until it can be cracked open by a quantum machine, is very real.
“Most data these days has a pretty good lifespan,” explains Skip Sanzeri, founder of quantum startup QuSecure. “Think of personal information: that can be 50 to 75 years, depending upon a lifetime. Healthcare information? Usually over 50 years. Banking information? 25 years. Military secrets? 75 years.” The integrity of all of those secrets, argues Sanzeri, is therefore threatened in the here and now – regardless of when a quantum computer gets round to decrypting it.
How to write post-quantum encryption algorithms
The emergence of the post-quantum threat signals the end of what was an effective solution to the problem of securing information online. Devised in the 1970s, modern encryption methods require pairs of classical computers to parse mathematical problems that can only be solved with helpful pre-existing clues, known as ‘keys’, which are only available to the machines.
In the case of RSA, that involves prime factorization, or the act of factorizing large-enough integers of a number into its component primes. If one computer in the communicating pair already has the primes ready, it takes them no time at all. This is known as the ‘private key,’ while the ‘public key’ is the product of the primes. Only once both are produced can the encrypted message be unlocked.
Absent these keys, a classical computer would spend years – 300 trillion of them, according to one estimate – trying to work out a single prime factorization problem. However, in 1994, a researcher named Peter Shor devised a new algorithm that demonstrated how a quantum computer might harness the superimposed quantum status of its component informational units – known, in short, as qubits – to crack encryption methods like RSA in next to no time at all. “It’s really just because of Shor’s algorithm that quantum computers are relevant,” says Moody.
All that remained, then, was to build the machine. In 1998, that work began with the creation of a 2-qubit quantum computer at Oxford University. The number of working qubits has edged slowly upward in the intervening decades, which has also served to increase anxiety among cryptographers looking for a form of encryption immune to quantum attack. Boiled down, says Crowder, this involved “trying to find a math problem that both classical computers and quantum computers suck at”.
The hardest puzzle to solve in this regard seems to be lattice-based cryptography. Devised in the 1980s, this method’s strength lies in how difficult it is to calculate the nearest point between one number and another in a lattice structure encompassing up to 500 separate spatial dimensions. Four of the quantum-safe algorithms NIST eventually chose to recommend for standardisation, in both encryption and digital signatures, were lattice-based. “They’re good, all-round performers,” says Moody. “They’re very efficient. Their key sizes are not too big. Their security has been well-studied.”
It’s been a long and painful process to get to those final four. Early examples of lattice-based encryption were difficult to parse for classical computers, even with access to the necessary public keys, leading cryptographers to simplify the algorithms and inadvertently compromise their security. It’s a pattern that’s persisted into the present day, with dozens of examples volunteered for NIST’s evaluation being compromised since 2016. “In the first round, there were probably 15 to 20 that got broken,” says Moody. “In the second round, there were seven. And even in the third round... Rainbow was broken, and then, more recently, SIKE was also broken.”
Additionally, without an actual quantum computer to hand, there’s no guarantee that the algorithms which survived NIST’s third round are truly quantum-safe. Until then, says Moody, we don’t really have a choice but to trust in the Darwinian process of winnowing out the weakest algorithms by open-sourcing their code and watching them get picked off, one by one, by the wider cryptographic community.
“This is how we gain confidence,” says Moody. “We put them out there for the expert to evaluate; we give them a number of years to look at them; and, if a lot of people look at it and over a number of years, nobody finds any weaknesses, we can start to gain confidence in them.”
Preparing businesses for post-quantum encryption
It remains uncertain how long Moody and the rest of the cryptographic community will have to scrutinise these post-quantum encryption algorithms. Sanzeri is among the corps of true believers in the quantum community who think it likely that a machine capable of cracking RSA encryption by the end of this decade. And by that point, he adds, their ability to compute variables in problems at the drop of a hat means that a spot of codebreaking will be the least of its accomplishments.
“That's why,” says Sanzeri, “they're going to be awesome for AI, genomics and protein folding, chemistry, material science, optimisation, logistics, aerospace design - things where you've got tons and tons and tons of variables.”
Others in the field are more sceptical. A study published earlier this year estimated that it would take 13 million qubits to crack 256-bit encryption in a day - or, if you were in more of a rush, 317 million in an hour. By comparison, one of the most advanced quantum processors in existence, IBM’s ‘Osprey’ processor, has just 433 qubits. Although there is a clear roadmap to increasing the computational power of a quantum computer by parallelizing these processors, these devices will require significant assistance from error-correction algorithms to run in a useful way, says one of the study’s authors, Dr Sebastian Weidt - a research field, he adds, which is extremely nascent.
Regardless of when a code-cracking quantum computer is actually built, though, Weidt is adamant that businesses should be preparing for the post-quantum future now. “You’d love to think that, because we’re shouting this message very loudly years in advance, that it’s [going to be] barely a footnote somewhere that this has happened,” he says. “But realistically, lots of people will get caught out.”
Some might have been already. Both the UK’s National Cyber Security Centre and the NSA have been highly vocal in recent years about the need to secure telecommunications networks from quantum attacks, while both Sanzeri and Moody claim to have heard furtive whispers from their own contacts in the intelligence community that HNDL attacks are probably already happening.
As such, several institutions have already begun preparing for the post-quantum future, led first and foremost by the US government. In May, the Biden administration ordered federal agencies to begin preparing plans to secure their networks using post-quantum encryption algorithms, in addition to directing NIST to establish a working group to prepare the private sector for the road that lies ahead. They’ll be working alongside a growing number of start-ups like QuSecure and various tech giants that offer their own post-quantum preparation services.
“Those big companies – the Google’s, Microsoft, IBM, Intel – they’re all very well aware of the quantum threat,” says Moody. “As soon as the standards come out, you’ll see them start using the algorithms in their products.”
Some multilaterals, like Mastercard, have started offering products utilising quantum cryptography as a way of signalling their security credentials. IBM, meanwhile, is liaising with a range of banks, telecoms providers and manufacturers to harden their networks against quantum attack. “If you look at it from Vodafone’s perspective, they are a player that has a lot of their own IT, but they rely on a whole mass of vendors in their supply chain,” says Crowder. For their systems to be truly secure, he adds, their vendors need to be hardened against quantum attacks as well. “It’s an ecosystem play.”
Crowder is under no illusions, however, that transitioning such systems will be easy. “We definitely had to upgrade SHA-1, SHA-2, SHA-3, over time,” he says. “But we’ve never, since the internet got launched, really, had to do a transformation of this nature.”
Meanwhile, the world awaits NIST’s final judgement about post-quantum encryption standards. For his part, Moody expects those to be published next year. But, he adds, businesses shouldn’t wait to ready themselves for what lies ahead. “Learn all you can,” says Moody. “Talk to us if you have questions – and make sure your organisation is prepared for this quantum threat.”
Read more: IBM unveils quantum supercomputer which could reach 4,000 qubits by 2025
