Evaluating isogenies in polylogarithmic time

Damien Robert

Paper 2022/1068

Evaluating isogenies in polylogarithmic time

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

Abstract

Let 𝑓 ∶ 𝐸 → 𝐸′ be an N-isogeny between elliptic curves (or abelian varieties) over a finite field 𝔽_𝑞. We show that there always exist an efficient representation of 𝑓 that takes polylogarithmic 𝑂(log^𝑂(1) 𝑁 log 𝑞) space and which can evaluate 𝑓 at any point 𝑃 ∈ 𝐸(𝔽_{𝑞^𝑘}) in polylogarithmic 𝑂(log^𝑂(1) 𝑁) arithmetic operations in 𝔽_{𝑞^𝑘}. Furthermore, this efficient representation can be computed by evaluating 𝑓 on 𝑂(log 𝑁) points defined over extensions of degree 𝑂(log 𝑁) over 𝔽_𝑞. In particular, if 𝑓 is represented by the equation 𝐻(𝑥) = 0 of its kernel 𝐾, then using Vélu’s formula the efficient representation can be computed in time 𝑂 ̃(𝑁 log 𝑞 + log^2 𝑞).

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: isogeny
Contact author(s): damien robert @ inria fr
History: 2022-08-21: approved; 2022-08-17: received; See all versions
Short URL: https://ia.cr/2022/1068
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1068,
      author = {Damien Robert},
      title = {Evaluating isogenies in polylogarithmic time},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1068},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1068}},
      url = {https://eprint.iacr.org/2022/1068}
}