Publications

Construction et optimisation des cryptosystèmes basés sur les codes correcteurs d’erreurs, 2008

Identity-based Identification and Signature Schemes using Error Correcting Codes

P.-L. Cayrel, P. Gaborit and M. Girault

Identity-Based Cryptography, chapter 8, 2009

4 - Improved zero-knowledge identification with lattices
P.-L. Cayrel, R. Lindner, M. Rückert and R. Silva
Tatracrypt Mountains Mathematical Publications, volume 53, pages 33-63, 2012
3 - Post-quantum cryptography : lattice identification schemes
R. Silva, P.-L. Cayrel and J. Buchmann
Publicationes Mathematicae Debrecen, volume 79/3-4, pages 729-748, 2011, impact factor : 0.65
2 - 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 : 3.009
1 - Quasi-cyclic codes as codes over rings of matrices
P.-L. Cayrel, C. Chabot and A. Necer
Finite Fields and their Applications, number 16(2), pages 100-115, 2010, impact factor : 0.737

19 - An improved threshold ring signature scheme based on error correcting codes

The concept of threshold ring signature in code-based cryptography was introduced by Aguilar et al. in [1]. Their proposal uses Stern’s identification scheme as basis. In this paper we construct a novel threshold ring signature scheme built on the q-SD identification scheme recently proposed by Cayrel et al. in [14]. Our proposed scheme benefits of a performance gain as a result of the reduction in the soundness error from 2/3 for Stern’s scheme to 1/2 per round for the q-SD scheme. Our threshold ring signature scheme uses random linear codes over the field Fq, secure in the random oracle model and its security relies on the hardness of an error-correcting codes problem (namely the q-ary syndrome decoding problem). In this paper we also provide implementation results of the Aguilar et al. scheme and our proposal, this is the first efficient implementation of this type of code-based schemes.

P.-L. Cayrel, S. M. El Yousfi Alaoui, G. Hoffmann and P. Véron
Proceedings of WAIFI 2012, LNCS 7369, pages 45-63, Springer-Verlag, 2012

18 - Improving the Performance of the SYND Stream Cipher

In 2007, Gaborit et al. proposed the stream cipher SYND as an improvement of the pseudo random number generator due to Fischer and Stern. This work shows how to improve considerably the efficiency the SYND cipher without using the so-called regular encoding and without compromising the security of the modified SYND stream cipher. Our proposal, called XSYND, uses a generic state transformation which is reducible to the Regular Syndrome Decoding problem (RSD), but has better computational characteristics than the regular encoding. A first implementation shows that XSYND runs much faster than SYND for a comparative security level (being more than three times faster for a security level of 128 bits, and more than 6 times faster for 400-bit security), though it is still only half as fast as AES in counter mode. Parallel computation may yet improve the speed of our proposal, and we leave it as future research to improve the efficiency of our implementation.

M. Meziani, G. Hoffmann and P.-L. Cayrel
Proceedings of AfricaCrypt 2012, LNCS 7374, pages 99-116, Springer-Verlag, 2012

17 - Extended Security Arguments for Signature Schemes
S. M. El Yousfi Alaoui, Ö. Dagdelen, P. Véron, D. Galindo and P.-L. Cayrel
Proceedings of AfricaCrypt 2012, LNCS 7374, pages 19-34, Springer-Verlag, 2012
16 - 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

15 - Broadcast attacks against code-based schemes
R. Niebuhr and P.-L. Cayrel
Proceedings of WEWoRC 2011, LNCS 7242, pages 1-17, Springer-Verlag, 2012
14 - Improved identity-based identification and signature schemes using Quasi-Dyadic Goppa codes

In this paper, we present an improved version of an identity-based identification scheme based on error-correcting codes. Our scheme combines the Courtois-Finiasz-Sendrier signature scheme using quasi-dyadic codes (QD-CFS) proposed in [2] and the identification scheme by Stern [18]. Following the construction proposed in [5], we obtain an identity-based identification scheme which has the advantage to reduce a public data size, the communication complexity and the signature length.

S. M. El Yousfi Alaoui, P.-L. Cayrel and M. Meziani
Proceedings of ISA 2011, CCIS 200, pages 146-155, Springer-Verlag, 2011
13 - S-FSB : An Improved Variant of the FSB Hash Family

