Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

G.R. Pellikaan; I. Marquez-Corbella; A. Couvreur

doi:10.1007/978-3-319-17296-5_13

Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

G.R. Pellikaan, I. Marquez-Corbella, A. Couvreur

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

Abstract

We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.

Original language	English
Title of host publication	Coding Theory and Applications
Subtitle of host publication	4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014
Editors	R. Pinto, P.R. Malonek, P. Vetton
Place of Publication	Dordrecht
Publisher	Springer
Pages	133-140
Number of pages	8
ISBN (Electronic)	978-3-319-17296-5
ISBN (Print)	978-3-319-17295-8
DOIs	https://doi.org/10.1007/978-3-319-17296-5_13
Publication status	Published - 2015
Event	4th International Castle Meeting Coding Theory and Applications (4ICMCTA) - Palmela, Portugal Duration: 15 Sept 2014 → 18 Sept 2014 Conference number: 4 http://icmcta.web.ua.pt/

Publication series

Name	CIM Series in Mathematical Sciences
Volume	3

Conference

Conference	4th International Castle Meeting Coding Theory and Applications (4ICMCTA)
Abbreviated title	ICMCTA
Country/Territory	Portugal
City	Palmela
Period	15/09/14 → 18/09/14
Internet address	http://icmcta.web.ua.pt/

Keywords

Algebraic geometry codes; Code-based cryptography; Schur products of codes; Distinguishers

Access to Document

10.1007/978-3-319-17296-5_13

Cite this

Pellikaan, G. R., Marquez-Corbella, I., & Couvreur, A. (2015). Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. In R. Pinto, P. R. Malonek, & P. Vetton (Eds.), Coding Theory and Applications: 4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014 (pp. 133-140). (CIM Series in Mathematical Sciences ; Vol. 3). Springer. https://doi.org/10.1007/978-3-319-17296-5_13

Pellikaan, G.R. ; Marquez-Corbella, I. ; Couvreur, A. / Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. Coding Theory and Applications: 4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014. editor / R. Pinto ; P.R. Malonek ; P. Vetton. Dordrecht : Springer, 2015. pp. 133-140 (CIM Series in Mathematical Sciences ).

@inproceedings{cc5f2157452a464fafd0096fcdb1ac32,

title = "Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes",

abstract = "We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.",

keywords = "Algebraic geometry codes; Code-based cryptography; Schur products of codes; Distinguishers ",

author = "G.R. Pellikaan and I. Marquez-Corbella and A. Couvreur",

year = "2015",

doi = "10.1007/978-3-319-17296-5_13",

language = "English",

isbn = "978-3-319-17295-8",

series = "CIM Series in Mathematical Sciences ",

publisher = "Springer",

pages = "133--140",

editor = "Pinto, {R. } and P.R. Malonek and P. Vetton",

booktitle = "Coding Theory and Applications",

address = "Germany",

note = "4th International Castle Meeting Coding Theory and Applications (4ICMCTA) , ICMCTA ; Conference date: 15-09-2014 Through 18-09-2014",

url = "http://icmcta.web.ua.pt/",

}

Pellikaan, GR, Marquez-Corbella, I & Couvreur, A 2015, Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. in R Pinto, PR Malonek & P Vetton (eds), Coding Theory and Applications: 4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014. CIM Series in Mathematical Sciences , vol. 3, Springer, Dordrecht, pp. 133-140, 4th International Castle Meeting Coding Theory and Applications (4ICMCTA) , Palmela, Portugal, 15/09/14. https://doi.org/10.1007/978-3-319-17296-5_13

Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. / Pellikaan, G.R.; Marquez-Corbella, I.; Couvreur, A.
Coding Theory and Applications: 4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014. ed. / R. Pinto; P.R. Malonek; P. Vetton. Dordrecht: Springer, 2015. p. 133-140 (CIM Series in Mathematical Sciences ; Vol. 3).

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

TY - GEN

T1 - Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

AU - Pellikaan, G.R.

AU - Marquez-Corbella, I.

AU - Couvreur, A.

N1 - Conference code: 4

PY - 2015

Y1 - 2015

N2 - We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.

AB - We give a polynomial time attack on the McEliece public key cryptosystem based on subcodes of algebraic geometry (AG) codes. The proposed attack reposes on the distinguishability of such codes from random codes using the Schur product. Wieschebrink treated the genus zero case a few years ago but his approach cannot be extent straightforwardly to other genera. We address this problem by introducing and using a new notion, which we call the t-closure of a code.

KW - Algebraic geometry codes; Code-based cryptography; Schur products of codes; Distinguishers

U2 - 10.1007/978-3-319-17296-5_13

DO - 10.1007/978-3-319-17296-5_13

M3 - Conference contribution

SN - 978-3-319-17295-8

T3 - CIM Series in Mathematical Sciences

SP - 133

EP - 140

BT - Coding Theory and Applications

A2 - Pinto, R.

A2 - Malonek, P.R.

A2 - Vetton, P.

PB - Springer

CY - Dordrecht

T2 - 4th International Castle Meeting Coding Theory and Applications (4ICMCTA)

Y2 - 15 September 2014 through 18 September 2014

ER -

Pellikaan GR, Marquez-Corbella I, Couvreur A. Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes. In Pinto R, Malonek PR, Vetton P, editors, Coding Theory and Applications: 4th International Castle Meeting, Palmela Castle, Portugal, September 15-18, 2014. Dordrecht: Springer. 2015. p. 133-140. (CIM Series in Mathematical Sciences ). doi: 10.1007/978-3-319-17296-5_13

Cryptanalysis of public-key cryptosystems that use subcodes of algebraic geometry codes

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this