I defended my PhD entitled
on May 25th, 2021 at 2:00pm (Paris time).
Today, most public-key cryptosystems used to ensure the privacy and authenticity of communications rely on the hardness of number theoretic problems. For instance, the security of the RSA algorithm is based on the fact that factoring a product of large prime numbers is computationally hard. However, in 1994, Shor proposed an algorithm to efficiently solve this problem using a quantum computer. Large-scale quantum computers do not exists yet, but this could change within the next decades. Therefore, we need new public-key cryptosystems that resist quantum attacks. This is known as post-quantum cryptography.
In 2017, the American National Institute of Standards and Technologies (NIST) invited researchers to submit proposals for the standardisation of post-quantum cryptographic algorithms. One promising solution is to design cryptosystems based of the hardness of decoding error-correcting codes. A significant proportion of cryptosystems submitted to the NIST use this approach.
In this thesis, we propose an analysis of different code-based post-quantum cryptosystems. First, we study the case of QC-MDPC codes and show that one can recover the private key by observing the syndrome weight or the number of iterations of the decoding algorithm. Then, we propose key-recovery attacks exploiting the structure of three cryptosystems: Edon-K, RLCE and XGRS. Finally, we study the hardness of the general decoding problem for ternary codes, in the large weight setting, which is used in the Wave signature scheme.