In research labs around the world, a race is playing out between engineers building a completely new kind of computer and the cryptographers creating encryption tools to protect us from the superior computing power. Here’s why businesses should start thinking about post-quantum cryptography now, and the steps they can take to keep safe.
Fully scaled quantum computers, which will rip up the computing rulebook, are still some way off: some experts say it will be another 10 years before we see at-scale, error-free quantum computers, while more conservative estimates put this figure closer to 30.
But recent advances, such as Google’s claim to quantum supremacy – when a quantum computer solves a problem that a classical computer is unable to – have underscored how their radically different approach can upend computing.
Quantum computing (QC) is usually explained by saying that where a normal computer operates using bits of information, a quantum computer uses quantum bits or “qubits”. A normal bit is 1 or 0, on or off: a qubit is much more complicated. When it is measured it will be either 1 or 0; before that, it exists in a quantum superposition of those two states. The quantum superposition is usually described using “complex numbers”, mathematics based on the so-called “imaginary unit”, the square root of minus one.
Another way of visualising this is that normal bits are like coins lying on a table. They are either heads or tails up: they can be flipped over. A qubit, however, is like a coin spinning in the air. It can interact with other spinning coins, affecting how they spin, but none of them are heads or tails up until the quantum operations are complete.
Theoreticians can describe what qubits will do in a network of quantum logic gates, even if they don’t have any actual machinery capable of carrying out the process. As a result, algorithms can be, and have been, developed for QC machinery even before there was any – rather in the way that Ada Lovelace famously wrote some of the first conventional computer programs for Charles Babbage’s proposed 19th-century mechanical computer, the Analytical Engine, even though it was never actually built.
Thus we know many of the things that QC could achieve. Its effects, when it becomes available at appropriate scale, will be enormous. Quantum computers will find a use anywhere there is a large and complicated problem to be solved. That could be anything from predicting the financial markets, to improving weather forecasts, to cracking encryption systems.
The turbo-charged computing power of quantum computers is expected to make mincemeat of many of our current encryption tools, which we depend on every day to keep our messages private and know that the machines we communicate with are legitimate.
To understand how quantum computers will be able to crack today’s encryption, it’s worth considering how cryptography works today.
There are two commonly used types of cryptography: symmetric and asymmetric. It is asymmetric cryptography that is at risk from quantum computers. Its algorithms consist of two mathematically linked keys – a private and a public key. The public key encrypts, while the private key is known only by the party decrypting the information.
Asymmetric cryptography is the most used in day-to-day communication, with many types of encryption falling under this umbrella. Perhaps the most widely used is RSA, which is used to secure web browsers, chat applications, VPNs and more. These algorithms are based on a complex maths problem known as prime factorisation. The longer the key – the more bits – the harder it is to replicate the maths and so break the encryption.
Current computers do not have the computing power to break the RSA algorithm. But we know that it will be possible with quantum computers thanks to Shor’s algorithm, devised by Peter Shor in 1994.
And by factoring these numbers on a quantum computer, an attacker will be able to reverse engineer, or factor, the private key.
“It’s not breaking the encryption. It is breaking the keys,” says Kevin Bocek, vice president of security strategy & threat intelligence at Venafi, a cybersecurity firm protecting machine identities.
Post-quantum cryptography: It’s not all about the qubits
The rough estimate is that two qubits per bit of the key are needed to break the encryption. So for RSA 2048, a quantum computer would need 4,096 qubits. But it’s not quite that simple, says IBM cryptographer Vadim Lyubashevsky, who has been working on the post-quantum cryptography problem since 2002.
“Just measuring qubits is somewhat deceptive,” he says. That’s because these estimates refer to a logical qubit that is free from the errors that today’s fledgling quantum computers are very much prone to.
He continues: “Unfortunately when you’re building a quantum computer, things are very unstable. So in order to create one of these logical qubits, we may need, say, 1,000 actual physical qubits.”
IBM’s most powerful quantum computer currently boasts 65 qubits, while Google’s has 72. All of these are far from the perfect, error-free logical qubit.
But computer scientists are working to improve these numbers. And when a fully functioning quantum computer with lots of qubits arrives on the scene, the security implications could be severe. A quantum computer could easily imitate the identity of another machine by replicating digital certificates such as SSL/TLS, which are used to tell us a computer is genuine.
“The risk is of a quantum computer being able to recreate these identities, these keys, essentially, out of thin air,” says Bocek. “And one machine now could look like another machine, one machine could break our privacy. So now we could have a whole bunch of masquerading, marauding machines and so our private communications, whether we’re a business or us personally – becomes known to everybody.”
We’ve already seen the dangers of expired digital certificates. In 2017, hackers managed to steal 145 million customer records from Equifax undetected in part because of an expired digital certificate.
But in a post-quantum world, it won’t be your average cybercriminal carrying out quantum attacks.
Despite the potentially serious implications of this looming threat, quantum computers will only be available to a small number of people. That’s because they are incredibly difficult to build, requiring very specific parts, and will need to be kept in controlled lab environments. And they’ll be expensive.
This means that they will remain firmly under the control of nation states, a small handful of large commercial entities and academic organisations.
Or, as Bocek puts it: “Terrorists can’t conjure up a quantum computer with pieces ordered on eBay”.
While they will likely remain firmly in the hands of powerful nation states, there is no guarantee that they won’t ever be used as part of a cyber-arsenal to further strategic goals.
“So whether that is eavesdropping, spying on a certain set of adversaries, or whether a nation state wanted to convey this as a weapon to destroy or create havoc in commerce – that’s the way that these will be used,” says Bocek.
“Another type of attack may be to create havoc and uncertainty. A nation state might look to create distrust maybe in the banking or financial systems as retribution. And so, be able to masquerade or change certain trades or banking operations.”
In extreme cases, they could hypothetically be used to disrupt banking operations an trigger a recession, adds Bocek.
Professor Michele Mosca, co-founder and deputy director of the Institute for Quantum Computing at the University of Waterloo, says that if adequate defences aren’t developed in time, then “critical IT infrastructures will fail with no quick fix. Unlike today’s hacks, where we detect and remediate as quickly as we can, in this scenario the new tools needed to remediate haven’t yet been developed”.
And if they are developed but not robustly deployed in time in the real-world, “migration will be managed as a crisis,” says Mosca.
“This will be disruptive, expensive and worst of all lead to very bad designs and implementations. Bad designs and implementations can be hacked without a quantum computer.”
Defending against quantum attacks
In 2017, Mosca estimated that there’s a one in six chance of quantum computers being able to break RSA 2048 by 2027. So, what can be done to defend against quantum attacks?
Some algorithms cannot be cracked by Shor’s algorithm, such as SHA-256, which is used in hashing for securely storing passwords, or AES, which is used to encrypt files and hard disks.
But these cannot be used for machine identities or to encrypt web communications. Instead, we will require new encryption tools that are based on different mathematical principles to defend against a quantum attack.
These will be bigger and larger keys, ones that are immune to quantum attacks. So how close are we to having these quantum-safe algorithms?
“These fundamental low-level tools already exist,” says Mosca. “But they aren’t deployed widely in real-world systems.”
Tech heavyweights such as Google, IBM and Microsoft are among the players developing these. Other companies, such as Thales, have announced plans to develop quantum-safe algorithms.
As GlobalData thematic analysts note in a quantum computing report: “Most observers believe that in the time it will take to develop a quantum computer sufficiently powerful to run Shor’s algorithm at a scale advanced enough to threaten encryption, the cybersecurity industry will develop quantum-resistant encryption.”
Lyubashevsky says that post-quantum cryptography is already here and we can be “reasonably certain of their security”. At IBM he helped develop three sets of post-quantum cryptography algorithms: Crystals Dilithium, Crystals Kyber and Falcon.
“It’s just a matter of being standardised,” he says. “And they’re already being used in some parts. Anyone can use them.”
But Mosca says that while – by some interpretations – we have these algorithms today, they haven’t been scrutinised enough yet.
“At the other end, one might argue we’re at least a decade away from robust, widescale, standardised deployment of quantum-safe crypto in critical real-world systems,” he says.
Leading the quantum resistance
The beacon for all these efforts and the body deciding the next encryption standards is the National Institute of Standards and Technology (NIST). The US government organisation is running a ‘competition’ to determine a handful of quantum-safe algorithms that will become the new standards.
NIST is experienced in managing encryption standards, having created the standards for all the previous encryptions and replacing them when they are cracked, all by a deadline.
Despite learning from the previous changes, it’s “not easy”, says Dustin Moody, the mathematician overseeing NIST’s post-quantum cryptography standards competition.
“It’s very, very slow, and you never completely get rid of the older [cryptography standards],” he says of the process of introducing new standards, adding that this time around it’s “going to be somewhat of a more painful transition”.
However, Moody is confident that the standards will be in place before large scale quantum computers start to threaten cryptography.
In June 2020, NIST narrowed the pool of potential encryption tools that will hold up in a post-quantum world down to a handful of cryptographic algorithms, with IBM’s post-quantum cryptography making the cut.
The finalists have been selected on two criteria: security and performance. The process essentially involves researchers trying to break the post-quantum algorithms and making corrections where necessary.
Given that quantum computers are still in the nascent stage, researchers estimate “as best they can” how many operations a quantum computer would need to do to break it, says Moody.
These algorithms will also need to be able to withstand current decryption techniques and need to work in big computers, smartphones and smaller, IoT devices.
“We want quantum-resistant algorithms that can perform this sort of lightweight cryptography,” Moody said in a NIST blog post.
Moody says that the aim is to narrow the quantum-safe tools down to a small handful to avoid confusion. NIST is aiming to publish these finalised standards in 2022, alongside guidance that explains the pros and cons of each type of quantum-safe encryption.
Once the standards are out, it will be down to industry to adopt them, knowing that the standards have the backing of the US government.
“These fundamental tools, even if standardised, need to be deployed in real-world systems,” says Mosca. “This is not easy either, but some companies are taking serious steps.”
Google, for example, has tested some post-quantum cryptography in Chrome, while Amazon, Microsoft, IBM and Cisco are among others that have been exploring it.
But a lot more needs to be done, says Mosca, and there is “broader complacency when it comes to cyber risk” among organisations.
“There is still a long hard road ahead, so we cannot be complacent,” he says, adding that researchers will need to continue studying what “novel quantum attacks” may be used to compromise the proposed quantum-safe alternatives.
What can businesses do to prepare for post-quantum cryptography?
So what, should businesses be doing right now when it comes to post-quantum cryptography?
Moody says that one of the main things is to “be aware of the threat” and know that a transition is on the horizon.
“We recommend that they do a kind of a quantum risk analysis, where they look at the cryptography that they’re using right now,” he says. “See what’s vulnerable and what isn’t, what public-key cryptography they’re using; what their vendors are using; what products they’re buying.”
Bocek agrees that organisations should be carrying out an audit of their current encryption keys, adding that automation is one way to swap out the keys at scale.
And businesses don’t necessarily have to wait for the standards, says Lyubashevsky. For example, a bank wanting to ensure its one-to-one transaction with its customers are quantum-safe today, it could put one of the algorithms on its mainframe to protect itself.
That’s exactly what IBM is doing now with some of its customers, carrying out assessments to see if it’s the right time to start migrating.
“There are right ways and wrong ways to incorporate these algorithms,” adds Lyubashevsky.
He says the wrong approach is to take the post-quantum cryptography and simply hard code it into a system and be done with it.
“The better way is to do it in a very agile, modular way; to say, look, here’s the place where our algorithm will go, we kind of know approximately how big the keys will be, we know how big the communication is going to be. And so then if you start migrating towards that type of architecture, and that type of security, it should be very easy to take whatever algorithms NIST will give, which will be some very small variation of what already has been submitted.”
All of these approaches lead to a position known as being ‘quantum agile’, where it’s easy to swap out old crypto for new post-quantum crypto.
But while quantum-safe cryptography is essentially already here and standardisation isn’t far off, it’s not time for businesses to relax.
Record now, break later
For some time now, security experts have been worried about a concept known as ‘record now, break later’. This means that anything currently encrypted with public key cryptography could be copied down now, stored, and decrypted when quantum computers are powerful enough.
“We need to have these standards in place as soon as possible because somebody could simply take your data right now and copy it down,” explains Moody. “And it’s encrypted using current public key cryptography. And then if a quantum computer comes out in 10 years, they could go back and decrypt your data.”
“This is definitely the major worry right now, that somebody is harvesting data,” agrees Lyubashevsky.
Of course, there’s plenty of data that will be useless in ten or 15 years’ time, or of no real security value. A message containing the family secret recipe to the perfect quiche is unlikely to draw the attention of a nation state, but for high-value data – be it medical patents or sensitive government cables – the hypothetical risk is too great to ignore.
And products such as satellites and trains with lifetime cycles of ten to 30 years that cannot be easily replaced once deployed, should be considering quantum-safe encryption.
That’s why some organisations are already looking to implement quantum-safe encryption on their most valuable data now.
Mosca says that quantum key distribution (QKD) is one way to future proof against future quantum attacks. QKD “provides key agreement through a non-confidential but authentic channel (including a quantum channel),” he says. “QKD cannot be mathematically cryptanalysed, so it’s resilient to ‘record now break later’ attacks.”
Although QKD is commercially available now, it cannot provide digital signatures like RSA, so it isn’t a silver bullet.
Above all, the main things for businesses to do now is be aware of the threat on the horizon, carry out an audit of their public encryption keys, keep an eye on NIST’s standards, and aim to become quantum agile.
What happens when the next cryptography standards are here? Will they be the last upgrade, or will another algorithm or technology come along and break these post-quantum algorithms?
Lyubashevsky says breaking post-quantum algorithms is unlikely. Instead, it’ll be that a faster, more efficient algorithm will come along and supersede the incoming generation of cryptography.
“There is no one hundred per cent guarantee in crypto.”
This is an updated version of an article that originally appeared in sister publication Verdict Encrypt in 2019.