Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

Alain Couvreur; Ayoub Otmani; Jean-Pierre Tillich

doi:10.1109/TIT.2016.2574841

Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

Alain Couvreur ^{1, 2} Ayoub Otmani ³ Jean-Pierre Tillich ⁴

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

Domain :

Computer Science [cs] / Information Theory [cs.IT]

Computer Science [cs] / Cryptography and Security [cs.CR]

Complete list of metadatas

Cited literature [55 references] Display Hide Download

https://hal.inria.fr/hal-01661935
Contributor : Jean-Pierre Tillich <>
Submitted on : Tuesday, December 12, 2017 - 4:13:12 PM
Last modification on : Thursday, November 21, 2019 - 6:32:53 PM

article.pdf

Files produced by the author(s)

Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

File

Identifiers

Collections

Citation

Export

Metrics

657

206

Contact

Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

File

Identifiers

Collections

Citation

Export

Share

Metrics

657

206

Contact