Is it post quantum time yet?

TL;DR

If you develop an application that will still be used after 2030 or if the data you manage will still be sensitive past that date, it's time to integrate post-quantum cryptography.

For most symmetric usage, classic state of the art algorithms are already resistant to attacks by a quantum computer. Make sure to use 256 bit keys for encryption (AES-256, CHACHA20) and hash function with 256 bits of output (SHA-256, BLAKE2).

For asymmetric usages, a few recommendations must be followed:

• Use a hybrid mechanism that rely on both a regular and a post quantum mechanism.
• Choose your post quantum mechanism among the most tried and tested ones. Round 3 post quantum NIST candidates are the logical choices.
• Hash-based signature mechanisms are interesting if you can keep up with their drawbacks (limited number of signatures, big signature size).

In any case, make sure to rely on a good quality cryptographic library that implements those mechanisms. The Post Quantum Safe project provides such a piece of software, but other providers, like BouncyCastle, also implement a few algorithms.

State of quantum computing

To start, it's probably important to remind that quantum computers are very different from standard ones. And, while the fact that they might be a lot more powerful than your laptop is probably true, it is also probably right that you will never play Call of Duty 65 on a quantum computer. Running a quantum computer not only requires a huge amount of prerequisite but both types of machine also work in very different ways.

Regular computers manipulate bits. Quantum ones manipulate qubits. The main difference is that, while a bit can only take the value 0 or 1, a qubit can take both values at the same time. As for many quantum physics principles, this looks counter intuitive. The physical principle that explains this behind the scene is called quantum superposition. Going into the details about this is far beyond the scope of this blog post but you can find really good resources popularizing the concept.

What's interesting with qubits is that, when combined, their computation power grows up exponentially compared to a regular computer's bits. Broadly speaking, if one qubit can take both 1 and 0 values, two qubits can take any of the 00, 01, 10 and 11 values or all of them at the same time. This expands to N qubits being capable of representing 2^N values.

Moreover, on a quantum computer, computations can be performed on all states at the same time, using quantum specific logical gates (think of Q versions of AND, OR and XOR except there are an infinite number of them and they have names like "phase shift").

The bottom line is quantum computers are not just the Dwayne Johnson of computers. They run in a very different way and use algorithms that are highly specific and absolutely not trivial.

Then comes the bad news: Google claiming they reached the quantum supremacy. That sounds bad. Quantum supremacy happens when a quantum computer manages to solve a problem not even the most powerful super-calculator can solve. That's what Google did, or claimed to have, between late 2019 and early 2020[1]. And now you see it coming, what kind of problems can't regular computers break? Most of our modern cryptosystems: AES, RSA et al.

 
State of the threat

As we stated above, Quantum Computers can only run Quantum algorithms. What academics have tried to do since the birth of quantum computing concepts is designing quantum algorithm that could take advantage of the specificity of quantum processors to accelerate all or parts of computing that we know to be difficult (as in non-polynomial but not only).

When speaking about cryptography, the main difficult problem we can think of is integer factorization. It's indeed the one that underpins the RSA cryptosystem and thus helps secure most of the Internet communication among other things. It happens that Peter Shor, an American mathematician, discovered an efficient algorithm to solve this problem on a quantum computer in 1994. While regular computing factorization algorithms have a near exponential complexity, Shor's algorithm is polynomial and thus performs exponentially faster than, say, Pollard's rho algorithm[2].

To finish the picture, Shor's algorithm also solves the discrete logarithm problem which underpins other critical cryptographic algorithms such a Diffie-Hellman or El Gamal (as in DSA).

However, unless we all missed severe updates since 2019, RSA encryption still helps to secure most of the Internet and we still set up shared secrets using Diffie-Hellman. What happened to Shor's algorithm and Google's quantum supremacy?

Well, the definition of Quantum supremacy states that the Q computer must solve A problem that regular machines can not, not ALL problems. Google quantum supremacy was reached on a very specific problem that has nothing to do with integer factorization or Shor's algorithm. It's a problem called quantum circuit sampling which is pretty artificial and have very little application outside quantum computing itself.

Google's quantum computer, when it was used to reach that "supremacy", used 56 functional qubits. Recent studies of Shor's algorithm and integer factorization on quantum hardware estimate that 20 millions qubits are necessaries to break a 2048 bits RSA private key, in 8 hours[3]. In current state of knowledge about quantum computing, it is clear we are not even close to reach such a quantum computing power.

