Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Gustavo Banegas; Valerie Gilchrist; Anaëlle Le Dévéhat; Benjamin Smith

doi:10.1007/978-3-031-44469-2_7

Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Gustavo Banegas
, Valerie Gilchrist
, Anaëlle Le Dévéhat
, Benjamin Smith

Qualcomm France SARL
Université Libre de Bruxelles
Laboratoire d'Informatique (LIX)

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

3 Citations (Scopus)

Abstract

Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu’s formulæ give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ; and the performance of Vélu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve Vélu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when.

Original language	English
Title of host publication	Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings
Editors	Abdelrahaman Aly, Mehdi Tibouchi
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	129-148
Number of pages	20
ISBN (Print)	9783031444685
DOIs	https://doi.org/10.1007/978-3-031-44469-2_7
Publication status	Published - 1 Jan 2023
Event	8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023 - Quito, Ecuador Duration: 3 Oct 2023 → 6 Oct 2023

Publication series

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

Conference

Conference	8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023
Country/Territory	Ecuador
City	Quito
Period	3/10/23 → 6/10/23

Access to Document

10.1007/978-3-031-44469-2_7

Cite this

Banegas, G., Gilchrist, V., Dévéhat, A. L., & Smith, B. (2023). Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields. In A. Aly, & M. Tibouchi (Eds.), Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings (pp. 129-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14168 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-44469-2_7

Banegas, Gustavo ; Gilchrist, Valerie ; Dévéhat, Anaëlle Le et al. / Fast and Frobenius : Rational Isogeny Evaluation over Finite Fields. Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings. editor / Abdelrahaman Aly ; Mehdi Tibouchi. Springer Science and Business Media Deutschland GmbH, 2023. pp. 129-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a1c5d420e4ef4522a6292c4d35cd44dd,

title = "Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields",

abstract = "Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on V{\'e}lu{\textquoteright}s formul{\ae} give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ; and the performance of V{\'e}lu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve V{\'e}lu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when.",

author = "Gustavo Banegas and Valerie Gilchrist and D{\'e}v{\'e}hat, \{Ana{\"e}lle Le\} and Benjamin Smith",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023 ; Conference date: 03-10-2023 Through 06-10-2023",

year = "2023",

month = jan,

day = "1",

doi = "10.1007/978-3-031-44469-2\_7",

language = "English",

isbn = "9783031444685",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "129--148",

editor = "Abdelrahaman Aly and Mehdi Tibouchi",

booktitle = "Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings",

}

Banegas, G, Gilchrist, V, Dévéhat, AL & Smith, B 2023, Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields. in A Aly & M Tibouchi (eds), Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14168 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 129-148, 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, 3/10/23. https://doi.org/10.1007/978-3-031-44469-2_7

Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields. / Banegas, Gustavo; Gilchrist, Valerie; Dévéhat, Anaëlle Le et al.
Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings. ed. / Abdelrahaman Aly; Mehdi Tibouchi. Springer Science and Business Media Deutschland GmbH, 2023. p. 129-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14168 LNCS).

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

TY - GEN

T1 - Fast and Frobenius

T2 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023

AU - Banegas, Gustavo

AU - Gilchrist, Valerie

AU - Dévéhat, Anaëlle Le

AU - Smith, Benjamin

PY - 2023/1/1

Y1 - 2023/1/1

N2 - Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu’s formulæ give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ; and the performance of Vélu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve Vélu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when.

AB - Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on Vélu’s formulæ give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ; and the performance of Vélu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve Vélu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when.

U2 - 10.1007/978-3-031-44469-2_7

DO - 10.1007/978-3-031-44469-2_7

M3 - Conference contribution

AN - SCOPUS:85174440194

SN - 9783031444685

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

SP - 129

EP - 148

BT - Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings

A2 - Aly, Abdelrahaman

A2 - Tibouchi, Mehdi

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 3 October 2023 through 6 October 2023

ER -

Banegas G, Gilchrist V, Dévéhat AL, Smith B. Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields. In Aly A, Tibouchi M, editors, Progress in Cryptology – LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 129-148. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-44469-2_7

Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this