Post-Quantum Cryptography: What is Emmanuel Macron Talking About?

“This tweet may sound technical, it is! » By announcing on TwitterThursday 1^Eh In December, when sending the first encrypted telegram using post-quantum technology, the President of the Republic, Emmanuel Macron, is well aware that he is talking about an issue that the general public does not talk about. However, the development of post-quantum cryptography is an important issue for the world of cryptography, for the secrecy of communications, and therefore for the Internet.

Quantum computer, what is it?

A quantum computer is not necessarily “more powerful” than a traditional computer. On the other hand, it is better suited to solving certain problems that a conventional machine would struggle to solve. A good example is factorization: it is extremely difficult for a classical computer to decompose a number into prime factors, that is, to determine which of the prime numbers (numbers that can only be divided by themselves) is a product – the factorization of 65. For example, there is 5 × 13, 5 and 13 are prime numbers.

This task, on the other hand, is easy for a quantum computer. We’ve known this for almost thirty years: in 1994, mathematician Peter Shore developed an algorithm that can factor large numbers using such a machine. While the Shore algorithm works, the American company IBM tested it on a small scale in 2001.

In recent years, research on quantum computer projects has made significant progress. Several governments, such as France, the United States, and the United Kingdom, are funding significant programs, and some major industrialists, such as IBM, already have functional quantum computers.

What does this have to do with cryptography?

The factorization capability of a quantum computer has very real consequences for the world of cryptography: the encryption algorithms used today to ensure data privacy are in fact primarily based on certain mathematical functions, including the computation of discrete logarithms… and the factorization of integers. The RSA algorithm, which is considered one of the foundations of modern encryption, is based on the factorization of two integers.

Thus, quantum computers could, in theory, easily break encryption and make it possible to read secret communications. Provided you have enough power. Running Shore’s algorithm requires a quantum computer with a power greater than 1,000 qubits, a unit of measurement for the computing power of quantum computers, to break the encryption of current algorithms. However, in November, IBM announced that it had succeeded in producing a quantum computer capable of operating at 433 qubits, which, however, still suffers from limitations. In the coming years, manufacturers hope to be able to build a quantum computer powerful enough to run Shor’s algorithm.

What is “post-quantum cryptography” used for?

In anticipation of this deadline, the cryptography community has been working to develop new encryption algorithms that do not rely on operations vulnerable to quantum computers. These algorithms are referred to as “post-quantum cryptography”.

In the United States, the National Institute of Standards and Technology has been running a program since 2016 to test and test various algorithm proposals resistant to this threat. In July, after several “rounds”, the institute presented the first four algorithms that have become new standards in the field.

These proposals are a first step, but for now they remain experimental: as noted by the National Agency for Security of Information Systems (Anssi) in its official position on the subject, published in April, “It is important to recognize and consider the immaturity of post-quantum cryptography: ANS will not prove any direct replacement in the short or medium term..

The agency is therefore urging some caution, while encouraging companies and organizations that use encryption to consider possible replacement algorithms in the coming years. A major project that is not limited to a simple software upgrade, but is likely to include the production and installation of special equipment in certain critical sectors such as banking or the military.

What is written in the telegram that Emmanuel Macron is talking about?

The content of the French diplomatic message mentioned by the President of the Republic is not particularly confidential: as explained in the press release of the Ministry of Foreign Affairs, it is a memorandum signed between the Minister of Higher Education and Research, Sylvie Retaleau. Arati Prabhakar, director of the United States Office of Science and Technology Policy. This memorandum aims to support joint efforts between France and the United States in quantum computing research.

Therefore, this is primarily the focus of this issue, rather than the actual production of post-quantum encryption tools by the French government. Still, companies are already looking to position themselves. Thus, the encryption of the message sent across the Atlantic was ensured thanks to the French startup CryptoNext Security, which specializes in the implementation of new post-quantum encryption algorithms.