Status of post-quantum cryptography

Quantum computers have given rise to a raft of hopes and fears. Their computing capabilities could enable us to solve certain problems more quickly than today’s computers, including those upon which modern cryptography is based. Does this mean that the advent of quantum computing will mark the end of cryptography as we know it? And, if so, what contribution can post-quantum cryptography bring to this new paradigm?

The quantum computer is slowly becoming a reality

The field of quantum computing has seen many advances since the early research of the 1980s—especially that of Richard Feynman[i], and the emergence of the first quantum algorithms in the 1990s. The first prototype quantum computers appeared in the 2000s and, since the beginning of the 2010s, there has been a proliferation of substantive and encouraging announcements in the area. These include D-Wave Systems’s launch of the first commercial quantum computer[ii], IBM’s development of a cloud-based quantum machine[iii], and Google’s recent announcement on its new quantum processor[iv]. On a European scale, there has also been the launch of Atos’s quantum simulator,[v] which can test and optimize quantum algorithms for use in real conditions.

As we’ve discussed in a previous article[vi], the fundamental difference between conventional and quantum computers is that traditional machines work on a series of bits whose value is equal to 1 or 0, while quantum computers work on qubits whose value corresponds to a superposition of states[vii]. For a given problem, it’s sometimes possible to write a quantum algorithm which—by making use of this superposition of states and the quantum entanglement[viii] principle—can solve it more quickly than a conventional algorithm. Since such quantum acceleration can only be applied to a limited set of problems (i.e. those for which it’s possible to write a quantum algorithm) it’s likely that, in the future, quantum computers will be used in addition to—rather than in place of—conventional computers.

Today’s quantum computers have only a very small capacity. Google’s quantum processor is rated at 72-qubits, while Intel recently announced the development of a 49-qubit quantum processor[ix]. As an illustration, Google estimates that the number of qubits needed for a real application is between one and ten million. The main difficulty in designing a larger quantum computer lies in the fact that all external interactions induce the phenomenon of quantum decoherence—which means that the quantum entanglement it needs to operate can’t be maintained[x]. The higher the number of qubits, the more difficult it is to maintain the state of coherence. Doing so requires the system to be isolated at very low temperatures. In view of the current state of development, and the challenges still to be overcome, we may still be a long way from quantum computers being used in any practical application.

Classical cryptography’s applications

To understand the implications of quantum computers for cryptography, we first need to understand the principles of classical cryptography—and its applications.

Classical cryptography involves several different types of algorithms:

Asymmetric (or public-key) cryptography, which is used to establish an encrypted channel between two parties for authentication or electronic-signature purposes (examples are: Diffie-Hellmann, RSA, and elliptic-curve cryptography). Asymmetric cryptography is usually based on integer factorization or discrete logarithm
Symmetric (or secret-key) cryptography, which can be used for the effective encryption of data, especially when an encrypted channel has previously been established using asymmetric algorithms (examples are AES and DES). Symmetric cryptography is based on the principles of diffusion and confusion.
Hash functions, which are used to verify the integrity of a file or electronic certificate (examples are MD5 and SHA-2). Hash functions rely on the avalanche effect, which causes each output bit to depend on each input bit.

How might quantum computers change the game?

Among the best-known and oldest quantum algorithms is Shor’s algorithm[xi] which can effectively factorize integers and solve discrete logarithm problems. Come the day we’re able to construct a quantum computer powerful enough to handle very large numbers using Shor’s algorithm, all public-key cryptography based on these problems will be rendered immediately obsolete.

Another well-known quantum algorithm is Grover’s algorithm[xii], which enables the inversion of functions. This algorithm can be applied to search effectively for items in an unordered list or unstructured database, something that can be likened to looking for a needle in a haystack. Grover’s algorithm thus makes it possible to accelerate a search for a symmetric encryption key but does not call into question the principles of secret-key cryptography.

Post-quantum cryptography

Post-quantum cryptography refers to cryptographic algorithms that do not rely on problems which can be solved more rapidly by a quantum computer. Such algorithms won’t be threatened by the advent of—still hypothetical—quantum computers. It should not be confused with quantum cryptography, which is a form of cryptography that makes use of quantum phenomena to achieve its ends. The challenges associated with post-quantum cryptography are twofold:

To establish a new form of public-key cryptography that doesn’t rely on solving integer factorization or discrete logarithm problems;
To strengthen secret-key cryptography—to make it resilient to the key-finding capabilities of quantum computers.

Public-key cryptography will have to be redesigned entirely using new cryptographic systems that are based on, for example, error-correcting codes or Euclidean networks[xiii]. While numerous theoretical solutions exist, much research is still needed to turn these into concrete options. There are several initiatives designed to stimulate research in the area. Examples are the PQCrypto conference series[xiv], which has been running for over ten years, and the evaluation process recently put in place by NIST, which aims to standardize one, or more, post-quantum cryptographic algorithms[xv].

Secret-key cryptography is expected to prove robust in a post-quantum world—provided that the length of keys used is sufficient. Doubling the key size provides an adequate measure of security against quantum computers[xvi]. For example, the AES encryption algorithm will be less secure, but could still be used with a 256-bit key. The security of protocols like Kerberos, which are based on these algorithms, doesn’t need to be fundamentally questioned.

And when it comes to hash functions, quantum algorithms don’t appear to find collisions more quickly than conventional algorithms[xvii]. Hash functions will therefore remain secure in a post-quantum world.

Quantum computing remains a distant threat

The advent of a quantum computer with sufficient capacity to pose a threat to classical cryptography is still a long way off. Between now and then, we can expect research into post-quantum cryptography to have advanced considerably, and that the changes needed in cryptographic constructions will have been widely anticipated.

[i] https://people.eecs.berkeley.edu/~christos/classics/Feynman.pdf

[ii] https://phys.org/news/2011-06-d-wave-commercial-quantum.html

[iii] https://www-03.ibm.com/press/us/en/pressrelease/49661.wss

[iv] https://research.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html

[v] https://atos.net/fr/2017/communiques-de-presse/communiques-generaux_2017_07_04/atos-lance-aujourdhui-le-simulateur-quantique-le-plus-performant-au-monde

[vi] https://www.riskinsight-wavestone.com/2017/06/informatique-quantique-securite/

[vii] https://en.wikipedia.org/wiki/Quantum_superposition

[viii] https://en.wikipedia.org/wiki/Quantum_entanglement

[ix] https://newsroom.intel.com/news/intel-advances-quantum-neuromorphic-computing-research

[x] https://en.wikipedia.org/wiki/Quantum_computing#Quantum_decoherence

[xi] https://en.wikipedia.org/wiki/Shor%27s_algorithm

[xii] https://en.wikipedia.org/wiki/Grover%27s_algorithm