Welcome to the resource topic for 2024/1852
Title:
Faster algorithms for isogeny computations over extensions of finite fields
Authors: Shiping Cai, Mingjie Chen, Christophe Petit
Abstract:Any isogeny between two supersingular elliptic curves can be defined over \mathbb{F}_{p^2}, however, this does not imply that computing such isogenies can be done with field operations in \mathbb{F}_{p^2}. In fact, the kernel generators of such isogenies are defined over extension fields of \mathbb{F}_{p^2}, 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 \ell-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 Eriksen, Panny, Sotáková and Veroni (LuCaNT’23) in the case of a generic prime characteristic, achieving around 30% speedup over their results.
ePrint: https://eprint.iacr.org/2024/1852
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .