On index calculus algorithms for subfield curves

Steven D. Galbraith; Robert Granger; Simon-Philipp Merz; Christophe Petit

doi:10.1007/978-3-030-81652-0_5

On index calculus algorithms for subfield curves

Steven D. Galbraith, Robert Granger, Simon-Philipp Merz, Christophe Petit

Computer Science

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

183 Downloads (Pure)

Abstract

In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over F_q with ECDLP in Fqn. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the q-power Frobenius automorphism of the field Fqn, reducing the number of polynomial systems that need to be solved. A reduction by a factor of 1/n is the best one could hope for. We show how to choose factor bases to achieve this, while simultaneously accelerating the linear algebra step of the index calculus method for Koblitz curves by a factor n². Furthermore, we show how to use the Frobenius endomorphism to improve symmetry breaking for Koblitz curves. We provide constructions of factor bases with the desired properties, and we study their impact on the polynomial system solving costs experimentally.

Original language	English
Title of host publication	Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers
Editors	Orr Dunkelman, Michael J. Jacobson, Jr., Colin O’Flynn
Publisher	Springer
Pages	115-138
Number of pages	24
ISBN (Electronic)	9783030816520
ISBN (Print)	9783030816513
DOIs	https://doi.org/10.1007/978-3-030-81652-0_5
Publication status	Published - 21 Jul 2021
Event	27th International Conference on Selected Areas in Cryptography, SAC 2020 - Virtual, Online Duration: 21 Oct 2020 → 23 Oct 2020

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12804
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Conference on Selected Areas in Cryptography, SAC 2020
City	Virtual, Online
Period	21/10/20 → 23/10/20

Bibliographical note

Funding Information:
Acknowledgements. We thank Jean-Marc Couveignes and Reynald Lercier for their work on Galois invariant smoothness bases [2] and helpful conversations about the topic. Furthermore, we would like to thank the anonymous reviewers for their helpful comments on the submitted manuscript of this paper. Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Simon-Philipp Merz was supported by the EPSRC grant EP/P009301/1.

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-81652-0_5

GalbraithS2021Index
The final authenticated version is available online at: https://doi.org/10.1007/978-3-030-81652-0_5
Accepted author manuscript, 520 KBLicence: None: All rights reserved

Cite this

Galbraith, S. D., Granger, R., Merz, S.-P., & Petit, C. (2021). On index calculus algorithms for subfield curves. In O. Dunkelman, M. J. Jacobson, Jr., & C. O’Flynn (Eds.), Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers (pp. 115-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12804). Springer. https://doi.org/10.1007/978-3-030-81652-0_5

Galbraith, Steven D. ; Granger, Robert ; Merz, Simon-Philipp et al. / On index calculus algorithms for subfield curves. Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers. editor / Orr Dunkelman ; Michael J. Jacobson, Jr. ; Colin O’Flynn. Springer, 2021. pp. 115-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0247769078b94ddbbc6d77937e25bfc6,

title = "On index calculus algorithms for subfield curves",

abstract = "In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over Fq with ECDLP in Fqn. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the q-power Frobenius automorphism of the field Fqn, reducing the number of polynomial systems that need to be solved. A reduction by a factor of 1/n is the best one could hope for. We show how to choose factor bases to achieve this, while simultaneously accelerating the linear algebra step of the index calculus method for Koblitz curves by a factor n2. Furthermore, we show how to use the Frobenius endomorphism to improve symmetry breaking for Koblitz curves. We provide constructions of factor bases with the desired properties, and we study their impact on the polynomial system solving costs experimentally.",

author = "Galbraith, {Steven D.} and Robert Granger and Simon-Philipp Merz and Christophe Petit",

note = "Funding Information: Acknowledgements. We thank Jean-Marc Couveignes and Reynald Lercier for their work on Galois invariant smoothness bases [2] and helpful conversations about the topic. Furthermore, we would like to thank the anonymous reviewers for their helpful comments on the submitted manuscript of this paper. Christophe Petit{\textquoteright}s work was supported by EPSRC grant EP/S01361X/1. Simon-Philipp Merz was supported by the EPSRC grant EP/P009301/1. Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 27th International Conference on Selected Areas in Cryptography, SAC 2020 ; Conference date: 21-10-2020 Through 23-10-2020",