In 2003, Augot et al. introduced the Fast Syndrome-Based hash family (in short FSB), which follows the generic construction of Merkle-Damgård and is based on the syndrome decoding problem. In 2007, Finiasz et al. proposed an improved version of FSB. In this work, we propose a new efficient hash function, which incorporates the ideas of FSB and the sponge construction introduced by Bertoni et al. Our proposal is up to 30 % faster in practice than FSB. Its security is related on the Regular Syndrome (RSD) Decoding problem, which is proven NP-complete.

M. Meziani, Ö. Dagdelen, P.-L. Cayrel and S. M. El Yousfi Alaoui
Proceedings of ISA 2011, CCIS 200, pages 132-145, Springer-Verlag, 2011
12 - 2SC : an Efficient Code-based Stream Cipher

In this article, we present a new code-based stream cipher called 2SC, based on the sponge construction. The security of the keystream generation of 2SC is reducible to the conjectured intractability of the Syndrome Decoding (SD) problem, which is believed to be hard in the average case. Our stream cipher compares favorably with other provably secure stream ciphers such as QUAD and SYND in terms of efficiency and storage. In particular, 2SC is much faster than both these stream ciphers, requiring shorter keys and initial vectors (IVs) in order to attain comparable security levels (the runtime in terms of clock cycles is actually halved compared to SYND for around 170 bits of security, whereas the key size is about 50 bits smaller).

M. Meziani, P.-L. Cayrel and S. M. El Yousfi Alaoui
Proceedings of ISA 2011, CCIS 200, pages 111-122, Springer-Verlag, 2011
11 - GPU Implementation of the Keccak Hash Function Family

Hash functions are one of the most important cryptographic primitives. Some of the currently employed hash functions like SHA-1 or MD5 are considered broken today. Therefore, in 2007 the US National Institute of Standards and Technology announced a competition for a new family of hash functions. Keccak is one of the five final candidates to be chosen as SHA-3 hash function standard. In this paper, we present an implementation of the Keccak hash function family on graphics cards, using NVIDIA’s CUDA framework. Our implementation allows to choose one function out of the hash function family and hash arbitrary documents. In addition we present the first ready-to-use implementation of the tree mode of Keccak which is even more suitable for parallelization.

P.-L. Cayrel, G. Hoffmann and M. Schneider
Proceedings of ISA 2011, CCIS 200, pages 33-42, Springer-Verlag, 2011
awarded of the Hex-Hot-Ticks prize for the most interesting implementation of Keccak on exotic platforms by the Keccak team.
10 - Recent progress in code-based cryptography

The last three years have witnessed tremendous progress in the understanding of code-based cryptography. One of its most promising applications is the design of cryptographic schemes with exceptionally strong security guarantees and other desirable properties. In contrast to number-theoretic problems typically used in cryptography, the underlying problems have so far resisted subexponential time attacks as well as quantum algorithms. This paper will survey the more recent developments.

P.-L. Cayrel, S. M. El Yousfi Alaoui, G. Hoffmann, M. Meziani and R. Niebuhr
Proceedings of ISA 2011, CCIS 200, pages 21-32, Springer-Verlag, 2011
9 - Quasi Dyadic CFS Signature Scheme

Courtois-Finiasz-Sendrier (CFS) digital signatures critically depend on the ability to efficiently find a decodable syndrome by random sampling the syndrome space, previously restricting the class of codes upon which they could be instantiated to generic binary Goppa codes. In this paper we show how to construct t-error correcting quasi-dyadic codes where the density of decodable syndromes is high, while also allowing for a reduction by a factor up to t in the key size.

P.S.L.M. Barreto, P.-L. Cayrel, R. Misoczki and R. Niebuhr
Proceedings of InsCrypt 2010, LNCS 6584, pages 336-349, Springer-Verlag, 2010
8 - 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
7 - Improved Zero-knowledge Identification with Lattices

Zero-knowledge identification schemes solve the problem of authenticating one party to another via an insecure channel without disclosing any additional information that might be used by an impersonator. In this paper we propose a scheme whose security relies on the existence of a commitment scheme and on the hardness of worst-case lattice problems. We adapt a code-based identification scheme devised by Cayrel and Véron, which constitutes an improvement of Stern’s construction. Our solution sports analogous improvements over the lattice adaption of Stern’s scheme which Kawachi et al. presented at ASIACRYPT 2008. Specifically, due to a smaller cheating probability close to 1/2 and a similar communication cost, any desired level of security will be achieved in fewer rounds. Compared to Lyubashevsky’s scheme presented at ASIACRYPT 2009, our proposal, like Kawachi’s, offers a much milder security assumption : namely, the hardness of SIS for trinary solutions. The same assumption was used for the SWIFFT hash function, which is secure for much smaller parameters than those proposed by Lyubashevsky.

