Skip to Main content Skip to Navigation

Étude de la sécurité de certaines clés compactes pour le schéma de McEliece utilisant des codes géométriques

Elise Barelli 1
1 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the invariant code. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism σ. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the Schur product and the conductor of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters.
Complete list of metadatas

Cited literature [113 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Tuesday, January 15, 2019 - 4:54:11 PM
Last modification on : Tuesday, January 19, 2021 - 3:30:45 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01982502, version 1



Elise Barelli. Étude de la sécurité de certaines clés compactes pour le schéma de McEliece utilisant des codes géométriques. Cryptography and Security [cs.CR]. Université Paris Saclay (COmUE), 2018. English. ⟨NNT : 2018SACLX095⟩. ⟨tel-01982502⟩



Record views


Files downloads