Paper 2023/995

Fast and Frobenius: Rational Isogeny Evaluation over Finite Fields

Abstract

Consider the problem of efficiently evaluating isogenies $\varphi :\mathcal{E}\to \mathcal{E}/H$ of elliptic curves over a finite field ${\mathbb{F}}_q$, where the kernel $H=⟨G⟩$ 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 $\varphi (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 $$ is defined over $$. However, for general isogenies, $$ is only defined over some extension $$, even though $$ as a whole (and thus $$) is defined over the base field $$; and the performance of Vélu-style algorithms degrades rapidly as $$ grows. In this article, we revisit the isogeny-evaluation problem with a special focus on the case where $$. We improve Vélu-style isogeny evaluation for many cases where $$ using special addition chains, and combine this with the action of Galois to give greater improvements when $$.