Thomas Debris-Alazard is redesigning cryptography in the quantum era

You have just been awarded an ERC Starting Grant to improve post-quantum cryptography. Why does the development of quantum computers pose a threat to data encryption?

Thomas Debris-Alazard: Let’s take a look back to the 1970s, when RSA, the first public-key cryptosystem, was created. In RSA cryptography, security is related to the difficult problem of finding two prime numbers from their product. No conventional attack algorithm has been able to solve it in 50 years. And even if we doubled the computing power of our computers every year, it would still take hundreds of years for these conventional algorithms to succeed. It's a bit like a thief trying to test all the possible combinations of a complex digital lock... RSA has therefore been widely deployed to secure data sent via the internet in particular.

But in 1994, mathematician Peter Shor revealed a quantum algorithm, Shor’s algorithm, capable of breaking RSA encryption. Quantum algorithms are indeed more powerful than conventional algorithms, as they can process many operations simultaneously. And this poses a serious problem in that if I build a military aircraft today that uses RSA encryption, I want to be sure that it cannot be attacked by a quantum computer in 10 or 20 years' time. Similarly, I’m guessing that governments don't want sensitive data that is encrypted today to be stored and then decoded in a few years' time. We therefore need to start using secure, or ‘quantum safe’ cryptography now. 

The aim of your IQ-SCALe project is to verify the security of the post-quantum cryptography solutions under development, particularly the solutions using Euclidean lattices and codes. What do these methods actually involve?

They are very similar to each other and are based on a different problem to that of RSA. Here, we imagine a finite or infinite grid, which serves as the public data. If I want to send a message confidentially, I encode it as a point on the grid, at the intersection of lines. Encryption consists of moving this point off a line, while decryption aims to recover the original location of the point, i.e. the nearest point. In the code-based method, the distance is measured according to the Hamming distance, whereas in the Euclidean lattice method, it corresponds to a Euclidean distance. Solving the problem in two dimensions is simple, but it becomes much more complex in 1,000 or 2,000 dimensions, when 1,000 or 2,000 pieces of information are needed to define the location of a single point. This is a problem that we hope will be sufficiently challenging for quantum algorithms. These are the techniques currently favoured by standardisation bodies such as NIST (National Institute of Standards and Technology).

Why is it necessary to verify the security of these methods?

For the moment, encryption algorithms have not been sufficiently tested against quantum attacks. The proof: NIST received around 110 submissions of post-quantum encryption algorithms, and they were subjected to around 40 attacks, but none of them involved quantum algorithms! Too little research is being conducted on the subject, and too few scientists are trained in this field. Another illustration of this lack of expertise was revealed last year. A researcher announced that he had successfully solved code and lattice problems, but his calculations turned out to be wrong, and because there are so few cryptographers working on quantum problems, it took a long time to come to this conclusion. 

My idea is therefore to both improve students' skills in the field of quantum-safe cryptography, combining cryptography and quantum algorithmics, and to develop new quantum algorithms to test the robustness of Euclidean lattices and codes. The European Union considered these ideas promising enough to award me a €1.4 million ERC Starting Grant for five years. With this backing, I will be able to fund three theses and two postdoctoral fellowships from February 2026. I am delighted, as it proves that people are really starting to acknowledge the importance of developing a cryptographic community with solid knowledge of quantum algorithmics. But I am mindful that, while I was awarded this grant, it is actually recognition for an entire research community. These ideas were developed thanks to discussions with my colleagues from the Grace joint project team (Inria, Ecole Polytechnique, CNRS) and the facilities and support provided by Inria, both during my thesis and now in my current role.

How do you plan to test Euclidean codes and lattices?

At the heart of my project lies the work of Oded Regev, a computer scientist who, in the 2000s, sought to adapt Shor's algorithm to solve coding and lattice problems. He may have been unsuccessful, but his research boosted our confidence in this type of cryptography, and his results are now recognised as a major contribution to post-quantum cryptography. 

I recently discovered that the effectiveness of Regev's approach is closely linked to sphere packing problems. These involve questions like: how many cannonballs can I store in a ship's hold if I stack them in the most efficient way possible? In three dimensions, the human mind is able to solve this problem. But in higher dimensions, mathematicians have so far only been able to establish upper bounds, which tells us that it is impossible to store more than x cannonballs in the hold, and lower bounds, which guarantee that at least x cannonballs can be stored in the hold. The effectiveness of Regev's algorithm relies precisely on one of the known upper bounds. But this particular bound is not the most precise available, and other, more accurate bounds have been discovered since. As a result, Regev's adaptation of Shor's algorithm is not the most optimal, but by improving it, we may be able to break existing codes and lattices. This is what we aim to explore. This will not be an easy task, however. We will need to explore mathematical theories in depth and combine them with post-quantum cryptography algorithms to devise new, potentially effective attacks.

What could be the outcome of your work in the long term?

There are two possible outcomes. Either we succeed in proving that quantum algorithms can solve code and lattice problems, which would call into question current developments in part of post-quantum cryptography. Or we will fail but will have contributed to boosting confidence in these systems by proving that they can withstand the attacks we subjected them to. In either case, it will be a major breakthrough for the field. Not to mention that we will have provided students with this specific training, thereby adding to the community of scientists capable of creating and testing quantum-safe cryptography algorithms. A strategy that, once again, can only improve our future digital security.

Find out more

• Debit cards and transaction security: moving towards post-quantum cryptography (by Thomas Debris and Antonin Leroux - in French), The Conversation, 16/3/2022.
• Tools to facilitate quantum cryptanalysis, Inria, 24/4/2025.
• Securing our data in the quantum era: a major challenge, Inria, 20/1/2025.