Computing Isomorphisms between Products of Supersingular Elliptic Curves
Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer · 2025
Read Computing Isomorphisms between Products of Supersingular Elliptic Curves by Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-21535.txt.
Introduction
Pierrick Gaudry, Julien Soumier, and Pierre-Jean Spaenlehauer give ways to compute maps between products of special elliptic curves, in a 2025 paper. A classic theorem says such maps exist for these curves over finite fields. The task here is to find them in practice, not just to know they exist. The authors assume the rings of maps for each curve are known at the start.
Their route turns the curve problem into an algebra problem with quaternions, a type of number system with four parts. The work then comes down to solving sets of equations over whole numbers. New tools handle those equations when a small subring is at hand. Put together, the steps give a fast randomized method that runs in fair time.
Catalog record
| CREATOR | Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 77 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21535
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computing Isomorphisms between Products of Supersingular Elliptic Curves Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer Abstract . The Deligne-Ogus-Shioda theorem guarantees the existence of isomorphisms between products of supersingular elliptic curves over finite fields. In this paper, we present an algorithm for explicitly computing these isomorphisms given the endomorphism rings of the curves. Under GRH, it is proved to run in expected polynomial time. Our approach leverages the Deuring correspondence, enabling us to reformulate computational isogeny problems into algebraic problems in quaternions. Specifically, we reduce the computation of isomorphisms to solving systems of quadratic and linear equations over the integers derived from norm equations. We develop ℓ \ell -adic techniques for solving these equations when we have access to a low discriminant subring. Combining these results leads to the description of an efficient probabilistic Las Vegas algorithm for computing the desired isomorphisms. 1. Introduction Algorithms for computing isogenies between elliptic curves have been a vast field of research, leading to the recent development of higher-dimensional techniques in cryptography [ 17 , 8 ] . In particular, abelian varieties of dimension g\geq 2 isomorphic to a product of supersingular elliptic curves play an important role in this setting [ 5 , 18 , 23 , 3 , 2 ] . An important feature of such abelian varieties is that they are all isomorphic over an algebraic closure. Let \mathbb{F}_{q} be a finite field of characteristic p>0 . An abelian variety defined over \mathbb{F}_{q} is superspecial if it is \overline{\mathbb{F}_{q}} -isomorphic to a product of supersingular elliptic curves defined over \overline{\mathbb{F}_{q}} . The Deligne-Ogus-Shioda theorem [ 25 , Thm. 3.5] states that for all g>1 , all dimension- g superspecial abelian varieties defined over \mathbb{F}_{q} are \overline{\mathbb{F}_{q}} -isomorphic (as unpolarized abelian varieties). The aim of this paper is to investigate computational aspects of this theorem. Problem 1.1 (Effective Deligne-Ogus-Shioda problem) . Let g\geq 2 be an integer. Given supersingular elliptic curves E_{1},\dots,E_{g} and E_{1}^{\prime},\dots,E_{g}^{\prime} defined over \mathbb{F}_{q} , compute an \overline{\mathbb{F}_{q}} -isomorphism E_{1}\times\cdots\times E_{g}\to E_{1}^{\prime}\times\cdots\times E_{g}^{\prime} . This appears to be a difficult computational problem. Indeed, computing the endomorphism ring of a supersingular curve is a computational problem which is considered hard, and the security of several cryptographic constructions relies on it [ 3 , 2 ] . Solving Problem 1.1 would provide non-trivial information about the endomorphism rings of the curves: From an isomorphism E_{1}\times E_{2}\to E_{1}^{\prime}\times E_{2}^{\prime} , we can compute four isogenies \varphi_{ij}:E_{j}\to E_{i}^{\prime} , and the composition \widehat{\varphi}_{21}\varphi_{22}\widehat{\varphi}_{12}\varphi_{11}:E_{1}\to E_{1} is in general a non-trivial endomorphism of E_{1} . In this paper, we study Problem 1.1 in the context where we have extra information: the endomorphism rings of the elliptic curves are given (see Section 2.2.2 for technical details on the encoding of the endomorphism rings). In this setting, Deuring’s correspondence allows us to translate Problem 1.1 into a problem about quaternion algebras. 1.1. Contributions We focus on the case g=2 , which is the base case which serves as a building block for the general case g\geq 2 . Therefore our main problem is the computation of an isomorphism E_{1}\times E_{2}\to E_{1}^{\prime}\times E_{2}^{\prime} between two products of supersingular elliptic curves, assuming that their endomorphisms rings are known. Endomorphism rings are given via an efficient representation of a \mathbb{Z} -basis together with an explicit isomorphism with a maximal order in the quaternion algebra \mathscr{B}_{p,\infty} . Our main contribution is a polynomial-time algorithm that computes an isomorphism E_{1}\times E_{2}\to E_{1}^{\prime}\times E_{2}^{\prime} between products of maximal elliptic curves over \mathbb{F}_{p^{2}} , assuming that we know the endomorphism rings of the curves. This algorithm relies on two main subroutines. The first one describes how to build a two by two matrix of isogenies which is an isomorphism, given its first column. The second one allows us to compute isomorphisms of the form E^{2}\to E_{1}^{\prime}\times E when we know a non-scalar low-discriminant endomorphism in \End(E) . In order to design such algorithms, we need some new computational techniques. We provide a quasi-linear quaternionic method to divide an endomorphism by an isogeny, see Proposition 4.6 . Our main theoretical tool is a necessary and sufficient criterion to decide whether a pair of separable isogenies \varphi_{11}:E_{1}\to E_{1}^{\prime} , \varphi_{21}:E_{1}\to E_{2}^{\prime} of coprime degrees can appear as the first column of a matrix (\varphi_{ij})_{i,j\in\{1,2\}} describing an isomorphism E_{1}\times E_{2}\to E_{1}^{\prime}\times E_{2}^{\prime} : this happens when the direct sum of the kernels of \varphi_{11} and \varphi_{21} is the kernel of an isogeny E_{1}\to E_{2} . This result is formalized in Theorem 5.3 and is used in our algorithms for both subroutines. In the low-discriminant case, we also use the fact that we can solve efficiently norm equations in low-discriminant imaginary quadratic orders. In both cases, we use Wesolowski’s variant [ 31 ] of the KLPT algorithm [ 15 ] as an important building block, whose complexity is proved under GRH. To demonstrate some of the algorithms presented in this paper, we provide a proof-of-concept implementation in the computer algebra software Magma , freely available at [ 1 ] . We only compute the quaternionic part of the isomorphisms, meaning that we output four ideals \{I_{ij}\}_{1\leq i,j\leq 2} , which are kernel ideals of four isogenies \varphi_{I_{ij}} , which form a matrix that represents an isomorphism. To recover the isogenies, one can use IdealToIsogeny algorithms, described for example in [ 3 , 21 ] ; see also [ 10 , Lem. 4] which provides a general polynomial-time complexity bound for this step. 1.2. Related works Superspecial abelian varieties are central objects in the recent developments of isogeny-based cryptography , as they are the main characters of the new high-dimensional techniques, see e.g. [ 23 , 7 , 8 ] . Being able to compute isomorphisms between such objects would be a useful computational tool. In particular, one typical setting is to consider a special curve which has the property that its endomorphism ring contains a low-discriminant imaginary quadratic order. For instance, when p\equiv 3\bmod 4 , the endomorphism ring of the elliptic curve E_{0} defined over \mathbb{F}_{p^{2}} by the equation y^{2}=x^{3}+x contains a subring isomorphic to \mathbb{Z}[i] . Being able to compute an isomorphism between a superspecial abelian variety and E_{0}^{g} would give access to these low-discriminant subrings of endomorphisms. Another application of our work is the representation of some polarized abelian varieties. In particular, the Ibukiyama-Katsura-Oort correspondence shows that superspecial principally polarized abelian surfaces (up to polarized isomorphisms) can be represented via two by two matrices over the quaternions (modulo congruence). Algorithms have been recently developed in [ 6 ] to perform efficient computations via this representation. Our algorithms contribute to this toolbox since isomorphisms between products of supersingular elliptic curves can be used to compute the Ibukiyama-Katsura-Oort representation of principally polarized abelian surfaces that are not Jacobians of genus- 2 curves. In the direction of the construction of isomorphisms between products of elliptic curves, one can find in the proof of [ 4 , Thm A.1] an explicit construction of an isomorphism between the E\times E/(K_{1}+K_{2}) and E/K_{1}\times E/K_{2} for K_{i} finite étale subgroups of coprime orders. This result has similarities with our Theorem 5.3 , but it is not general enough for our purposes. 1.3. Organization of the paper Section 2 recalls background material. We state