Mise en œuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses

Abstract : This thesis is about algorithmic problems arising when someone wants to imple- ment a cryptosystem based on error correcting codes or a cryptanalysis of such a system. The benefits of these systems come from their excellent algorithmic com- plexity, better of several orders than the classical public key schemes. They also bring a credible alternative to the current systems that for most of them rely on number theory and on the problems of factorisation and discrete logarithm. P.Shor showed that these two problems could be solved in polynomial time in the quantum computer model. This computer is far from being operational but we will need alternatives we can trust and that have efficient implementations. After an introductive section bringing required notions in cryptography and error correcting codes theory, this thesis presents in a first part an implementation of the CFS signature scheme, scheme proposed in 2001 by N. Courtois, M. Finiasz and N. Sendrier. This scheme is based on the Niederreiter cryptosystem and relies on the syndrome decoding problem and the indistinguishability of binary Goppa codes. The cumbersome aspect of this scheme (very big public key) may be the reason that slowed the studies of the problems linked to its implementation. This part tries to show that, despite the drawbacks, the scheme can be used in practice. An implementation is proposed and manage to generate a signature in about 1 second. In a second part, an implementation of several algorithms from the Information Set Decoding family is presented. This family is used to decode a linear code in a generic way, that is without using the potential structure underlying in the code. Most of the code based systems rely their security on the difficulty of this problem. It is important to find the most efficient algorithms solving it in order to size the systems correctly. This part presents an implementation of two algorithms of this family (it could be extending to some others) and shows the result of the application of this implementation on cryptographic challenges proposed by D. Bernstein, T. Lange and C. Peters in 2011 together with a cryptanalysis of a encryption scheme based on convolutional codes proposed by C. Löndahl and T. Johansson in 2012.
Document type :
Theses
Complete list of metadatas

Cited literature [69 references]  Display  Hide  Download

https://hal.inria.fr/tel-01097806
Contributor : Grégory Landais <>
Submitted on : Monday, December 22, 2014 - 10:44:25 AM
Last modification on : Friday, May 25, 2018 - 12:02:05 PM
Long-term archiving on: Monday, March 23, 2015 - 7:11:36 PM

Identifiers

  • HAL Id : tel-01097806, version 1

Collections

Citation

Grégory Landais. Mise en œuvre de cryptosystèmes basés sur les codes correcteurs d’erreurs et de leurs cryptanalyses. Cryptographie et sécurité [cs.CR]. Université Pierre et Marie Curie, 2014. Français. ⟨tel-01097806⟩

Share

Metrics

Record views

615

Files downloads

1303