Orient Express: Using Frobenius to Express Oriented Isogenies

Abstract

In this paper we study supersingular elliptic curves primitively oriented by an imaginary quadratic order, where the orientation is determined by an endomorphism that factors through the Frobenius isogeny. In this way, we partly recycle one of the main features of CSIDH, namely the fact that the Frobenius orientation can be represented for free. This leads to the most efficient family of ideal-class group actions in a range where the discriminant is significantly larger than the field characteristic p. Moreover, if we orient with a non-maximal order and we assume that it is feasible to compute the ideal-class group of the maximal order, then also the ideal-class group of O is known and we recover the central feature of SCALLOP-like constructions.

We propose two variants of our scheme. In the first one, the orientation is by a suborder of the form Z(f√-p) for some f coprime to p, so this is similar to SCALLOP. In the second one, inspired by the work of Chenu and Smith, the orientation is by an order of the form Z(√-dp) where d is square-free and not a multiple of p. We give practical ways of generating parameters, together with a proof-of-concept SageMath implementation of both variants, which shows the effectiveness of our construction.