A polynomial time attack against algebraic geometry code based public key cryptosystems

A. Couvreur; I. Márquez-Corbella; G.R. Pellikaan

doi:10.1109/ISIT.2014.6875072

A polynomial time attack against algebraic geometry code based public key cryptosystems

A. Couvreur, I. Márquez-Corbella, G.R. Pellikaan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

22 Citations (Scopus)

Abstract

We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.

Original language	English
Title of host publication	2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014)
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	1446-1450
ISBN (Print)	978-1-4799-5186-4
DOIs	https://doi.org/10.1109/ISIT.2014.6875072
Publication status	Published - 2014
Event	conference; 2014 IEEE International Symposium on Information Theory; 2014-06-29; 2014-07-04 - Duration: 29 Jun 2014 → 4 Jul 2014

Conference

Conference	conference; 2014 IEEE International Symposium on Information Theory; 2014-06-29; 2014-07-04
Period	29/06/14 → 4/07/14
Other	2014 IEEE International Symposium on Information Theory

Access to Document

10.1109/ISIT.2014.6875072

Cite this

Couvreur, A., Márquez-Corbella, I., & Pellikaan, G. R. (2014). A polynomial time attack against algebraic geometry code based public key cryptosystems. In 2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014) (pp. 1446-1450). Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ISIT.2014.6875072

@inproceedings{aacbfbf12efa48219fef97c4be3a61e5,

title = "A polynomial time attack against algebraic geometry code based public key cryptosystems",

abstract = "We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.",

author = "A. Couvreur and I. M{\'a}rquez-Corbella and G.R. Pellikaan",

year = "2014",

doi = "10.1109/ISIT.2014.6875072",

language = "English",

isbn = "978-1-4799-5186-4",

pages = "1446--1450",

booktitle = "2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "conference; 2014 IEEE International Symposium on Information Theory; 2014-06-29; 2014-07-04 ; Conference date: 29-06-2014 Through 04-07-2014",

}

Couvreur, A, Márquez-Corbella, I & Pellikaan, GR 2014, A polynomial time attack against algebraic geometry code based public key cryptosystems. in 2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014). Institute of Electrical and Electronics Engineers, Piscataway, pp. 1446-1450, conference; 2014 IEEE International Symposium on Information Theory; 2014-06-29; 2014-07-04, 29/06/14. https://doi.org/10.1109/ISIT.2014.6875072

A polynomial time attack against algebraic geometry code based public key cryptosystems. / Couvreur, A.; Márquez-Corbella, I.; Pellikaan, G.R.

2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014). Piscataway : Institute of Electrical and Electronics Engineers, 2014. p. 1446-1450.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A polynomial time attack against algebraic geometry code based public key cryptosystems

AU - Couvreur, A.

AU - Márquez-Corbella, I.

AU - Pellikaan, G.R.

PY - 2014

Y1 - 2014

N2 - We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.

AB - We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.

U2 - 10.1109/ISIT.2014.6875072

DO - 10.1109/ISIT.2014.6875072

M3 - Conference contribution

SN - 978-1-4799-5186-4

SP - 1446

EP - 1450

BT - 2014 IEEE International Symposium on Information Theory (ISIT'14, Honolulu HI, USA, June 29-July 4, 2014)

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - conference; 2014 IEEE International Symposium on Information Theory; 2014-06-29; 2014-07-04

Y2 - 29 June 2014 through 4 July 2014

ER -

A polynomial time attack against algebraic geometry code based public key cryptosystems

Abstract

Conference

Access to Document

Fingerprint

Cite this