An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography

Pierrick  Dartois; Luciano Maino; Giacomo  Pope; Damien  Robert

doi:10.1007/978-981-96-0891-1_10

An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography

Pierrick Dartois, Luciano Maino, Giacomo Pope, Damien Robert

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

1 Citation (Scopus)

Abstract

In this paper, we describe an algorithm to compute chains of (2,2)-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.

We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2024
Subtitle of host publication	30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III
Editors	Kai-Min Chung, Yu Sasaki
Publisher	Springer, Singapore
Pages	304-338
Number of pages	35
ISBN (Electronic)	9789819608911
ISBN (Print)	9789819608904
DOIs	https://doi.org/10.1007/978-981-96-0891-1_10
Publication status	Published - 12 Dec 2024
Event	ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security - Kolkata, India Duration: 9 Dec 2024 → 13 Dec 2024 https://asiacrypt.iacr.org/2024/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	15486
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	ASIACRYPT 2024
Country/Territory	India
City	Kolkata
Period	9/12/24 → 13/12/24
Internet address	https://asiacrypt.iacr.org/2024/

Bibliographical note

Publisher Copyright:
© 2025 International Association for Cryptologic Research.

Access to Document

10.1007/978-981-96-0891-1_10

Full-text PDF (accepted manuscript)
This is the accepted author manuscript (AAM) of the article which has been made Open Access under the University of Bristol's Scholarly Works Policy. The final published version (Version of Record) can be found on the publisher's website. The copyright of any third-party content, such as images, remains with the copyright holder.
Accepted author manuscript, 692 KBLicence: CC BY

Handle.net

Persistent link

Cite this

Dartois, P., Maino, L., Pope, G., & Robert, D. (2024). An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography. In K.-M. Chung, & Y. Sasaki (Eds.), Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III (pp. 304-338). (Lecture Notes in Computer Science; Vol. 15486). Springer, Singapore. https://doi.org/10.1007/978-981-96-0891-1_10

Dartois, Pierrick ; Maino, Luciano ; Pope, Giacomo et al. / An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography. Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. editor / Kai-Min Chung ; Yu Sasaki. Springer, Singapore, 2024. pp. 304-338 (Lecture Notes in Computer Science).

@inproceedings{ce624dbceab6472498cd21478d953870,

title = "An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography",

abstract = "In this paper, we describe an algorithm to compute chains of (2,2)-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.",

author = "Pierrick Dartois and Luciano Maino and Giacomo Pope and Damien Robert",

note = "Publisher Copyright: {\textcopyright} 2025 International Association for Cryptologic Research.; ASIACRYPT 2024 : 30th International Conference on the Theory and Application of Cryptology and Information Security ; Conference date: 09-12-2024 Through 13-12-2024",

year = "2024",

month = dec,

day = "12",

doi = "10.1007/978-981-96-0891-1_10",

language = "English",

isbn = "9789819608904",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Singapore",

pages = "304--338",

editor = "Kai-Min Chung and Yu Sasaki",

booktitle = "Advances in Cryptology – ASIACRYPT 2024",

address = "Singapore",

url = "https://asiacrypt.iacr.org/2024/",

}

Dartois, P, Maino, L, Pope, G & Robert, D 2024, An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography. in K-M Chung & Y Sasaki (eds), Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. Lecture Notes in Computer Science, vol. 15486, Springer, Singapore, pp. 304-338, ASIACRYPT 2024, Kolkata, India, 9/12/24. https://doi.org/10.1007/978-981-96-0891-1_10

An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography. / Dartois, Pierrick ; Maino, Luciano; Pope, Giacomo et al.
Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. ed. / Kai-Min Chung; Yu Sasaki. Springer, Singapore, 2024. p. 304-338 (Lecture Notes in Computer Science; Vol. 15486).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography

AU - Dartois, Pierrick

AU - Maino, Luciano

AU - Pope, Giacomo

AU - Robert, Damien

PY - 2024/12/12

Y1 - 2024/12/12

N2 - In this paper, we describe an algorithm to compute chains of (2,2)-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

AB - In this paper, we describe an algorithm to compute chains of (2,2)-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

UR - https://asiacrypt.iacr.org/2024/

U2 - 10.1007/978-981-96-0891-1_10

DO - 10.1007/978-981-96-0891-1_10

M3 - Conference Contribution (Conference Proceeding)

SN - 9789819608904

T3 - Lecture Notes in Computer Science

SP - 304

EP - 338

BT - Advances in Cryptology – ASIACRYPT 2024

A2 - Chung, Kai-Min

A2 - Sasaki, Yu

PB - Springer, Singapore

T2 - ASIACRYPT 2024

Y2 - 9 December 2024 through 13 December 2024

ER -

Dartois P, Maino L, Pope G, Robert D. An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography. In Chung KM, Sasaki Y, editors, Advances in Cryptology – ASIACRYPT 2024: 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9–13, 2024, Proceedings, Part III. Springer, Singapore. 2024. p. 304-338. (Lecture Notes in Computer Science). doi: 10.1007/978-981-96-0891-1_10

An Algorithmic Approach to (2,2)-isogenies in the Theta Model and Applications to Isogeny-based Cryptography

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Handle.net

Other files and links

Fingerprint

Cite this