[Resource Topic] 2022/1068: Evaluating isogenies in polylogarithmic time

Resource Foundations
#1

Welcome to the resource topic for 2022/1068

Title:
Evaluating isogenies in polylogarithmic time

Authors: Damien Robert

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 π‘ž).

ePrint: https://eprint.iacr.org/2022/1068

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 .