P.-L. Cayrel, R. Lindner, M. Rückert and R. Silva
Proceedings of ProvSec 2010, LNCS 6402, pages 1-16, Springer-Verlag, 2010
6 - A Lattice-Based Threshold Ring Signature Scheme

In this article, we propose a new lattice-based threshold ring signature scheme, modifying Aguilar’s code-based solution to use the short integer solution (SIS) problem as security assumption, instead of the syndrome decoding (SD) problem. By applying the CLRS identification scheme, we are also able to have a performance gain as result of the reduction in the soundness error to 1/2 per round. Such gain is also maintained through the application of the Fiat-Shamir heuristics to derive signatures from our identification scheme. From security perspective we also have improvements, because our scheme exhibits a worst-case to average-case reduction typical of lattice-based cryptosystems. This gives us confidence that a random choice of parameters results in a system that is hard to break, in average.

P.-L. Cayrel, R. Lindner, M. Rückert and R. Silva
Proceedings of LatinCrypt 2010, LNCS 6212, pages 255-272, Springer-Verlag, 2010
5 - Post-Quantum Cryptography : Code-based Signatures

This survey provides a comparative overview of code-based signature schemes with respect to security and performance. Furthermore, we explicitly describe serveral code-based signature schemes with additional properties such as identity-based, threshold ring and blind signatures.

P.-L. Cayrel and M. Meziani
Proceedings of ISA 2010, LNCS 6059, pages 82-99, Springer-Verlag, 2010
4 - 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
3 - A New Efficient Threshold Ring Signature Scheme based on Coding Theory

Ring signatures were introduced by Rivest, Shamir and Tauman in 2001. Bresson, Stern and Szydlo extended the ring signature concept to t-out-of-N threshold ring signatures in 2002. We present in this paper a generalization of Stern’s code based authentication (and signature) scheme to the case of t-out-of-N threshold ring signature. The size of our signature is in O(N) and does not depend on t. Our protocol is anonymous and secure in the random oracle model, it has a very short public key and has a complexity in O(N) . This protocol is the first efficient code-based ring signature scheme and the first code-based threshold ring signature scheme. Moreover it has a better complexity than number-theory based schemes which have a complexity in O(Nt) .

C. Aguilar Melchor, P.-L. Cayrel and P. Gaborit
Proceedings of PQCrypto 2008, LNCS 5299, pages 1-16, Springer-Verlag, 2008
2 - 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
1 - On Kabatianskii-Krouk-Smeets Signatures

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on random error-correcting codes. In this paper we investigate the security and the efficiency of their proposal. We show that a passive attacker who may intercept just a few signatures can recover the private key. We give precisely the number of signatures required to achieve this goal. This enables us to prove that all the schemes given in the original paper can be broken with at most 20 signatures. We improve the efficiency of these schemes by firstly providing parameters that enable to sign about 40 messages, and secondly, by describing a way to extend these few-times signatures into classical multi-time signatures. We finally study their key sizes and a mean to reduce them by means of more compact matrices.

P.-L. Cayrel, A. Otmani and D. Vergnaud
Proceedings of WAIFI 2007, LNCS 4547, pages 237-251, Springer-Verlag, 2007

2 - A Lattice-Based Batch Identification Scheme
R. Silva, P.-L. Cayrel and R. Lindner
Proceedings of ITW 2011, IEEE , pages 215 - 219, 2011
1 - McEliece/Niederreiter PKC : sensitivity to fault injection
P.-L. Cayrel and P. Dusart
Proceedings of FEAS 2010, IEEE, pages 1 - 6, 2010

