Skip to Main content Skip to Navigation
Journal articles

Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

Alain Couvreur 1, 2 Ayoub Otmani 3 Jean-Pierre Tillich 4
1 LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
2 GRACE - Geometry, arithmetic, algorithms, codes and encryption
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
3 LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
4 SECRET - Security, Cryptology and Transmissions
Inria de Paris
Abstract : We present a polynomial-time structural attack against the McEliece system based on Wild Goppa codes defined over a quadratic finite field extension. We show that such codes can be efficiently distinguished from random codes. The attack uses this property to compute a filtration, that is to say, a family of nested subcodes which will reveal their secret algebraic description.
Keywords : Index Terms—McEliece cryptosystem cryptanalysis Wild Goppa code McEliece cryptosystem Goppa Code Distinguishing problem
Document type :
Journal articles
Complete list of metadata

Cited literature [55 references]  Display  Hide  Download
https://hal.inria.fr/hal-01661935
Contributor : Jean-Pierre Tillich Connect in order to contact the contributor
Submitted on : Tuesday, December 12, 2017 - 4:13:12 PM
Last modification on : Thursday, January 7, 2021 - 3:38:03 PM

File

Vignette du document
article.pdf
Files produced by the author(s)

Identifiers

Collections

CNRS | LIX | LITIS | COMUE-NORMANDIE | X-LIX | INRIA | X | INSA-ROUEN | UNIROUEN | UNILEHAVRE | X-DEP-INFO | INSA-GROUPE

Citation

Alain Couvreur, Ayoub Otmani, Jean-Pierre Tillich. Polynomial Time Attack on Wild McEliece Over Quadratic Extensions. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2017, 63 (1), pp.404--427. ⟨10.1109/TIT.2016.2574841⟩. ⟨hal-01661935⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

791

Files downloads

393

 

Contact                    Legal Notice                    Personal Data