IACR News item: 27 June 2023
Gustavo Banegas, Valerie Gilchrist, Anaëlle Le Dévéhat, Benjamin Smith
ePrint Report
Consider the problem of efficiently evaluating
isogenies $\phi: \mathcal{E} \to \mathcal{E}/H$
of elliptic curves over a finite field $\mathbb{F}_q$,
where the kernel \(H = \langle{G}\rangle\)
is a cyclic group of odd (prime) order:
given \(\mathcal{E}\), \(G\), and a point (or several points) $P$ on $\mathcal{E}$,
we want to compute $\phi(P)$.
This problem is at the heart of efficient implementations of
group-action- and isogeny-based post-quantum cryptosystems such as CSIDH.
Algorithms based on Vélu's formul\ae{} give an efficient solution to this problem
when the kernel generator $G$ is defined over $\mathbb{F}_q$.
However, for general isogenies,
\(G\) is only defined over some extension $\mathbb{F}_{q^k}$,
even though $\langle{G}\rangle$ as a whole (and thus \(\phi\))
is defined over the base field $\mathbb{F}_q$;
and the performance of Vélu-style algorithms degrades rapidly as $k$ grows.
In this article we revisit the isogeny-evaluation problem
with a special focus on the case where $1 \le k \le 12$.
We improve Vélu-style isogeny evaluation
for many cases where \(k = 1\)
using special addition chains,
and combine this with the action of Galois
to give greater improvements when \(k > 1\).
Additional news items may be found on the IACR news page.