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

Paper 2023/1747

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

Pierrick Dartois, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux

Luciano Maino, University of Bristol

Giacomo Pope

, University of Bristol, NCC Group

Damien Robert

, Inria Bordeaux - Sud-Ouest Research Centre, Institut de Mathématiques de Bordeaux

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.

Note: Updated after resubmission to fix typos and the inclusion of an explicit description of projective formulae, previously only mentioned in passing

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: isogenies abelian surfaces theta model post-quantum cryptography implementation
Contact author(s): pierrick dartois @ u-bordeaux fr
luciano maino @ bristol ac uk
giacomo pope @ nccgroup com
damien robert @ inria fr
History: 2024-06-05: last of 2 revisions; 2023-11-11: received; See all versions
Short URL: https://ia.cr/2023/1747
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1747,
      author = {Pierrick Dartois and Luciano Maino and Giacomo Pope and Damien Robert},
      title = {An Algorithmic Approach to $(2,2)$-isogenies in the Theta Model and Applications to Isogeny-based Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1747},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1747}
}