year = "2021",

month = jul,

day = "21",

doi = "10.1007/978-3-030-81652-0_5",

language = "English",

isbn = "9783030816513",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "115--138",

editor = "Orr Dunkelman and {Jacobson, Jr.}, {Michael J.} and Colin O{\textquoteright}Flynn",

booktitle = "Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers",

}

Galbraith, SD, Granger, R, Merz, S-P & Petit, C 2021, On index calculus algorithms for subfield curves. in O Dunkelman, MJ Jacobson, Jr. & C O’Flynn (eds), Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12804, Springer, pp. 115-138, 27th International Conference on Selected Areas in Cryptography, SAC 2020, Virtual, Online, 21/10/20. https://doi.org/10.1007/978-3-030-81652-0_5

On index calculus algorithms for subfield curves. / Galbraith, Steven D.; Granger, Robert; Merz, Simon-Philipp et al.
Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers. ed. / Orr Dunkelman; Michael J. Jacobson, Jr.; Colin O’Flynn. Springer, 2021. p. 115-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12804).

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

TY - GEN

T1 - On index calculus algorithms for subfield curves

AU - Galbraith, Steven D.

AU - Granger, Robert

AU - Merz, Simon-Philipp

AU - Petit, Christophe

N1 - Funding Information: Acknowledgements. We thank Jean-Marc Couveignes and Reynald Lercier for their work on Galois invariant smoothness bases [2] and helpful conversations about the topic. Furthermore, we would like to thank the anonymous reviewers for their helpful comments on the submitted manuscript of this paper. Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Simon-Philipp Merz was supported by the EPSRC grant EP/P009301/1. Publisher Copyright: © 2021, Springer Nature Switzerland AG.

PY - 2021/7/21

Y1 - 2021/7/21

N2 - In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over Fq with ECDLP in Fqn. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the q-power Frobenius automorphism of the field Fqn, reducing the number of polynomial systems that need to be solved. A reduction by a factor of 1/n is the best one could hope for. We show how to choose factor bases to achieve this, while simultaneously accelerating the linear algebra step of the index calculus method for Koblitz curves by a factor n2. Furthermore, we show how to use the Frobenius endomorphism to improve symmetry breaking for Koblitz curves. We provide constructions of factor bases with the desired properties, and we study their impact on the polynomial system solving costs experimentally.

AB - In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over Fq with ECDLP in Fqn. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the q-power Frobenius automorphism of the field Fqn, reducing the number of polynomial systems that need to be solved. A reduction by a factor of 1/n is the best one could hope for. We show how to choose factor bases to achieve this, while simultaneously accelerating the linear algebra step of the index calculus method for Koblitz curves by a factor n2. Furthermore, we show how to use the Frobenius endomorphism to improve symmetry breaking for Koblitz curves. We provide constructions of factor bases with the desired properties, and we study their impact on the polynomial system solving costs experimentally.

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

UR - https://eprint.iacr.org/2020/1315

U2 - 10.1007/978-3-030-81652-0_5

DO - 10.1007/978-3-030-81652-0_5

M3 - Conference contribution

AN - SCOPUS:85113581267

SN - 9783030816513

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 138

BT - Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers

A2 - Dunkelman, Orr

A2 - Jacobson, Jr., Michael J.

A2 - O’Flynn, Colin

PB - Springer

T2 - 27th International Conference on Selected Areas in Cryptography, SAC 2020

Y2 - 21 October 2020 through 23 October 2020

ER -

Galbraith SD, Granger R, Merz SP, Petit C. On index calculus algorithms for subfield curves. In Dunkelman O, Jacobson, Jr. MJ, O’Flynn C, editors, Selected Areas in Cryptography - 27th International Conference, 2020, Revised Selected Papers. Springer. 2021. p. 115-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-81652-0_5

On index calculus algorithms for subfield curves

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this