Equivalent computational problems for superspecial abelian surfaces

Mickaël Montessinos · 2026

Read Equivalent computational problems for superspecial abelian surfaces by Mickaël Montessinos (2026) 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-2601-18050.txt.

Introduction

Mickaël Montessinos ties together several hard computing problems about special surfaces. His 2026 preprint deals with superspecial abelian surfaces with a principal polarization. The problems include computing the endomorphism ring of such a surface. They also include computing a certain matrix named for Ibukiyama, Katsura, and Oort, and finding isomorphisms between unpolarised surfaces. The author shows reductions and equivalences between these problems.

Equivalence means a solver for one problem yields solvers for the rest. That web of links lets progress on any one front lift the others. These surfaces matter for cryptography based on isogenies. Clear problem links help judge how hard that cryptography really is.

Catalog record

CREATORMickaël Montessinos
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18050

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Equivalent computational problems for superspecial abelian surfaces Thanks: The author is supported by the grant ”EXCELLENCE-151343”. Mickaël Montessinos Abstract . We show reductions and equivalences between various problems related to the computation of the endomorphism ring of principally polarised superspecial abelian surfaces. Problems considered are the computation of the Ibukiyama-Katsura-Oort matrix and computation of unpolarised isomoprhisms between superspecial abelian surfaces. 2020 Mathematics Subject Classification Primary 14Q10 1. Introduction The problem of computing the endomorphism ring of a supersingular elliptic over a finite field has been well studied in recent years. It was proven equivalent to the Isogeny Path Problem and the One Isogeny Problem [ 16 ] . In particular, the hardness of the endomorphism ring computation underlies the security of most one-dimensional isogeny-based cryptographic protocols. The precise statement of the problem depends on the choice of representation for the endomorphism ring of a supersingular elliptic curve. Essentially, one may either wish to know an efficient algorithm to evaluate 4 endomorphisms which form a \mathbb{Z} -basis of the endomorphism ring, or to know the basis of a maximal order in the quaternion \mathbb{Q} -algebra B_{p,\infty} which ramifies at the prime p , the characteristic of the base field of the curve. The two forms of the problem were proved to be equivalent, first heuristically [ 7 ] , then unconditionally under GRH [ 26 ] and finally unconditionally [ 16 ] . The main tool appearing in reductions from most problems underlying the security of isogeny-based schemes is the so-called \mathsf{KLPT} algorithm. Its original version was published in [ 14 ] , and relied on specific conditions regarding the characteristic of the base field of the elliptic curves involved, as well as some heuristic considerations. Several subsequent works improved both the performance and the assumptions of the algorithm, and a general version relying only on GRH was given in [ 26 ] . This algorithm uses quaternion arithmetic to compute an isogeny of power-smooth degree between elliptic curves with known endomorphism rings. We note however that the more recent results from [ 16 ] overcome the reliance on GRH by circumnavigating the need for using KLPT. In recent years, applications of the algorithmic theory of principally polarised superspecial abelian varieties of dimension greater than one has emerged, both regarding the construction of cryptographic schemes [ 3 ] and the cryptanalysis of schemes using supersingular elliptic curves [ 4 , 15 , 22 ] . As in the case of one dimensional protocols, most security assumptions rely on the difficulty of computing polarised isogenies between principally polarised superspecial abelian surfaces (PPSAS). As for maximal quaternion orders, a \mathsf{KLPT}^{2} algorithm working over hermitian matrices in M_{2}(B_{p,\infty}) and allowing for the computation of polarised isogenies of power-smooth degrees between surfaces was given in [ 2 ] . In the higher dimensional case, since all unpolarised superspecial abelian varieties are isomorphic, their endomorphisms rings are as well. In fact, they are all isomorphic to the ring M_{2}(O) , where O is any maximal order in the quaternion algebra B_{p,\infty} . The input to the \mathsf{KLPT}^{2} algorithm is therefore not a characterisation of the endomorphism ring, but rather the data of a certain Hermitian matrix in M_{2}(O) , which we call the Ibukiyama-Katsura-Oort matrix, for reasons that will be made clear in Section 2 . Much like in the one dimensional case, a question naturally arises of what the various alternative computational representations of a usable ”known endomorphism ring” are, and of their equivalences. The knowledge the Ibukiyama-Katsura-Oort matrix of a principally polarised superspecial abelian surface is analogous to the knowledge of a maximal quaternion order isomorphic to the endomorphism ring of a curve, in the sense that it is the input to the relevant \mathsf{KLPT}^{2} algorithm. Another possible representation is the knowledge of efficient algorithms representing 16 endomorphisms of an abelian variety A which form a basis of the endomorphism ring. If the variety A is represented as either a product of elliptic curves or the Jacobian of a hyperelliptic curve of genus 2 , one may hope that an efficient representation of these endomorphisms be enough to compute their image by the Rosati involution related to the principal polarisation implied by the representation of A . Another problem to consider is that of the computation of an unpolarised isomoprhism between two PPSAS. It is known that the restriction of this problem to PPSAS presented as products of supersingular elliptic curves may be solved when the endomorphism rings of the curves are known [ 9 ] . This problem is also a natural candidate for equivalence to the computation of the Ibukiyama-Katsura-Oort matrix of a PPSAS: one may recover the endomorphisms of the factors of a product surface from the Ibukiyama-Katsura-Oort matrix, and then compute isomorphisms to other products. Conversely, computing an unpolarised isomorphism from a variety A to a reference surface A_{0} may allow to recover the Ibukiyama-Katsura-Oort matrix. Finally, one may fix a supersingular curve E_{0} with known endomorphism ring O_{0} , and consider the structure of the Hermitian left O_{0} -module \Hom(A,E_{0} associated to a PPSAS [ 23 ] . We do not consider this problem in this work, but it is the object of [ 20 ] . 1.1. Our contributions Let A be a PPSAS. If A is presented as a product of supersingular elliptic curves, we prove that the following problems are equivalent under GRH and the assumptions necessary to use the \mathsf{KLPT}^{2} algorithm: • Computing the Ibukiyama-Katsura-Oort matrix of A ; • Computing an effective representation of endomorphisms of A that form a basis of \End(A) as a \mathbb{Z} -module; • Computing an unpolarised isomorphism from E_{0}^{2} (or any product of curves with known endomorphism rings) to A If A is presented as the Jacobian surface of a genus 2 hyperelliptic curve instead, we prove that the problem of computing the Ibukiyama-Kastura-Oort matrix of A is equivalent to the problem of computing a so-called good representation of its endomorphism ring, which contains effective representations of endomorphisms of A as above, but also some additional information. We also prove that the problems of computing an effective representation of the endomorphism ring of A and computing an unpolarised isomorphism to any other PPSAS with known Ibukiyama-Katsura-Oort matrix both reduce to the computation of the Ibukiyama-Katsura-Oort matrix of A . Theses results are stated formally as Theorem 3.5 , and a diagram presenting the various reductions is given there. It should be noted that, albeit polynomial, the reduction from computing the Ibukiyama-Katsura-Oort matrix of a variety from its endomorphism ring with additional information is not practical. Indeed, the algorithm for computing an isomorphism between the endomorphism algebra \End(A)otimes\mathbb{Q} and M_{2}(B_{p,\infty}) has a very large constant part in its complexity. We provide an implementation of the algorithm from Lemma 5.1 at the following address: https://gitlab.com/Mickanos/isomorphisms-to-superspecial-jacobians 1.2. Methods The two main technical contributions of this work are the reduction from computing unpolarised isomorphisms to computing Ibukiyama-Katsura-Oort matrices, and from computing Ibukiyama-Katsura-Oort matrices to computing the endomorphism ring of a PPSAS and some additional information. The problem of computing unpolarised isomorphisms between products of supersingular elliptic curves knowing their endomorphism rings being solved, it is enough to provide an algorithm which, given a

Read the complete text