Etude et analyse de cryptosystèmes basés sur les codes correcteurs implantables en pratique
Boly Seck · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
Code-based Cryptography is one of the approaches to building post-quantum cryptosystems. Unlike the difficult problems of discrete logarithm and factorization (number theory), which are soluble with Shor’s algorithm, the security of code-based cryptography relies on the difficult problem of syndrome decoding (code theory). The asymmetric security protocols used today for encryption (RSA), key exchange (Diffie-Hellman), and digital signature (DSA and RSA) are essentially based on these number-theoretic problems. For this reason, since 2016, NIST has launched a standardization process to define new post-quantum standards for these protocols. In this thesis, we first present an efficient software implementation of the binary and secure version of DAGS, a key encapsulation mechanism (KEM) based on generalized Srivastava codes, submitted during the first round process. The construction of the KEM makes it possible to achieve very small data sizes compared with all other codebased submissions. However, due to security concerns raised by Barelli and Couvreur, DAGS was eliminated in the second round of the process. Since then, efforts have been made by the submission’s authors to provide parameters that make it beyond the reach of structural attacks. Our software implementation of binary DAGS performs better than previous implementations and places it as a credible alternative to the code-based finalists for the fourth round of this process. Next, we show that the Goppa polynomial coefficient loading function used in the reference implementation of Classic McEliece leaks secret information during decapsulation. By performing a template attack, we managed to find secret information about these coefficients, in particular their Hamming weight. This information allowed us to find new results in code-based cryptography and to improve the complexity of the exhaustive search for this polynomial on F_2^m. We also propose a new formalism in code-based cryptography, the resolution of which allows us to make a generic attack on the private key in code-based schemes: this is the matrix-vector product problem. Solving this problem using a profiled attack allows us to recover the secret matrix in the Niederreiter scheme without having to face the difficult problem of syndrome decoding. Finally, we show that the rank-metric identification protocol published at CANS 2018 leaks information about the secret, before doing its cryptanalysis. The flaw in the protocol is related to a bad masking of the secret by a simple random permutation on F_q^m. Using a special permutation, we managed to correctly mask the secret in F_q^m before proposing a zero-knowledge rank-based Véron’s identification protocol with the rankmetric settings that yields an efficient signature scheme with the Fiat-Shamir transformation