Paper 2022/1068

Evaluating isogenies in polylogarithmic time

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 𝑞).