Data security: a post-quantum signature that does the job

Date:
Changed on 12/04/2021
In a world as digital as ours, cryptography, which is used to protect data, is indispensable. However, cryptanalysis, which involves testing current security systems, has revealed that when it comes to dealing with quantum computers, some of these systems are not up to scratch. As a result, transitioning to post-quantum cryptography has become a matter of urgency. Drawing on error correction codes, the researcher Thomas Debris-Alazard has taken research one step closer to achieving this aim.
Illustration ordinateur quantique
Pete Linforth de Pixabay

Cryptography, a PhD, an award

“I would like to thank Inria for the working environment they gave me, and in particular my PhD supervisor Jean-Pierre Tillich, who allowed me to carry out research over a longer period of time without the pressure of results.” This was Thomas Debris-Alazard, currently working as a researcher with the Grace project team at the Inria Saclay – Île-de-France research centre, talking about the prestigious Gilles Kahn prize, which the young researcher was awarded on 14 January for his PhD, completed between 2016 and 2019 as a member of the Secret project team. The title of his PhD was “Cryptography based on codes: new approaches for construction and proofs; contributing to cryptanalysis”. Let’s take a look at it in a bit more detail.

Resisting the quantum computer through encryption

Portrait de Thomas Debris-Alazard, équipe-projet Grace

“Cryptography is the science of the secret”, explains the young researcher. “At this current juncture, it is particularly important given the vast amount of information we exchange via digital means.” The problem is that a quantum computer, something many scientists are working on, would be capable of circumventing certain forms of public key cryptography that are currently used in a range of fields, from defence and finance to health. Indeed, some hostile individuals are already storing this encrypted data and are awaiting the arrival of the quantum computer in order to be able to decipher it. “If you were to build a military aircraft that features cryptography, you would need to be able to ensure that the aircraft wouldn't be vulnerable in 10, 20 or 30 years’ time. That means we have to start modifying our encryption protocols right now.”  

Debris-Alazard has given the computing world a new way of achieving this, having developed the very first signature based on error correction codes that would be capable of withstanding an attack from a quantum computer. So, how does it work? These codes modify a message by removing any errors in a particular way that only the individual who signed the message would be familiar with. This can be used to confirm that the sender of a message is in fact who they are claiming to be, and that the message has not been altered en route.

The solution? To break the mould

When it came to creating his signature, Thomas Debris-Alazard moved away from the conventional approach. “Normally you would try to decode, i.e. to find an error-free message that is close to the message to be signed. But with long distance decoding, the aim is now to find a ‘distant’ error-free version.” 

Let’s consider, for example, a correction code corresponding to all possible first names. If you spell out your name over the phone, saying “D for Daniel”, even if the person only hears “Niel”, they will think “Daniel”, given that this is a ‘close’ error-free version of “Niel”. With long distance decoding meanwhile, when you hear “Niel”, the aim is to find a ‘distant’ first name, like Zenedine.

Although this might not make sense when it comes to telecommunication, that’s not an issue for post-quantum cryptography: what matters is finding a problem that is sufficiently difficult that a quantum computer wouldn’t be able to solve it but a user with the secret code would. This is what Thomas Debris-Alazard’s innovation has made possible, taking us one step closer to data security in a post-quantum world.

The Grace project team in 180 seconds

The name of the project team Thomas Debris-Alazard is a member of speaks to its multidisciplinarity: Grace stands for Geometry, Arithmetic, Algorithms, Codes and Encryption. Headed up by Alain Couvreur, eight permanent researchers, four postdoctoral researchers and a dozen or so PhD students explore algorithms in cryptography, based on error correction codes, factorisation, elliptic curves, etc. The members of the team also work on protocols which incorporate these algorithms. From its initial building blocks through to final construction, Grace - a joint undertaking involving the Inria Saclay-Île de France research centre and the École Polytechnique at the Institut Polytechnique de Paris - has covered a vast field of research in cryptography.