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
, Ayoub Otmani
, Jean Pierre Tillich

Normandie Université
LITIS - Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes
INRIA Institut National de Recherche en Informatique et en Automatique

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	7496988
Pages (from-to)	404-427
Number of pages	24
Journal	IEEE Transactions on Information Theory
Volume	63
Issue number	1
DOIs	https://doi.org/10.1109/TIT.2016.2574841
Publication status	Published - 1 Jan 2017

Keywords

Goppa code distinguishing problem
McEliece cryptosystem
Wild Goppa code
cryptanalysis

Access to Document

10.1109/TIT.2016.2574841

Cite this

@article{9ee02ed2fd764b0c98d9f5826702b70d,

title = "Polynomial time attack on wild McEliece over quadratic extensions",

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 = "Goppa code distinguishing problem, McEliece cryptosystem, Wild Goppa code, cryptanalysis",

author = "Alain Couvreur and Ayoub Otmani and Tillich, \{Jean Pierre\}",

note = "Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",

year = "2017",

month = jan,

day = "1",

doi = "10.1109/TIT.2016.2574841",

language = "English",

volume = "63",

pages = "404--427",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - Polynomial time attack on wild McEliece over quadratic extensions

AU - Couvreur, Alain

AU - Otmani, Ayoub

AU - Tillich, Jean Pierre

PY - 2017/1/1

Y1 - 2017/1/1

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

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

KW - Goppa code distinguishing problem

KW - McEliece cryptosystem

KW - Wild Goppa code

KW - cryptanalysis

U2 - 10.1109/TIT.2016.2574841

DO - 10.1109/TIT.2016.2574841

M3 - Article

AN - SCOPUS:85008481819

SN - 0018-9448

VL - 63

SP - 404

EP - 427

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 1

M1 - 7496988

ER -

Polynomial time attack on wild McEliece over quadratic extensions

Abstract

Keywords

Access to Document

Fingerprint

Cite this