How much time will be necessary to reach that critical threshold is impossible to predict. If we suppose Moore laws to hold in quantum world, getting from 56 to 20 000 000 qubits would require about 30 years of research. But that would probably be an inaccurate estimation.

So why should we care about that threat now? In thirty years most of us will probably have retrained as ewes keepers.

The fact is, for most applications, quantum computing does not represent a severe threat for now. That does not mean you can just overlook it. Who knows what will happen? But it probably shouldn't become your number one priority.

There are only two main situations in which you should consider quantum computing and cryptography seriously:

• If your application is expected to still run in many years.
• If the data your application protects will still be sensitive in many years. Indeed, encrypted data could be captured today and decrypted when a big quantum computer is built.

The definition of "many years" may vary. Today, french ANSSI sets the limit to 2030[4], which is not that far from now.

State of the defense

Hopefully, the world has not just been watching the evolution of quantum computing wondering when the collapse will happen. In fact, cryptographers from all around the globe started studying and designing quantum resistant algorithms long before the quantum computer started to become a reality. For example, Robert McEliece published the so called McEliece cryptosystem in 1978[5]. While not originally designed for post-quantum resistance, it has later been studied and proved to actually have this ability.

Since then, multiple new algorithms have been designed that rely on new categories of hard problems which security is, to date, not known to be weakened by quantum algorithms. The main problems currently under study are based on:

• lattices
• error correction codes
• multivariate polynomials

Each of those problems are the basis of multiple algorithms most of which many people are unaware of. For example, error correction codes underlie the following algorithms:

• Big quake
• Classic McEliece
• BIKE
• DAGS
• etc

Moreover, most of these algorithms have pros and cons that should not be trifled with. Some have huge key size, others have large signature size or require an important amount of computing power to be executed safely.

What would be convenient would be to have an AES like default choice for everything. Unfortunately no consensus have been reached yet. However, a NIST competition for post quantum algorithms is currently running[6]. While not finished yet, it reached its third and last phase with only few candidates remaining. In fact there are only four candidates left for public key encryption schemes and three for the digital signature schemes.

What's interesting here is that, for both categories, the NIST selected a list of alternate candidates that would have to be used in case the main choice appears to be vulnerable in the future or does not fit a given usage. This shows that, even among cryptography experts, post quantum world is still uncertain and care is a priority.

In fact, to date, none of the algorithms or problems are trusted as much as RSA and the factorization problem in the regular world. Nothing indicates that post quantum candidates won't appear vulnerable faced to future quantum or even regular algorithms.

I need post quantum security NOW!

Symmetric encryption

If you made it this far in the reading, chances are you are part of those who need to implement post quantum security now, even if only for compliance with regulation expectations.

Fortunately, there are good news and fine ways to set up that without scuttling your security.

First of all, for the good news, symmetric algorithms are (mostly) not threatened by quantum algorithms. In fact, there exists the very versatile Grover algorithm that allows searching through a set of size N in O(N^1/2). When applied to symmetric cryptography it obviously divides attacks complexity by two. This means that, for AES with 128 bits keys, an exhaustive search would only require 2⁶⁴ operations, which is far under the limit of acceptable security.

Of course, we know a lot of serious algorithms, including AES, that accept 256 bits key size. Their remaining strength, against Grover algorithm, is 128 security bits which meets current and future security expectations. No problem here.

Hashing and symmetric authentication

Here again, no attack is known on current algorithms apart from the Grover algorithm. If you use SHA-256 as your go-to hash algorithm, it happens you are already prepared for the post quantum world. How sweet is that!

In fact, the security of hash functions is even the basis of some post quantum constructions as we will see later.

Asymmetric cryptography

This is where problems begin. This category of algorithms is the one that is the most impacted by a quantum computer. As we already stated before, most asymmetric algorithms we use today fall against a quantum attacker.

NIST round 3 candidates can definitely help you prepare for the future. However, with the limited faith we have in them now, it might happen that using them will degrade your security at some point. A solution must be found to consider the future while keeping security against current, regular attackers.

The key here are hybrid mechanisms.

Indeed, to reach the objective we defined, it is necessary to combine both regular and post quantum algorithms in such a way that the resulting mechanism has at least the security level of the remaining algorithm if one of them appears completely broken. Let's take an example with key exchange.

