Skip to main navigation Skip to search Skip to main content

Faster algorithms for isogeny computations over extensions of finite fields

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

6 Downloads (Pure)

Abstract

Any isogeny between two supersingular elliptic curves can be defined over Fp2, however, this does not imply that computing such isogenies can be done with field operations in Fp2. In fact, the kernel generators of such isogenies are defined over extension fields of Fp2, generically with extension degree linear to the isogeny degree. Most algorithms related to isogeny computations are only efficient when the extension degree is small. This leads to efficient algorithms used in isogeny-based cryptographic constructions, but also limits their parameter choices at the same time. In this paper, we consider three computational subroutines regarding isogenies, focusing on cases with large extension degrees: computing a basis of l-torsion points, computing the kernel polynomial of an isogeny given a kernel generator, and computing the kernel generator of an isogeny given the corresponding quaternion ideal under the Deuring correspondence. We then apply our algorithms to the constructive Deuring correspondence algorithm from [EPSV23] in the case of a generic prime characteristic, achieving around 30% speedup over [EPSV23].
Original languageEnglish
Title of host publicationNumber-Theoretic Methods in Cryptology
Subtitle of host publication4th International Conference, NuTMiC 2024, Szczecin, Poland, June 24–26, 2024, Revised Selected Papers
EditorsAndrzej Dąbrowski, Josef Pieprzyk, Jacek Pomykała
PublisherSpringer
Pages136-155
Number of pages19
Edition1
ISBN (Electronic)9783031823800
ISBN (Print)9783031823794
Publication statusPublished - 19 Feb 2025
EventNumber-Theoretic Methods in Cryptology 2024 - Szczecin, Poland
Duration: 24 Jun 2024 → 26 Jun 2024
Conference number: 4
https://nutmic2024.usz.edu.pl/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume14966
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceNumber-Theoretic Methods in Cryptology 2024
Abbreviated titleNuTMiC 2024
Country/TerritoryPoland
CitySzczecin
Period24/06/24 → 26/06/24
Internet address

Fingerprint

Dive into the research topics of 'Faster algorithms for isogeny computations over extensions of finite fields'. Together they form a unique fingerprint.

Cite this