Although there are no practical quantum computers yet, many believe it is only a matter of decades before they become a reality. This threatens most public-key cryptosystems, especially the widely used RSA. There is a need to develop post-quantum cryptosystems, that is cryptosystems that remain secure against an adversary equiped with a quantum computer. The National Institute of Standards and Technology (NIST) announced in 2016 a call for standardization of post-quantum cryptosystems. The cryptosystems proposed in response for this call are available online and most of them are based on two families of problems: error-correcting codes and lattices. My work is dedicated to the design and analysis of the security of the cryptosystems based on error-correcting codes, especially in the context of the NIST standardization process.
Security analysis of code-based cryptosystems. Among the 69 proposals that the NIST juged "complete and proper", 23 rely on the hardness of problems from coding theory. These cryptosystems need to be thoroughly studied. We found attacks on two proposals (Edon-K and RLCE) and are still studying remaining proposals.
Syndrome Decoding in large weight. Most code-based cryptosystems rely on the Syndrome Decoding problem. It is therefore very important to understand the complexity of this problem. We studied this problem in the non-binary case, especially in a ternary field, and showed that finding large-weight codewords is an interestingly difficult problem. This problem is used in the new code-based signature, called Wave. We intend to study the complexity of the problem for larger fields.
Practical security of generic decoding. While there is a lot of litterature concerning the theoritical security of the syndrome decoding problem, it is sometimes difficult to relate this to the practical complexity of solving instances of the problem. Therefore we launched a website with code-based challenges to solve: decodingchallenge.org. The next step is now to design and run the state-of-the-art syndrome-decoding algorithms to try to solve some of the challenges. See this page for a list of useful resources.
Decoding of QC-MDPC codes. The goal of this project is to study the decoding of the Quasi-cyclic Moderate Density Parity Check (QC-MDPC) codes. These codes are very promising for post-quantum cryptography and are used in the BIKE cryptosystem, submitted to the NIST standardization process. In order for these codes to be used for cryptography, one needs to have an efficient decoder with an extremely low decoding failure rate. Besides, recent attacks (following [GJS16]) show that the decoder must run in constant time. We are working on the developpement of state-of-the art decoders achieving both properties.
Analysis of code-based post-quantum cryptosystems, Matthieu Lequesne, Sorbonne Université (2021).
The PQC Migration Handbook: Guidelines for Migrating to Post-Quantum Cryptography, AIVD, TNO and CWI (2023), see press release.
On the security of subspace subcodes of Reed-Solomon codes for public key encryption, Alain Couvreur and Matthieu Lequesne. In IEEE Transactions on Information Theory.
QC-MDPC: A Timing Attack and a CCA2 KEM, Edward Eaton, Matthieu Lequesne, Alex Parent and Nicolas Sendrier. In PQCrypto 2018.
Attack on the Edon-K Key Encapsulation Mechanism, Matthieu Lequesne and Jean-Pierre Tillich. In ISIT 2018.
Recovering Short Secret Keys of RLCE in Polynomial Time, Alain Couvreur, Matthieu Lequesne and Jean-Pierre Tillich. In PQCrypto 2019.
Ternary Syndrome Decoding with Large Weight, Rémi Bricout, André Chailloux, Thomas Debris-Alazard and Matthieu Lequesne. In SAC 2019.
CBC 2017, A side Channel Key Recovery Attack on QC-MDPC Using the Syndrome Weight, at 5th Code-Based Cryptography Workshop, Universidad de La Laguna, Spain, May 31, 2017 .
CBC 2018, Attack on the Edon-K Key Encapsulation Mechanism, at 6th Code-Based Cryptography Workshop, Florida Atlantic University, Fort Lauderdale, USA, April 5, 2018 .
Journées C2 2018, Recovering short secret keys of RLCE key encapsulation mechanism in polynomial time, at Journées Codage & Cryptographie, Aussois, France, October 10, 2018 .
GT BAC, Recovering short secret keys of RLCE key encapsulation mechanism in polynomial time, at Groupe de Travail "Butte aux Cailles", Paris, France, January 17, 2019 (SLIDES) .
MWCC, Ternary Syndrome Decoding in Large Weight, at Munich Workshop on Coding and Cryptography (poster session), Munich, Germany, July 15, 2019 (POSTER).
Rennes, Cryptanalysis of GRS-based Cryptosystems Using the Square-Code Distinguisher, at Séminaire de Cryptographie de l'IRMAR, Rennes, France, February 07, 2020 (SLIDES) .
Versailles, Decoding challenge: Assessing the practical hardness of syndrome decoding for code-based cryptography, at Séminaire de Cryptographie de l'UVSQ, Rennes, France, February 27, 2020 (SLIDES) .
Journées C2 2020, On the security of subspace subcodes of Reed-Solomon codes, at Journées Codage & Cryptographie, virtual, November 05, 2020 (SLIDES) .
CWI Crypto group Seminar, On the security of subspace subcodes of Reed-Solomon codes, at CWI Crypto group Seminar, virtual, December 18, 2020 (SLIDES) .
Decoding challenge website: a website dedicated to challenges in code-based cryptography to assess the practical security of code-based problems. Nicolas Aragon, Julien Lavauzelle and Matthieu Lequesne, 2019.
PQCrypto 2020: co-organization of the 11th International Conference on Post-Quantum Cryptography, organized virtually (from Paris), September 21-23, 2020.