What next in the world of post-quantum cryptography?
Recent claims to have achieved quantum supremacy have got the world talking even more about cryptography in a post-quantum age. But could this simply be hype? We take a look below.
Research in quantum computers is advancing quickly and researchers recently claimed to have reached quantum supremacy, in other words, the ability of quantum computers to perform a calculation out of reach of even the most powerful classical supercomputers.
However, any claims that quantum computers are close to cracking any practically used cryptosystems are highly exaggerated. Such powerful quantum computers are very likely several decades away, if indeed they will ever be built. Many significant technical advances are still required before a large-scale, practical quantum computer can be achieved, and some commentators even doubt whether such a scenario will ever be possible.
What we do know, however, is that large-scale cryptography-breaking quantum computers are highly unlikely to develop during the next decade. Yet, in spite of this, systems which need very long-term protection such as government systems with classified information or root certificates with very long lifetimes must nevertheless start preparing to replace today’s asymmetric algorithms.
Impact of quantum on asymmetric cryptography
In traditional cryptography, there are two forms of encryption: symmetric and asymmetric.
Most of today's computer systems and services such as digital identities, the Internet, cellular networks, and crypto currencies use a mixture of symmetric algorithms like AES and SHA-2 and asymmetric algorithms like RSA (Rivest-Shamir-Adleman) and elliptic curve cryptography.
The asymmetric parts of such systems would very likely be exposed to significant risk if we experience a breakthrough in quantum computing in the coming decades.
What is post-quantum cryptography?
In anticipation of such a quantum computing paradigm, cryptography is being developed and evolved by using so-called “quantum-safe” algorithms. They run on classical computers and are believed to withstand attacks from powerful quantum computers.
When we compare post-quantum cryptography with the currently used asymmetric algorithms, we find that post-quantum cryptography mostly have larger key and signature sizes and require more operations and memory. Still, they are very practical for everything except perhaps very constrained Internet of Things devices and radio.
Standardizing post-quantum cryptographic algorithms
The US National Institute of Standards and Technology (NIST) is currently standardizing stateless quantum-resistant signatures, public-key encryption, and key-establishment algorithms and is expected to release the first draft publications between 2022–2024. After this point, the new standardized algorithms will likely be added to security protocols like X.509, IKEv2, TLS and JOSE and deployed in various industries. The IETF crypto forum research group has finished standardizing two stateful hash-based signature algorithms, XMSS and LMS which are also expected to be standardized by NIST. XMSS and LMS are the only post-quantum cryptographic algorithms that could currently be considered for production systems e.g. for firmware updates.
The US government is currently using the Commercial National Security Algorithm Suite for protection of information up to ‘top secret’. They have already announced that they will begin a transition to post-quantum cryptographic algorithms following the completion of standardization in 2024.
Why should the industry be taking note of this decision? ‘Top secret’ information is often protected for 50 to 75 years, so the fact that the US government is not planning to finalize the transition to post-quantum cryptography until perhaps 2030 seems to indicate that they are quite certain that quantum computers capable of breaking P-384 and RSA-3072 will not be available for many decades.
Symmetric cryptography and quantum computers
When we turn our focus to symmetric cryptography as opposed to asymmetric cryptography, we see that the threat is even more exaggerated. In fact, even a quantum computer capable of breaking RSA-2048 would pose no practical threat to AES-128 whatsoever.
Grover’s algorithm applied to AES-128 requires a serial computation of roughly 265 AES evaluations that cannot be efficiently parallelized. As quantum computers are also very slow (operations per second), very expensive, and quantum states are hard to transfer from a malfunctioning quantum computer, it seems highly unlikely that even clusters of quantum computers will ever be a practical threat to symmetric algorithms. AES-128 and SHA-256 are both quantum resistant according to the evaluation criteria in the NIST PQC (post quantum cryptography) standardization project.
Other alternatives within quantum cryptography
In addition to post-quantum cryptography running on classical computers, researchers in quantum networking are looking at quantum key distribution (QKD), which would theoretically be a provably secure way to do unauthenticated key exchange.
QKD is however not useful for any other use cases such as encryption, integrity protection, or authentication where cryptography is used today as it requires new hardware and is also very expensive compared to software-based algorithms running on classical computers.
In a well-written white paper, the UK government is discouraging use of QKD stating that it seems to be introducing new potential avenues for attack, that the hardware dependency is not cost-efficient, that QKD’s limited scope makes it unsuitable for future challenges, and that post-quantum cryptography is a better alternative. QKD will likely remain a niche product until quantum networks are needed for non-security reasons.
Recent quantum supremacy claims
The calculation recently used to show quantum supremacy was not very interesting in itself and was contrived to show quantum supremacy. The claim was also criticized by competing researchers who claim that the corresponding classical calculation could be done over a million times faster. Quantum computers able to solve any practical problems more cost-effectively than classical computers are still years away.
The “quantum supremacy” computer consists of 54 physical qubits (quantum bit), which after quantum error correction corresponding to only a fraction of a single logical qubit. This is very far away from quantum computers able to break any cryptographic algorithm used in practice which would require several thousand logical qubits and hundreds of billions of quantum gates. Scaling up the number of qubits will not be easy, but some researchers believe that the number of qubits will follow a quantum equivalent of Moore’s law called Neven’s law. We will likely see undisputed claims of quantum supremacy in the coming years.
What can we expect next?
Since our earlier post in 2017 about post-quantum cryptography in mobile networks, the hype around quantum computers and the worries about their security impacts have been more nuanced, aligning with our previous analysis.
Recent reports from academia and industry now says that large-scale cryptography-breaking quantum computers are highly unlikely during the next decade. There has also been general agreement that quantum computers do not pose a large threat to symmetrical algorithms. Standardization organizations like IETF and 3GPP and various industries are now calmly awaiting the outcome of the NIST PQC standardization.
Quantum computers will likely be highly disruptive for certain industries, but probably not pose a practical threat to asymmetric cryptography for many decades and will likely never be a practical threat to symmetric cryptography. Companies that need to protect information or access for a very long time should start thinking about post-quantum cryptography. But as long as US government protects ‘top secret’ information with elliptic curve cryptography and RSA, they are very likely good enough for basically any other non-military use case.
Read our colleagues’ earlier blog series on quantum computing, beginning with an introduction to quantum computer technology.
Read our earlier technical overview to cryptography in an all encrypted world in the Ericsson Technology Review.
Visit our future technologies page to learn how tomorrow’s world is evolving.