“This tweet may sound technical, it is! » By announcing on TwitterThursday 1is December, the sending of the first encrypted telegram using post-quantum technology, the President of the Republic, Emmanuel Macron, knows very well that he is talking about an issue that will not speak to the general public. However, the development of post-quantum cryptography is an important issue for the world of cryptography, the secrecy of communications and therefore, by extension, for the Internet.
The quantum computer, what is it?
The quantum computer is not necessarily more “powerful” than a traditional computer. On the other hand, it is more suitable for solving certain problems that an ordinary machine struggles to solve. A good example is factorization: it is extremely difficult for a classical computer to decompose a number into prime factors, i.e. to define from which prime numbers (numbers that can only be divided by themselves) it is the product – the factorization of 65, for example, is 5 × 13, 5 and 13 being prime numbers.
This task is, on the other hand, easy for a quantum computer. We have known this for almost thirty years: in 1994, the mathematician Peter Shor developed an algorithm capable of factoring large numbers using such a machine. Shor’s 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, following the example of France, the United States and the United Kingdom, finance important programs and certain large industrialists, like IBM, already have functional quantum computers.
What does this have to do with cryptography?
The aptitude of the quantum computer for factorization has a very real consequence for the world of cryptography: the encryption algorithms used today to ensure the confidentiality of data are in fact mainly based on certain mathematical functions, among which the calculation of the discrete logarithm… and the factorization of integers. The RSA algorithm, considered one of the bases of modern encryption, is thus based on the factorization of two integers.
Quantum computers can therefore, in theory, easily break an encryption and make it possible to read secret communications. Provided you have enough power. To crack the encryption of current algorithms by running Shor’s algorithm, it is estimated that a quantum computer with a power of just over 1,000 qubits is needed, the unit for measuring the computing power of quantum computers. However, in November, IBM announced that it had succeeded in producing a quantum computer capable of operating 433 qubits, which nevertheless still suffers from limitations. In the coming years, manufacturers hope to be able to develop a quantum computer powerful enough to run Shor’s algorithm.
What is “post-quantum cryptography” used for?
Anticipating this deadline, the cryptography community has worked to develop new encryption algorithms that do not rely on operations vulnerable to quantum computers. It is these algorithms that 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 different algorithm proposals resistant to this threat. In July, after several “rounds”, the institute presented the first four algorithms envisaged to become the new standards in this area.
These proposals are a first step but remain experimental for the moment: as noted by the National Information Systems Security Agency (Anssi) in its official position on the subject, published in April, “it is important to recognize and take into account the immaturity of post-quantum cryptography: Anssi will not approve any direct replacement in the short or medium term”.
The agency therefore calls for a certain degree of caution, while encouraging companies and organizations using encryption to anticipate a possible replacement of algorithms in the years to come. A major project, which is not limited to a simple software update but will probably involve the production and installation of dedicated devices in certain critical sectors, such as banking or the military.
What is in the telegram that Emmanuel Macron speaks of?
The content of the French diplomatic message mentioned by the President of the Republic is not particularly confidential: as explained in the press release from the Ministry of Foreign Affairs, it is a memorandum signed between the Minister of Higher Education and Research, Sylvie Retailleau, and Dr. Arati Prabhakar, Director of the United States Office of Science and Technology Policy. This memorandum aims to support the joint efforts of France and the United States on research in quantum computing.
It is therefore above all a spotlight on this issue rather than an actual production of post-quantum encryption tools by the French government. Still, companies are already looking to position themselves. The encryption of the message sent across the Atlantic was thus ensured thanks to the French start-up CryptoNext Security, which specializes in the deployment of new post-quantum encryption algorithms.