The Construction of Code-Based Cryptosystems

Abstract : Code-based cryptography was born in 1978 with the McEliece encryption scheme. The idea was simple and attractive: the public key is a scrambled generator matrix of a binary Goppa code and anyone can encrypt by transforming a piece data into a codeword which is obscured by adding to it a random error. The legitimate user can remove the error using the secret algebraic decoder of the Goppa code while the adversary is reduced decode in an arbitrary linear code, a problem known to be intractable. The cryptosystem survived to 35 years of cryptanalysis, with merely a small increase of the code parameters. A dual version, equivalent in terms of security, was proposed by Niederreiter in 1986. An intriguing feature of those schemes is, until recently, a peculiar lack of diversity in the choice of the family of secret codes. Almost all attempts at using efficiently decodable families of codes, other than Goppa codes, have failed. The reason was always the same, the algebraic structure, which allowed decoding, could not be properly hidden: the public generator matrix would leak some information on the secret code. In fact, the security reduction reveals us a very simple but interesting fact: if the public key is pseudo-random then the system is secure. In other words, if we assume that decoding is hard and if there is no efficient way to distinguish the public key of an instance of the scheme from a random matrix then the system is secure. This provides precious indications on the proper way to construct provably secure public-key code-based cryptosystem: the weak spot is the key security. The public is not only the weak spot for security, its size grows with the square of the block length and is certainly one of the major hindrance to using code-based cryptosystems. Key reduction techniques started in 2005 with the works of Gaborit. The idea is to introduce even more structure, for instance by restricting the public-key to block-circulant matrices (i.e. using quasi-cyclic codes). Those techniques lead to keys whose size grow linearly with the block length. It also lead to a new series of algebraic attacks which weakened many, but not all, of the reduced-key propositions. It appears difficult to combine algebraic properties to allow decoding (which essentially means using alternant codes) with an additional quasi-cyclic or quasi-dyadic structure to allow reduced key sizes. A new trend is to prefer graph-based codes (like LDPC codes) to algebraic code. The hope is to obtain more generic constructions, closer to random codes, for which key reduction techniques are safer. The most recent step in that direction was made with the use of quasi-cyclic MDPC (Moderate Density Parity Check) codes. This family has very little structure but still possesses some error correcting capability. Distinguishing QC-MDPC codes is possibly not easier than finding low weight codewords in a random quasi-cyclic code, a problem which is believed to be hard. The main current challenge of code-based cryptography is to progress in that direction, and to find McEliece-like encryption schemes whose security is provably reduced to the hardness of decoding and whose key size grow linearly or almost linearly with the security.
Type de document :
Communication dans un congrès
Fourteenth IMA International Conference on Cryptography and Coding, Dec 2013, Oxford, United Kingdom. 2013
Liste complète des métadonnées
Contributeur : Nicolas Sendrier <>
Soumis le : jeudi 16 janvier 2014 - 12:43:07
Dernière modification le : mardi 17 avril 2018 - 11:31:59


  • HAL Id : hal-00932115, version 1



Nicolas Sendrier. The Construction of Code-Based Cryptosystems. Fourteenth IMA International Conference on Cryptography and Coding, Dec 2013, Oxford, United Kingdom. 2013. 〈hal-00932115〉



Consultations de la notice