Selected publications

 A New Efficient Threshold Ring Signature Scheme based on Coding Theory
C. Aguilar Melchor, P.-L. Cayrel, P. Gaborit and F. Laguillaumie
IEEE Trans. Inf. Theory, number 57(7), pages 4833-4842, 2011, impact factor : 2.36
 Efficient implementation of a CCA2-secure variant of McEliece using generalized Srivastava codes

In this paper we present efficient implementations of McEliece variants using quasi-dyadic codes. We provide secure parameters for a classical McEliece encryption scheme based on quasi-dyadic generalized Srivastava codes, and successively convert our scheme to a CCA2-secure protocol in the random oracle model applying the Fujisaki-Okamoto transform. In contrast with all other CCA2-secure code-based cryptosystems that work in the random oracle model, our conversion does not require a constant weight encoding function. We present results for both 128-bit and 80-bit security level, and for the latter we also feature an implementation for an embedded device.

P.-L. Cayrel, G. Hoffmann and E. Persichetti
Proceedings of PKC 2012, LNCS 7293, pages 138-155, Springer-Verlag, 2012
 A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem

At CRYPTO’93, Stern proposed a 3-pass code-based identification scheme with a cheating probability of 2/3. In this paper, we propose a 5-pass code-based protocol with a lower communication complexity, allowing an impersonator to succeed with only a probability of 1/2. Furthermore, we propose to use double-circulant construction in order to dramatically reduce the size of the public key. The proposed scheme is zero-knowledge and relies on an NP-complete coding theory problem (namely the q-ary Syndrome Decoding problem). The parameters we suggest for the instantiation of this scheme take into account a recent study of (a generalization of) Stern’s information set decoding algorithm, applicable to linear codes over arbitrary fields \mathbbFq ; the public data of our construction is then 4 Kbytes, whereas that of Stern’s scheme is 15 Kbytes for the same level of security. This provides a very practical identification scheme which is especially attractive for light-weight cryptography.

P.-L. Cayrel, P. Véron and S. M. El Yousfi Alaoui
Proceedings of SAC 2010, LNCS 6544, pages 171-186, Springer-Verlag, 2010
 Reducing Key Length of the McEliece Cryptosystem

The McEliece cryptosystem is one of the oldest public-key cryptosystems ever designed. It is also the first public-key cryptosystem based on linear error-correcting codes. Its main advantage is to have very fast encryption and decryption functions. However it suffers from a major drawback. It requires a very large public key which makes it very difficult to use in many practical situations. A possible solution is to advantageously use quasi-cyclic codes because of their compact representation. On the other hand, for a fixed level of security, the use of optimal codes like Maximum Distance Separable ones allows to use smaller codes. The almost only known family of MDS codes with an efficient decoding algorithm is the class of Generalized Reed-Solomon (GRS) codes. However, it is well-known that GRS codes and quasi-cyclic codes do not represent secure solutions. In this paper we propose a new general method to reduce the public key size by constructing quasi-cyclic Alternant codes over a relatively small field like \mathbbF28. We introduce a new method of hiding the structure of a quasi-cyclic GRS code. The idea is to start from a Reed-Solomon code in quasi-cyclic form defined over a large field. We then apply three transformations that preserve the quasi-cyclic feature. First, we randomly block shorten the RS code. Next, we transform it to get a Generalised Reed Solomon, and lastly we take the subfield subcode over a smaller field. We show that all existing structural attacks are infeasible. We also introduce a new NP-complete decision problem called quasi-cyclic syndrome decoding. This result suggests that decoding attack against our variant has little chance to be better than the general one against the classical McEliece cryptosystem. We propose a system with several sizes of parameters from 6,800 to 20,000 bits with a security ranging from 280 to 2120.

T. P. Berger, P.-L. Cayrel, P. Gaborit and A. Otmani
Proceedings of AfricaCrypt 2009, LNCS 5580, pages 77-97, Springer-Verlag, 2009
 Secure Implementation of the Stern Signature Scheme for Low-Resource Devices

In this paper we describe the first implementation on smartcard of the code-based authentication protocol proposed by Stern at Crypto’93 and we give a securization of the scheme against side channel attacks. On the whole, this provides a secure implementation of a very practical authentication (and possibly signature) scheme which is mostly attractive for light-weight cryptography.

P.-L. Cayrel, P. Gaborit and E. Prouff
Proceedings of CARDIS 2008, LNCS 5189, pages 191-205, Springer-Verlag, 2008