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

Alain Couvreur; Irene Márquez-Corbella; Ruud Pellikaan

doi:10.1109/ISIT.2014.6875072

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

Alain Couvreur
, Irene Márquez-Corbella
, Ruud Pellikaan

Technical University of Eindhoven

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

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⁴) operations in F_q, where n denotes the code length. Compared to previous attacks, the present one 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 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	1446-1450
Number of pages	5
ISBN (Print)	9781479951864
DOIs	https://doi.org/10.1109/ISIT.2014.6875072
Publication status	Published - 1 Jan 2014
Event	2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States Duration: 29 Jun 2014 → 4 Jul 2014

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Conference

Conference	2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/Territory	United States
City	Honolulu, HI
Period	29/06/14 → 4/07/14

Access to Document

10.1109/ISIT.2014.6875072

Cite this

Couvreur, A., Márquez-Corbella, I., & Pellikaan, R. (2014). A polynomial time attack against algebraic geometry code based public key cryptosystems. In 2014 IEEE International Symposium on Information Theory, ISIT 2014 (pp. 1446-1450). Article 6875072 (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2014.6875072

@inproceedings{1022531615a940a9b66ff0a5c0126317,

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(n4) operations in Fq, where n denotes the code length. Compared to previous attacks, the present one allows to recover a decoding algorithm for the public key even for codes from high genus curves.",

author = "Alain Couvreur and Irene M{\'a}rquez-Corbella and Ruud Pellikaan",

year = "2014",

month = jan,

day = "1",

doi = "10.1109/ISIT.2014.6875072",

language = "English",

isbn = "9781479951864",

series = "IEEE International Symposium on Information Theory - Proceedings",

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

pages = "1446--1450",

booktitle = "2014 IEEE International Symposium on Information Theory, ISIT 2014",

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

}

Couvreur, A, Márquez-Corbella, I & Pellikaan, R 2014, A polynomial time attack against algebraic geometry code based public key cryptosystems. in 2014 IEEE International Symposium on Information Theory, ISIT 2014., 6875072, IEEE International Symposium on Information Theory - Proceedings, Institute of Electrical and Electronics Engineers Inc., pp. 1446-1450, 2014 IEEE International Symposium on Information Theory, ISIT 2014, Honolulu, HI, United States, 29/06/14. https://doi.org/10.1109/ISIT.2014.6875072

A polynomial time attack against algebraic geometry code based public key cryptosystems. / Couvreur, Alain; Márquez-Corbella, Irene; Pellikaan, Ruud.
2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc., 2014. p. 1446-1450 6875072 (IEEE International Symposium on Information Theory - Proceedings).

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

TY - GEN

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

AU - Couvreur, Alain

AU - Márquez-Corbella, Irene

AU - Pellikaan, Ruud

PY - 2014/1/1

Y1 - 2014/1/1

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(n4) operations in Fq, where n denotes the code length. Compared to previous attacks, the present one 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(n4) operations in Fq, where n denotes the code length. Compared to previous attacks, the present one 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

AN - SCOPUS:84906539573

SN - 9781479951864

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1446

EP - 1450

BT - 2014 IEEE International Symposium on Information Theory, ISIT 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE International Symposium on Information Theory, ISIT 2014

Y2 - 29 June 2014 through 4 July 2014

ER -

Couvreur A, Márquez-Corbella I, Pellikaan R. A polynomial time attack against algebraic geometry code based public key cryptosystems. In 2014 IEEE International Symposium on Information Theory, ISIT 2014. Institute of Electrical and Electronics Engineers Inc. 2014. p. 1446-1450. 6875072. (IEEE International Symposium on Information Theory - Proceedings). doi: 10.1109/ISIT.2014.6875072

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this