Polynomial Time Attack on Wild McEliece Over Quadratic Extensions

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 f...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2017-01, Vol.63 (1), p.404-427
Main Authors: Couvreur, Alain, Otmani, Ayoub, Tillich, Jean-Pierre
Format: Article
Language:English
Subjects:
Algebra
Complexity theory
Computer Science
cryptanalysis
Cryptography and Security
Decoding
Encryption
Fields (mathematics)
Goppa code distinguishing problem
Goppa codes
Information Theory
McEliece cryptosystem
Polynomials
Public key cryptography
Wild Goppa code
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2016.2574841