Quasi-subfield polynomials and the elliptic curve discrete logarithm problem

Ming-Deh Huang; Michiel  Kosters; Christophe Petit; Sze Ling  Yeo; Yang Yun

doi:10.1515/jmc-2015-0049

Quasi-subfield polynomials and the elliptic curve discrete logarithm problem

Ming-Deh Huang, Michiel Kosters, Christophe Petit, Sze Ling Yeo, Yang Yun

Computer Science

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

1 Citation (Scopus)

149 Downloads (Pure)

Abstract

We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials.

Original language	English
Pages (from-to)	25-38
Journal	Journal of Mathematical Cryptology
Volume	14
Issue number	1
DOIs	https://doi.org/10.1515/jmc-2015-0049
Publication status	Published - 14 Jun 2020

Keywords

Cryptanalysis
Elliptic Curve Discrete Logarithm Problem
Finite fields

Access to Document

10.1515/jmc-2015-0049Licence: Creative Commons: Attribution (CC BY)

Huang_et_al_Quasi-subfield_polynomials_Journal_of_Mathematical_Cryptology_2020Final published version, 487 KBLicence: Creative Commons: Attribution (CC BY)

https://www.degruyter.com/view/journals/jmc/14/1/article-p25.xmlLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{34fd2e9d60824f37a23fb427a625af3e,

title = "Quasi-subfield polynomials and the elliptic curve discrete logarithm problem",

abstract = "We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials. ",

keywords = "Cryptanalysis, Elliptic Curve Discrete Logarithm Problem, Finite fields",

author = "Ming-Deh Huang and Michiel Kosters and Christophe Petit and Yeo, {Sze Ling} and Yang Yun",

year = "2020",

month = jun,

day = "14",

doi = "10.1515/jmc-2015-0049",

language = "English",

volume = "14",

pages = "25--38",

journal = "Journal of Mathematical Cryptology",

issn = "1862-2976",

publisher = "De Gruyter",

number = "1",

}

TY - JOUR

T1 - Quasi-subfield polynomials and the elliptic curve discrete logarithm problem

AU - Huang, Ming-Deh

AU - Kosters, Michiel

AU - Petit, Christophe

AU - Yeo, Sze Ling

AU - Yun, Yang

PY - 2020/6/14

Y1 - 2020/6/14

N2 - We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials.

AB - We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials.

KW - Cryptanalysis

KW - Elliptic Curve Discrete Logarithm Problem

KW - Finite fields

UR - http://www.scopus.com/inward/record.url?scp=85087414336&partnerID=8YFLogxK

U2 - 10.1515/jmc-2015-0049

DO - 10.1515/jmc-2015-0049

M3 - Article

SN - 1862-2976

VL - 14

SP - 25

EP - 38

JO - Journal of Mathematical Cryptology

JF - Journal of Mathematical Cryptology

IS - 1

ER -

Quasi-subfield polynomials and the elliptic curve discrete logarithm problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this