I defended my PhD entitled
Structured Codes for Cryptography: from Source of Hardness to Applications
on Friday, December 15, 2023 at 09:00am (Paris time).
My manuscript and the slides of the defense are available.
President:
Reviewers:
Examiners:
Supervisors:
In this PhD thesis, we focus on cryptography based on error-correcting codes, and more specifically on those offering a strong algebraic structure. Code-based cryptography is not new, as McEliece already proposed in 1978 an encryption scheme which relies, among other things, on the hardness of the decoding problem. It is important to note that McEliece cryptosystem still appears to be resistant to known attacks (even though its parameters needed to be updated to meet new security standards), including those involving quantum computers. In particular, this makes of McEliece the oldest cryptosystem with this property. Indeed, it is known since the 1990s that Shor algorithm poses a significant threat to the cryptography currently used in practice. However, McEliece system suffers from a major drawback : its public keys are huge.
In order to address this issue, it was proposed to use error-correcting codes with an additional algebraic structure, such as quasi-cyclic codes, which allow for a more compact representation and better performances. However, it is fundamental to ensure that this efficiency does not come at the expense of security. This is especially important as the National Institute for Standards and Technology (NIST) has announced that the next post-quantum encryption standard will be chosen out of three candidates, two of them (BIKE and HQC) based on structured codes.
Nevertheless, HQC relies on a different paradigm than that of McEliece : its security is based on the difficulty of the so-called decisional variant of the decoding problem. In the case of generic codes, it is known that the decisional and search versions, which is the most studied one, are in fact equivalent. However, the situation is much more uncertain in the case of structured codes for which no reduction from search to decision is known.
Yet, the existence of theoretical reductions to well-established hard problems is an important characteristic to increase confidence in a cryptosystem. In particular, one of the contributions of this thesis is an attack on code-based encryption schemes based on rank metric codes (another form of structured codes) that did not have this kind of reduction. This is the context of the second part of this thesis.
Inspired by some techniques from lattice-based cryptography, we provide the first search-to-decision reduction for certain families of quasi-cyclic codes. It is based on a new interpretation of these codes using tools arising from the theory of function fields in positive characteristic, namely the Carlitz Modules. However, this reduction has certain limitations which we try to overcome.
Finally, in the last part, we explore another application of these structured codes in the field of secure multiparty computation (MPC). The goal of an MPC protocol is to allow several players to perform a computation together so that they each only has partial knowledge of the input, and no one learns anything else than the output. It turns out that they can often benefit from long lists of correlated random elements to achieve fast computation, and a new tool called Pseudorandom Correlation Generators (PCG) was recently introduced to efficiently generate those long list. Thanks to our analysis of quasi-cyclic codes, we provide a more solid theoretical foundation for the best PCG constructions. Last but not least, we introduce for the first-time the decisional variant of the decoding problem of so-called quasi-abelian codes, and analyse its hardness in light of the techniques developed in this thesis. This allows us to overcome certain limitations of the state-of-the-art PCGs.