Today, if you need to setup a secret between to parties, you will probably use a Diffie-Hellman key exchange. In the quantum world, you will use a key encapsulation algorithm (an asymmetric encryption algorithm applied on a symmetric encryption key) to send a secret properly encrypted. In the first case, a quantum computer will manage to break your shared secret. In the second one, an attack might be discovered that will decrypt your secret using a regular computer.
The best of both world is therefore to perform two secret exchanges, one with each mechanism, and to combine both keys into a final secret, for example using a cryptographic hash function.

In that case, without knowing both intermediate secrets, an attacker won't be able to recover the final key. Either of the key exchange algorithms can get broken without your mechanism loosing it's security. The only case when everything will burn to ashes is if the quantum ready part of the mechanism gets broken AFTER a quantum computer is built. But this leaves us with enough time to anticipate and, in any case, there is nothing better you can do, except choosing the best candidate algorithm for that not to happen.

The exact same idea can be applied to digital signature. For that, an hybrid mechanism will compute a signature of a message using both a regular and a post quantum algorithm. Both signature must then be included for validation. Once again, the resulting signing mechanism stays secure as long as one of the underlying algorithms stays secure.

There is still a special case to be talked about: the hash based signature schemes. As we already stated above, to the best of our knowledge, hash algorithms are not threatened by quantum computers and algorithms. Therefore, studies were performed to build cryptographic signature mechanisms that would rely only on the security of hash functions.

XMSS and SPHINCS are two examples of signature mechanisms that were successfully built that way. They only rely on classical mechanisms and structures that are combined in such a way that they are immune to known quantum attacks. What's interesting with Hash Based Signatures is that their security can be mathematically proven[7]. They are therefore a very tempting solution as a drop in replacement for digital signatures.

However, they also have important downfalls. First, the size of the signature computed by those algorithms is big, up to tens of kilobytes. But, most importantly, the number of signatures that can be performed with a public / private key pair is limited, between 2^10 and 2^20 for XMSS for example[8]. This makes them unsuitable for any high volume usage. However, they could be used for software signing, secure boot or other similar low bandwidth usage.

Putting it all together

To summarize, here is what you will want to do to anticipate the quantum computer threat:

• Make sure you use 256 bits keys for symmetric encryption, with a state of the art algorithm (AES, CHACHA, etc)
• Make sure you use hash functions with 256 bits outputs for all use cases, including authentication with HMAC.
• Use a hybrid mechanism for all key exchange and asymmetric signing operations. Both regular and quantum mechanisms should be chosen among state of the art algorithms. Round 3 NIST submissions should be considered for the quantum part.
• If you can put up with their drawback, use a Hash Based Signature mechanism which security is often proven (XMSS, etc). Use it in hybridization anyway.

In any case, you should rely on a robust external library to implement the post-quantum algorithms. Implementing cryptographic primitive is often a hard task and it is not different in the quantum world. The Open Quantum Safe project[9] aims to provide such a library. It is available for most platforms and can be used from most languages. It also only implements what is considered state of the art mechanisms.

If you choose to use a hash based signature mechanism, XMSS, or a similar algorithm, is generally implemented in the main crypto libraries. For example, BouncyCastle implements XMSS and SPHINCS along with a few other post quantum algorithms including McEliece and NTRU.

References

[1] https://www.nature.com/articles/s41586-019-1666-5 Quantum supremacy using a programmable superconducting processor

[2] https://pqcschool.org/slides/2019-pqc-school-intro.pdf Introduction to post-quantum cryptography

[3] https://arxiv.org/pdf/1905.09749.pdf How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

[4] https://www.ssi.gouv.fr/uploads/2021/03/anssi-guide-selection_crypto-1.0.pdf Guide de sélection d'algorithmes cryptographiques

[5] https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF A Public-Key Cryptosystem Based On Algebraic Coding Theory

[6] https://csrc.nist.gov/projects/post-quantum-cryptography Post-Quantum Cryptography PQC

[7] https://eprint.iacr.org/2015/1256.pdf Mitigating Multi-Target Attacks in Hash-based Signatures

[8] https://datatracker.ietf.org/doc/html/rfc8391#section-5.3.1 XMSS: eXtended Merkle Signature Scheme

[9] https://openquantumsafe.org/ Open Quantum Safe software for prototyping quantum-resistant cryptography