Post-quantum cryptography: Inria research shines

The news came at the heart of the summer with the publication of two scientific articles: the reliability of the SIKE (Supersingular Isogeny Key Encapsulation) protocol, presented as one of the most robust in terms of cybersecurity, has been undermined by the attacks of a new cryptanalysis algorithm.

These results, published by two researchers from the Catholic University of Louvain and taken up by two other experts from the University of Bristol, have not gone unnoticed by Damien Robert, a researcher at the Inria center of the University of Bordeaux in the LFANT project team. They demonstrate the potential weaknesses of a post-quantum cryptography protocol, a fast-growing field of research that is of interest to large computer, information and communication groups, as well as to governments, because of the need for secrecy (military, industrial, political, banking, etc.) in many economic activities.

"With mathematics and computer science, humans have long learned to encrypt messages using algorithms, recalls the researcher. To break the current systems consists in solving a very complex mathematical problem, out of reach of today's computing means. But the possible development of quantum computers, new computing machines with a multiplied speed of calculation, imposes to rethink the techniques of cryptography: research in post-quantum cryptography is thus developed, whose objective is to ward off future cyber attacks".

Among the most widely used post-quantum cryptographic techniques are "isogeny-based systems". What is their principle? The key to encrypting the information is a randomly constructed path in a gigantic graph (like a road map where there are more cities than the number of atoms in the universe). This path is secret, but the arrival point is made public. A mathematical result guarantees that there are too many possible paths to find the hidden path by testing all possibilities, so it is impossible to "crack" the key!   

This method allows to exchange secret information through a public channel (like a credit card number to pay on a website). In practice, it requires significant storage capacity. It is therefore necessary to exchange additional information (such as clues about the path followed) for the encryption algorithm to be effectively implemented on a computer.

In protocols such as SIKE, graphs are constructed from simple mathematical curves (they are of "dimension 1", like a straight line)," explains Damien Robert. The attack published this summer consisted in using graphs based on more complex surfaces (of "dimension 2", like a rectangle) and in exploiting the encryption indices to find the path between the starting and ending points in certain cases.

Always on the lookout for publications in his field of research - even during a summer break! -The researcher quickly became convinced that the attack developed by his colleagues could be generalized into an algorithm capable of breaking the SIKE protocol for sure.

I extended the principle of the attacks by using graphs built from mathematical objects of dimension greater than 2 - up to dimension 8," explains the researcher. This makes it possible to find in all cases the path used by the protocol. Moreover, I have shown that we can always do this efficiently - that is to say, with great precision and reduced computing time. With his results, the researcher then quickly published them, thus signing the end of the reliability of the SIKE protocol. 

If he succeeded in developing his algorithm in only a few days of work, after having read the work of his colleagues, it is because he is one of the rare world experts on this subject, which he has been digging for a long time! "I discovered 'higher dimensional isogenies' during my first thesis work in cryptography at the Inria center in Nancy - Grand Est, more than ten years ago... As a young graduate of ENS Paris in mathematics and computer science, I had joined the Institute's teams to work on applications in classical cryptography at that time. Little did I know that my work would find applications in post-quantum cryptography many years later!

The work of cryptology researchers is precisely this: to imagine the most secure algorithms possible and then to develop particularly effective attacks to ensure their reliability. "This type of challenge, and the research it stimulates, allows us to constantly improve the reliability of cryptographic protocols! It's about turning a weakness into a new strength: my work, for example, opens the way to new, more versatile and robust algorithms..." Until the next discovery - to which Damien Robert will no doubt contribute - of a flaw in another protocol?