Algebraic approaches for solving isogeny problems of prime power degrees (Q2027266)

Since 2006, isogenies between elliptic curves have began to be used for constructing several cryptographic schemes and hash functions. The security of isogeny cryptosystems is based on the general isogeny problem: Given two elements \(j\), \(\tilde{j}\) of a finite field \(\mathbb{F}_q\), to find an isogeny \(\phi : E \rightarrow \tilde{E}\), if exists, such that \( j(E) = j\) and \(j(\tilde{E}) = \tilde{j}\), where \(j(E)\) denotes the \(j\)-invariant of an elliptic curve \(E\). In the supersingular case, it is sufficient to take \(\mathbb{F}_{p^2}\) as the base field for a prime \(p\), since every supersingular curve over \(\mathbb{F}_p\) is isomorphic to one defined over \(\mathbb{F}_{p^2}\). An interesting variant of this problem is the case where the degree of \(\phi\) is known. In this paper, practical approaches for solving isogeny problems are considered, and in particular, the supersingular isogeny graph path-finding problem of prime power degree \(\ell = \ell_0^e\), for small \(\ell_0\), is discussed. Two algebraic approaches are proposed for solving this problem. The basic strategy is the reduction of the isogeny problem to a system of algebraic equations. The first approach uses the modular polynomial of prime level \(\ell_0\). The system of equations of modular polynomial is divided into two, and their Gröbner bases are computed to efficiently find \(j\)-invariants of intermediate curves between given two isogenous elliptic curves \(E\) and \(\tilde{E}\). The second approach takes an intermediate curve \(E_0\) between \(E\) and \(\tilde{E}\), and considers kernel polynomials \(F(x)\) and \(\tilde{F}(\tilde{x})\) of two isogenies \(\phi : E \rightarrow E_0\) and \(\tilde{\phi} : \tilde{E} \rightarrow E_0\). Since the curve \(E_0\) is unknown, its Weierstrass coefficients are considered as variables, and represent \( F(x)\) and \(\tilde{F}(\tilde{x})\) as certain multivariate polynomials. Finally, by using Vélu's formulae for isogenies, \(\phi \) and \(\tilde{\phi}\) are represented as rational functions over polynomial rings, and set up algebraic equations to determine the Weierstrass coefficients of \(E_0\). Moreover, some experimental results are presented.