Cryptanalysis of public-key cryptosystems based on algebraic geometry codes

I. Márquez-Corbella, E. Martínez-Moro, G.R. Pellikaan

Research output: Book/ReportReportAcademic

Abstract

This paper addresses the question of retrieving the triple (X ;P; E) from the algebraic geometry code CL(X ;P; E), where X is an algebraic curve over the finite field Fq, P is an n-tuple of Fq-rational points on X and E is a divisor on X . If deg(E) = 2g + 1 where g is the genus of X , then there is an embedding of X onto Y in the projective space of the linear series of the divisor E. Moreover, if deg(E) = 2g + 2, then I(Y), the vanishing ideal of Y, is generated by I2(Y), the homogeneous elements of degree two in I(Y). If n > 2 deg(E), then I2(Y) = I2(Q), where Q is the image of P under the map from X to Y. These two results imply that certain algebraic geometry codes are not secure if used in the McEliece public-key cryptosystem.
Original languageEnglish
Place of PublicationOberwolfach
PublisherMathematisches Forschungsinstitut Oberwolfach
Number of pages17
Publication statusPublished - 2012

Publication series

NameOberwolfach Preprints
VolumeOWP 2012-01

Fingerprint

Algebraic-geometry Codes
Public-key Cryptosystem
Cryptanalysis
Divisor
Linear Series
n-tuple
Rational Points
Algebraic curve
Projective Space
Galois field
Genus
Imply

Cite this

Márquez-Corbella, I., Martínez-Moro, E., & Pellikaan, G. R. (2012). Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. (Oberwolfach Preprints; Vol. OWP 2012-01). Oberwolfach: Mathematisches Forschungsinstitut Oberwolfach.
Márquez-Corbella, I. ; Martínez-Moro, E. ; Pellikaan, G.R. / Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2012. 17 p. (Oberwolfach Preprints).
@book{3e15bfe47b294b40bcaf06c7fa38114b,
title = "Cryptanalysis of public-key cryptosystems based on algebraic geometry codes",
abstract = "This paper addresses the question of retrieving the triple (X ;P; E) from the algebraic geometry code CL(X ;P; E), where X is an algebraic curve over the finite field Fq, P is an n-tuple of Fq-rational points on X and E is a divisor on X . If deg(E) = 2g + 1 where g is the genus of X , then there is an embedding of X onto Y in the projective space of the linear series of the divisor E. Moreover, if deg(E) = 2g + 2, then I(Y), the vanishing ideal of Y, is generated by I2(Y), the homogeneous elements of degree two in I(Y). If n > 2 deg(E), then I2(Y) = I2(Q), where Q is the image of P under the map from X to Y. These two results imply that certain algebraic geometry codes are not secure if used in the McEliece public-key cryptosystem.",
author = "I. M{\'a}rquez-Corbella and E. Mart{\'i}nez-Moro and G.R. Pellikaan",
year = "2012",
language = "English",
series = "Oberwolfach Preprints",
publisher = "Mathematisches Forschungsinstitut Oberwolfach",

}

Márquez-Corbella, I, Martínez-Moro, E & Pellikaan, GR 2012, Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. Oberwolfach Preprints, vol. OWP 2012-01, Mathematisches Forschungsinstitut Oberwolfach, Oberwolfach.

Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. / Márquez-Corbella, I.; Martínez-Moro, E.; Pellikaan, G.R.

Oberwolfach : Mathematisches Forschungsinstitut Oberwolfach, 2012. 17 p. (Oberwolfach Preprints; Vol. OWP 2012-01).

Research output: Book/ReportReportAcademic

TY - BOOK

T1 - Cryptanalysis of public-key cryptosystems based on algebraic geometry codes

AU - Márquez-Corbella, I.

AU - Martínez-Moro, E.

AU - Pellikaan, G.R.

PY - 2012

Y1 - 2012

N2 - This paper addresses the question of retrieving the triple (X ;P; E) from the algebraic geometry code CL(X ;P; E), where X is an algebraic curve over the finite field Fq, P is an n-tuple of Fq-rational points on X and E is a divisor on X . If deg(E) = 2g + 1 where g is the genus of X , then there is an embedding of X onto Y in the projective space of the linear series of the divisor E. Moreover, if deg(E) = 2g + 2, then I(Y), the vanishing ideal of Y, is generated by I2(Y), the homogeneous elements of degree two in I(Y). If n > 2 deg(E), then I2(Y) = I2(Q), where Q is the image of P under the map from X to Y. These two results imply that certain algebraic geometry codes are not secure if used in the McEliece public-key cryptosystem.

AB - This paper addresses the question of retrieving the triple (X ;P; E) from the algebraic geometry code CL(X ;P; E), where X is an algebraic curve over the finite field Fq, P is an n-tuple of Fq-rational points on X and E is a divisor on X . If deg(E) = 2g + 1 where g is the genus of X , then there is an embedding of X onto Y in the projective space of the linear series of the divisor E. Moreover, if deg(E) = 2g + 2, then I(Y), the vanishing ideal of Y, is generated by I2(Y), the homogeneous elements of degree two in I(Y). If n > 2 deg(E), then I2(Y) = I2(Q), where Q is the image of P under the map from X to Y. These two results imply that certain algebraic geometry codes are not secure if used in the McEliece public-key cryptosystem.

M3 - Report

T3 - Oberwolfach Preprints

BT - Cryptanalysis of public-key cryptosystems based on algebraic geometry codes

PB - Mathematisches Forschungsinstitut Oberwolfach

CY - Oberwolfach

ER -

Márquez-Corbella I, Martínez-Moro E, Pellikaan GR. Cryptanalysis of public-key cryptosystems based on algebraic geometry codes. Oberwolfach: Mathematisches Forschungsinstitut Oberwolfach, 2012. 17 p. (Oberwolfach Preprints).