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.
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.
Recovering Short Secret Keys of RLCE in Polynomial Time, Alain Couvreur, Matthieu Lequesne and Jean-Pierre Tillich. In PQCrypto 2019.
Analysis of code-based post-quantum cryptosystems, Matthieu Lequesne, Sorbonne Université (2021).
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 .
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) .
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.