Keeping information secure in the era of the quantum computer

This subject is the focus of the research being carried out by , within the project team. GRACE specialises in cryptography, with a particular focus on cryptographic primitives built using algorithmic number theory and algebraic codes, as well as cybersecurity. 

It is around this theme that the research of Antonin Leroux, a second year PhD student in the GRACE project-team, which is a joint team with the École polytechnique, and Benjamin Wesolowski, CNRS researcher and member of the LFANT project-team, revolve around this theme. Specialized in cryptography, these teams are interested among other things in cryptographic primitives built from the algorithmic theory of numbers and algebraic codes as well as in cybersecurity.

Antonin Leroux’s research is centred around isogeny-based cryptography, a new field within cryptography which has emerged over the course of the last ten years. Isogeny-based cryptography works by creating difficult mathematical problems, which are then used to generate a level of complexity that even a quantum computer would be unable to decipher. This research has seen him given a Best Paper Award, an internationally-renowned prize given to the best scientific articles submitted for the Asiacrypt conference, which is set to run from 7 to 11 December.

Research recognised by a Best Paper Award

Attributed by the committee of the 2020 Asiacrypt conference, the Best Paper Award has been given to an article written by Antonin Leroux, Luca De Feo[1], David Kohel[2], Christophe Petit[3] and Benjamin Wesolowski[4], in which they presented their research into isogeny-based cryptography.

The paper concerns a new isogeny-based digital signature protocol, which has the advantage of being ‘post-quantum’, meaning it is resistant to attacks employing the use of quantum computers.  “Unlike an email signature that takes the form of a first name and a surname and which anyone can imitate, the concept of the digital signature involves creating one that only the sender can make. To do this, a signature template is used to generate a specific sequence of characters. Any external individual who then sees the signed message will be able to verify the identity of the recipient”, explains Antonin Leroux.

The purpose of digital signatures is to enable senders to be identified entirely digitally. “Just like signing a cheque, a digital signature lets you sign a message in such a way that people will be able to tell who has written it just by looking at it”.

Another advantage is the size of this digital signature. The size of a signed message affects the speed at which it can be sent over a network, and what sets post-quantum signatures apart is their size, in that they are the smallest currently available. Digital signatures are particularly useful for connected objects with small memories, such as watches or connected cameras.

The challenge of post-quantum cryptography

Unlike standard computers, which are coded in binary, quantum computers operate using quantum bits, known as qbits, which are superpositions of 0 and 1. These new computers use the principle of quantum superposition to deal with the issue of infinitesimals.

At the infinitesimal level, particles can be thought of like lottery tickets. Before the draw is made, the status of each ticket is temporarily indeterminate: each ticket is either a winner or a loser. Those particles which have yet to be measured are said to be in an indeterminate state, a state that a standard computer would be unable to process. Quantum computers, however, are able to process this data using qbits. By processing data in all of its possible states, quantum computers are thus able to process much more quickly and handle a lot more information than a standard computer.

The development of functional quantum computers, which are expected to arrive in the next ten to twenty years, poses a real challenge for cryptography. The emergence of these computers will significantly weaken current cryptography, potentially endangering personal data. “This is why we have to seek out new mathematical problems which don’t have this weakness. These new problems will eventually enable us to counter the threat of attacks made possible by quantum computers”, says Antonin Leroux. “We don’t know exactly when functional quantum computers will appear, but we need to be ready for them when they do.”

The future of research into post-quantum cryptography

The methods developed in this field of cryptography will be extended to other areas, such as encryption or generating secure randoms.

“In the context of digital signatures, we started off with basic formulations, which we then adapted and improved before putting them together to create this specific protocol. The goal for the future is to see if the tools developed for use with digital signatures could be used to build other protocols. Our motivation is pretty simple: we have new tools, and we want to see how far we can go with them, because this could lead to new discoveries.” 

To find out more

SQISign: Compact Post-Quantum Signatures from Quaternions and Isogenies
L. de Feo, A. Leroux, D. Kohel, C. Petit and B. Wesolowski
https://eprint.iacr.org/2020/1240.pdf