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

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

“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.