Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups

Abstract : The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then \textit{symmetries} allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking {\it quasi-cyclic} (\QC{}) or {\it quasi-dyadic} (\QD{}) alternant/Goppa codes. We show that the use of such \textit{symmetric} alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called \textit{folding} that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold: the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (\textit{resp}. Goppa) code provides the dual of an alternant (\textit{resp}. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D{\"{u}}r). This enables not only to present a unified view but also to generalize the construction of \QC{}, \QD{} and even \textit{quasi-monoidic} (\QM{}) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2016, 62 (1), pp.184-198. 〈10.1109/TIT.2015.2493539〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00992389
Contributeur : Ludovic Perret <>
Soumis le : samedi 17 mai 2014 - 14:17:14
Dernière modification le : lundi 1 octobre 2018 - 09:58:08
Document(s) archivé(s) le : dimanche 17 août 2014 - 10:40:39

Fichier

folded_it.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, Frédéric De Portzamparc, Jean-Pierre Tillich. Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2016, 62 (1), pp.184-198. 〈10.1109/TIT.2015.2493539〉. 〈hal-00992389〉

Partager

Métriques

Consultations de la notice

445

Téléchargements de fichiers

120