10 - Lattice-based Zero-knowledge Identification with Low Communication Cost
R. Silva, P.-L. Cayrel and R. Lindner
Proceedings of SBSEG 2011
9 - Hash Functions Based on Coding Theory
M. Meziani, S. M. El Yousfi Alaoui and P.-L. Cayrel
Proceedings of WCCCS 2011, pages 32-37
8 - Improving the efficiency of GBA against certain structured cryptosystems
R.Niebuhr, P.-L. Cayrel and J. Buchmann
Proceedings of WCC 2011, pages 163-172
7 - Attacking code/lattice-based cryptosystems using Partial Knowledge
R.Niebuhr, P.-L. Cayrel, S. Bulygin and J. Buchmann
to appear in the short paper proceedings of InsCrypt 2010, Science Press of China
6 - Multi-Signature Scheme based on Coding Theory
M. Meziani and P.-L. Cayrel
Proceedings of ICCCIS 2010, pages 186-192
5 - Dual Construction of Stern-based Signature Schemes
P.-L. Cayrel and S. M. El Yousfi Alaoui
Proceedings of ICCCIS 2010, pages 369-374
4 - Side channels attacks in code-based cryptography
P.-L. Cayrel and F. Strenzke
Proceedings of COSADE 2010, pages 24-28
3 - New results on the Stern identification and signature scheme
P.-L. Cayrel
Bulletin of the Transilvania University of Brasov - Vol 2(51) - 2009 Series III : Mathematics, Informatics, Physics, pages 3-10
2 - Improved algorithm to find equations for algebraic attacks for combiners with memory
F. Armknecht, P.-L. Cayrel, P. Gaborit and O. Ruatta
Proceedings of BFCA 2007, pages 81-98
1 - Identity-based identification and signature schemes using correcting codes
P.-L. Cayrel, P. Gaborit and M. Girault
Proceedings of WCC 2007, pages 69-78

6 - Efficient implementation of code-based identification/signatures schemes

In this paper we present efficient implementations of several code-based identification schemes, namely the Stern scheme, the Véron scheme and the Cayrel-Véron-El Yousfi scheme. For a security of 80 bits, we obtain a signature in respectively 1.048 ms, 0.987 ms and 0.594 ms.

P.-L. Cayrel, S. M. El Yousfi Alaoui, Felix Günther, Gerhard Hoffmann and Holger Rother
Proceedings of WEWoRC 2011

5 - An improved threshold ring signature scheme based on error correcting codes
P.-L. Cayrel and S. M. El Yousfi Alaoui
accepted at WISSec 2010 (not presented)

4 - Implementation of the McEliece scheme based on compact (flexible) quasi-dyadic public keys
P.-L. Cayrel and G. Hoffman
accepted at eSmart 2010 (not presented)
3 - On lower bounds for Information Set Decoding over Fq
R. Niebuhr, P.-L. Cayrel, S. Bulygin and J. Buchmann
Proceedings of SCC 2010, pages 143-157
2 - Fault injection’s sensitivity of the McEliece PKC
P.-L. Cayrel and P. Dusart
Proceedings of WEWoRC 2009, pages 84-88
1 - New results on the Stern identification and signature scheme
P.-L. Cayrel
Proceedings of Colloque Franco Roumain de Mathématiques Appliquées page 53

9 - A zero-knowledge identification scheme based on the q-ary Syndrome Decoding problem
P.-L. Cayrel, P. Véron and S. M. El Yousfi Alaoui
KRYPTOTAG 2010
8 - Quasi Dyadic CFS Signature Scheme
P.S.L.M. Barreto, P.-L. Cayrel, R. Misoczki and R. Niebuhr
KRYPTOTAG 2010
7 - Algorithme de décodage (Reed-Muller)
P.-L. Cayrel and R. Fourquet
MAJECSTIC 2009, page 11
6 - Nouveaux résultats en cryptographie basée sur les codes correcteurs d’erreurs
P.-L. Cayrel
MAJECSTIC 2009, page 10
5 - Code-Based Signature Schemes
P.-L. Cayrel
KWE 2008, pages 23-27
4 - Dis-moi ce que tu consommes, je te dirai qui tu es
P.-L. Cayrel and N. El Mrabet
MAJECSTIC 2008
3 - Schémas de signature prouvés sûrs fondés sur la théorie des codes correcteurs d’erreurs
P.-L. Cayrel and L. Dallot
MAJECSTIC 2008
2 - Attaques algébriques
M. Barbier and P.-L. Cayrel
MAJECSTIC 2008

1 - Algorithme amélioré de recherche d’équations dans le cas d’attaques algébriques des registres avec mémoire
F. Armknecht, P.-L. Cayrel, P. Gaborit and O. Ruatta
MAJECSTIC 2007, pages 239-243

1 - Extended Security Arguments for (Ring) Signature Schemes
S. M. El Yousfi Alaoui, Ö. Dagdelen, P. Véron, D. Galindo and P.-L. Cayrel
Cryptology ePrint Archive : Report 2012/068