Computer scientists love to scare themselves with dark technological deadlines, such as the Y2K bug. With Q-Day, in reference to quantum computing, they are served. This term designates the day when a quantum computer will be powerful enough to make short work of the essential public key encryption algorithms, currently untouchable by traditional computing. This feat will then have the appearance of an earthquake. “This will collapse a whole section of cryptography, used for things we use on a daily basis,” summarizes Vincent Strubel, director general of the National Information Systems Security Agency (Anssi). Beyond diplomatic or military secrets, the secure operation of the Internet, electronic payments and even GPS geolocation signals rely on encryption technologies. A threat which constitutes a significant risk for the security of the United States, by putting pressure on its technological and scientific leadership, Joe Biden noted in a May 2022 memorandum.
In reality, computer scientists have had this fateful deadline in mind for almost thirty years. In 1994, mathematician Peter Shor, now a Santa Claus-like professor at the Massachusetts Institute of Technology, showed that a quantum computer, then in its infancy, could break the very popular RSA algorithm. This asymmetric encryption system – there is a public key and a private key, linked mathematically – is based on the calculation of two large prime numbers multiplied together. One of the methods for decrypting a message is therefore to carry out factorization, that is to say determining the integers used. An extremely complex task for conventional computers, which would have to run for an eternity to find the key.
Quantum computing, on the contrary, “knows how to attack this type of mathematical problem very well,” observes researcher Pierre-Alain Fouque, a specialist in cryptography. A victory by KO obtained thanks to a paradigm shift. “In classical computers, information is described in a binary way, with zeros and ones,” explains Eleni Diamanti, CNRS research director at Sorbonne-Université. But quantum computing, with the possible superposition of zeros and ones , allows access to intermediate states and therefore to a much richer space. This allows certain calculations to be accelerated very significantly.”
Quantum threat
The response to this threat is called post-quantum encryption. These are in fact algorithms capable of withstanding this computing power. This strategic project was opened eight years ago by the National Institute of Standards and Technology (Nist), an American public agency, with a competition that has cryptographers around the world salivating. The challenge ? Implement the encryption standards of tomorrow. “This may give the impression that the European Union is lagging behind, but the major standardization organizations are in the United States,” recalls MP (Renaissance) Mounir Belhamiti.
In 2022, after finding flaws in many of the 82 projects presented, Nist cautiously selected four proposals. The procedure may seem long. But an algorithm chosen too quickly and ultimately vulnerable would be a serious problem. Diversifying mathematical problems, with several different encryption schemes, is also “a way of not putting all your eggs in one basket”, observes Pierre-Alain Fouque. The researcher is one of the many French people – we find them in the four selected projects – who participated in the competition. The signature algorithm he worked on, Falcon, is thus based on Euclidean networks. To summarize in broad strokes, it is a kind of geometric problem in a large mesh made of hundreds of vectors where you have to find the point closest to the origin.
Cocorico, France has many assets in this area. In addition to research of “extraordinary vitality”, praised Anssi a few years ago, France has significant players who follow the subject. Like the industrialist Thales. The company headed by polytechnician Patrice Caine has just taken the lead in a consortium to develop a post-quantum encryption solution dedicated to the protection of communications. The work of one of the start-ups included in this consortium, CryptoNext Security, specializing in software solutions, also enabled, at the end of 2022, the sending of a first French diplomatic message supposed to be inviolable, even with a quantum computer. . It must be said that the post-quantum market promises to be juicy. It is estimated at $10 billion by 2030 by the Boston Consulting Group.
More qubits, more errors
While awaiting future contracts, this ecosystem is powered by part of the 1.8 billion public and private euros released as part of the national quantum strategy launched in 2021. Post-quantum cryptography is in fact one of the five objectives of this government plan. An area where implementation will be key. “It must be robust and efficient, because even if the algorithms are perfect, there are other threats,” explains Bernhard Quendt, the technical director of Thales. The secret of encryption can, for example, be revealed by analyzing the electromagnetic radiation of a chip. This must be resistant to the injection of faults, this way of making it speak by derailing it. New solutions must also be adapted to the needs of the industry and sufficiently efficient to equip telephones or cards. Post-quantum encryption will finally have to be used with current algorithms, a hybridization deemed more secure.
This excess of energy will perhaps be of no use. Because it is not absolutely certain that we will one day be able to design a quantum computer powerful enough to run Shor’s algorithm. “Some experts talk about 2030 or 2035, others much later,” agrees Florent Grosmaitre, CEO of CryptoNext Security. Condor, this quantum processor of 1,121 qubits (or quantum bits) from the IT giant IBM, does not have the muscles to break current encryption algorithms. Many more would likely be needed, on the order of a million qubits. However, scientists come up against a pitfall. The more qubits they collect, the more errors they get.
Secret weapons programs
However, the industry has made rapid progress in recent years. “It’s like AI, it could happen faster than we think,” warns Bernhard Quendt. Because the investments in quantum computing are there. These machines of the future could boost our weather forecasts or medical research. If “it is very unlikely that we will be able to make a very large quantum computer in a monolithic way, research will undoubtedly lead to interconnected modular architectures”, warns Eleni Diamanti.
A race that could overtake everyone. “In industry, infrastructure migration plans will take five to ten years, or even more,” says Florent Grosmaitre. On a military scale, the decades also pass quickly for complex weapons programs such as an aircraft carrier or a submarine. Equipment whose secrets the public authorities want to keep as long as possible. This threat is summarized in a formula “Harvest now, decrypt later”. Understand by this that States could have already started to amass encrypted databases while waiting to be able to update them. A perspective already integrated by the Signal foundation, which manages the secure messaging service of the same name. Since last September, out of an abundance of caution, it has now put its users’ messages through a post-quantum mill. A leap also made, a few months later, by Apple for its iMessages. Q-Day or not, their secrets will be well kept.
.