Supersingularity and Superspeciality Verification of Abelian Surfaces

Supersingularity and Superspeciality Verification of Abelian Surfaces Maria Corte-Real Santos1 , Gioella Lorenzon2 , and Krijn Reijnders2

arXiv:2610.01924v1 [math.NT] 1 Oct 2026

1

École Normale Supérieure de Lyon, CNRS 2 COSIC, KU Leuven

Abstract. Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiate this research topic by giving an efficient Monte Carlo algorithm to verify if an abelian surface over Fp is supersingular in O(log p) with negligible failure probability, and an efficient conclusive algorithm if the order is smooth. We derive this algorithm by a careful analysis on the structure of supersingular Jacobians over Fp . Furthermore, we derive efficient algorithms to verify if an abelian variety of any dimension is minimal or maximal, and to verify if a Jacobian of any dimension is superspecial.

Keywords: post-quantum cryptography, isogenies, Jacobians, supersingularity

1

Introduction

Since the spectacular break of SIDH/SIKE [10, 25, 33], higher-dimensional techniques have revolutionized isogeny-based cryptography. Modern protocols, such as the signature schemes SQIsign [1] and PRISM [3], the NIKE MIKE [35], or the KEM POKÉ [5] heavily rely on higher-dimensional isogenies for both performance and small sizes. Abelian varieties of dimension g > 1 have therefore become fundamental objects in isogeny-based cryptography. More precisely, such protocols rely on supersingular principally polarized abelian varieties, and often even the more restricted superspecial principally polarized abelian varieties. With recent developments, such as the module action framework [4, 35] or the Shimura class group action on abelian surfaces [11], validating supersingularity becomes crucial to security. This can be seen as the higher-dimensional equivalent of public key validation in CSIDH [12], where omitting key validation would introduce a significant attack vector for an adversary. Supersingular elliptic curves. Supersingularity verification of elliptic curves has been studied extensively in both mathematical and cryptographic literature. Sutherland [42] initiated this study by describing a Monte Carlo test for elliptic curves over Fp and Fp2 : take a random point P ∈ E(Fq ) and check if [p]P = ±P . 1 The probability of a false positive is O(q − 2 ) and therefore suitable for almost all cryptographic purposes, where q is large.

2

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Nevertheless, such a test does not conclusively prove that a curve is supersingular. To do so, Sutherland describes an algorithm based on the depth of isogeny volcanoes. In CSIDH [12], the supersingularity test is instead performed by ver√ ifying that the order of a random point is larger than 4 p, which, by the bound on width of the Hasse-Weil interval, proves that the order of the curve is p + 1, and therefore the curve is supersingular. dCSIDH [8] optimizes this approach for primes p where 2f | p + 1 with f > 12 log p, e.g., most primes used in currentday isogeny-based cryptography. Doliskani [18] describes an algorithm based on polynomial identity testing to establish supersingularity, which uses the fact that the p-th division polynomial ψp (x) is precisely ±1 for supersingular curves, as these have p-rank 0. Banegas, Gilchrist, and Smith [2] give an in-depth performance comparison between these algorithms, and reinterpret Doliskani’s test using Montgomery arithmetic, for which Robert [34] gives a reinterpretation as a self-pairing using cubical arithmetic. Lastly, in [31], pairings are used to optimize the verification of the order of the curve, moving much of the computational cost from curve arithmetic to field arithmetic. Supersingular and superspecial abelian surfaces. Moving up in dimension, there is no single analogue of supersingularity. Instead, there are several inequivalent generalizations organized by the Ekedahl–Oort stratification. As a leading example in dimension 2, supersingularity for elliptic curves may be generalized as either supersingularity of an abelian surface, or the more specific notion of superspeciality. The latter property is often the right generalization for cryptographic purposes. Although literature exists which studies this classification of abelian varieties in this stratification, we are not aware of literature addressing the specific question of efficiently verifying the supersingularity and superspeciality of abelian surfaces over a finite field. To the best of our knowledge, the best known methods to verify such results depend on point-counting algorithms or L-polynomial computations, which are prohibitively slow for the large primes used in isogeny-based cryptography. In this work, we present an efficient algorithm for supersingularity testing of abelian surfaces over Fp . We furthermore study the question of minimality and maximality of abelian varieties, which allows us to efficiently verify superspeciality of Jacobians over Fp and Fp2 . Key Example. We demonstrate the core idea of our simple and efficient probabilistic verification with the following key example, in which we verify minimality or maximality of an abelian variety. This property implies superspeciality, and therefore supersingularity [22, Thm. 5.3]. $

Algorithm 1 Let A be an abelian surface over Fp2 . Let P ← − A(Fp2 ). – If [p + 1]P = 0A , return true. – Otherwise, return false. The algorithm for minimal abelian surfaces replaces p + 1 by p − 1. The probability of a false positive is O(p−1 ), and is thus negligibly small for large primes.

Supersingularity and Superspeciality Verification of Abelian Surfaces

3

This follows from what we call the width-bound argument, used by Sutherland for elliptic curves [42]. In Theorem 4.1, we generalize this argument to abelian varieties. However, this algorithm only works for minimal and maximal varieties, whereas general supersingularity testing is much more complicated. Already for the cases of abelian surfaces over Fp , we require a deeper understanding of the group structures of supersingular abelian surfaces and their twists. Furthermore, the above algorithm can never conclusively prove that an abelian surface is supersingular or even superspecial, which requires additional understanding of the isotropic subgroups of abelian surfaces. Contributions. We provide the first practical polynomial time supersingularity and superspeciality verification algorithms for abelian surfaces over Fp . We develop both probabilistic and conclusive algorithms. 1. In Section 3, we analyze the structure of supersingular and superspecial Jacobians over Fp , resulting in three key results: (a) Theorem 3.12, which describes the possible orders of supersingular Jacobians over Fp2 ; (b) Table 3, giving the group structures of supersingular Jacobians over Fp ; (c) Theorem 3.26, which classifies superspecial Jacobians using the automorphism group of the associated genus-2 curve. These results underlie both the probabilistic and conclusive testing. 2. In Section 4, we derive algorithms for probabilistic verification of extremality, supersingularity and superspeciality of abelian surfaces. (a) In Algorithm 2 and Theorem 4.1, we generalize Algorithm 1 to verify minimality and maximality of an abelian variety of any dimension. (b) Using Theorem 3.26 we construct Algorithm 3, an efficient algorithm for testing superspeciality of Jacobians over Fp . Its correctness and runtime are proved in Theorem 4.2. We show a similar result for superspecial Jacobians over Fp2 in Appendix B. (c) In Algorithm 4 we give a O(log p) Monte Carlo supersingularity test for abelian surfaces over Fp , with all arithmetic performed over Fp . Its correctness and runtime are based on Theorem 4.7. 3. In Section 5, we derive algorithms for conclusive verification of supersingularity for abelian surfaces over Fp , summarized in Corollaries 5.5 and 5.10. We furthermore analyze the factorization and discrete logarithm requirements for these algorithms, and specialize to a case of specific cryptographic interest, i.e. when 2f | p + 1, with f close to log p. We give an overview of all verification algorithms in this work in Table 1 (probabilistic tests) and Table 2 (conclusive tests), listing the setting in which each algorithm applies, its complexity, and either its failure probability or its structural requirements. We implemented these algorithms in Magma, and benchmark their performance in Section 6. The code is available at the following repository, https://github.com/KULeuven-COSIC/supersingularity-and-superspeciality.

4

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Table 1: Overview of probabilistic (Monte Carlo) verification algorithms in this work. Complexities count field operations in the stated field, and q = p or p2 . Algorithm

Verifies

Variety

Complexity

Algorithm 1 Algorithm 2 Algorithm 3 Algorithm 4

maximality maximality superspeciality supersingularity

A/Fp2 A/Fq , any g J /Fq , any g A/Fp

O(log p) O(log p) O(g log p) O(log p)

False pos. O(p−1 ) O(p−1 ) O((g − 1) p−1 ) O(p−1/2 )

Table 2: Overview of conclusive verification algorithms in this work. In the first three rows, n = p2 − bp + 1 for b ∈ {−1, 0, 1} and n = p ∓ 1 for b = ±2, and ω(n) is the number of distinct prime factors of n. We assume the factorization of n is known. Complexities count field operations in the stated field. Algorithm

Verifies

Setting

Complexity

Requirements

Corollary 5.5 Corollary 5.5 Corollary 5.10 Lemma 5.15 Algorithm 5 Lemma 5.16

supersing. supersing. supersing. supersing. maximality maximality

b = 2 over Fp b = −2 over Fp b ∈ {−1, 0, 1} over Fp b = ±2 over Fp b = −2 over Fp2 b = −2 over Fp2

O(log ω(n) log p) O(log ω(n) log p) O(log ω(n) log p) O(log p) O(log p) O(log p)

factorization of n DLog in µp+1 works over Fpk p = c · 2f ± 1 DLog in µp+1 p = c · 2f − 1

Some of this work is phrased using Jacobians, representing principally polarized abelian surfaces that are neither products nor Weil restrictions. However, in practice we need fairly little machinery to apply our algorithms: the probabilistic algorithms rely only on uniform random sampling and scalar multiplication, whereas the conclusive algorithms additionally require pairing computations and discrete logarithms. Our conventions and the role of the principal polarization are detailed in Section 2. Related Work. The task of verifying supersingularity or superspeciality in dimension 2 fits into the much more general task of classifying curves and principally polarized abelian varieties according to their p-rank. This is called the Ekedahl– Oort stratification [28], and has been widely studied (see, e.g., [17, 27]). In dimension 2, one may directly detect supersingularity by computing the L-polynomial of the abelian surface or, equivalently, the characteristic polynomial of Frobenius. Methods to do so often rely on generalizations of Schooflike algorithms to determine the number of points on a curve or variety. Most directly applicable is the Schoof–Pila algorithm [29], and subsequent improvements [20, 24]. Of particular interest to this work is the article by Shi [39] on lifting L-polynomials of genus-2 curves. For superspeciality, the most well-

Supersingularity and Superspeciality Verification of Abelian Surfaces

5

known approach relies on computation of the Cartier-Manin or Hasse-Witt matrix, which also allows one to verify supersingularity. In Section 6, we compare these approaches to the algorithms given in this work. Acknowledgements. This work is supported by the European Research Council under grant No. 101116169 (AGATHA CRYPTY), under the European Union’s Horizon 2020 research and innovation programme (grant agreement ISOCRYPT – No. 101020788), by the Research Council KU Leuven grant C14/24/099 and by CyberSecurity Research Flanders with reference number VOEWICS02. The second-listed author is additionally supported by the Fonds voor Wetenschappelijk Onderzoek (FWO) under grant number 1139225N.

2

Preliminaries

We assume basic familiarity with elliptic curves and their arithmetic, see [40] for more background. Throughout, Fq denotes a finite field of characteristic p, and Fp its algebraic closure. 2.1

Supersingular Elliptic Curves

Supersingularity of elliptic curves over Fq can be defined by several equivalent properties. Among these, is that their endomorphism ring is isomorphic to a maximal order in a quaternion algebra, whereas ordinary curves have endomorphism rings isomorphic to quadratic orders. For this work, essential properties of supersingular elliptic curves are that their p-rank is 0, meaning that E[p](Fp ) = 0, and that the trace of the characteristic polynomial of Frobenius is a multiple of p. A shared feature of all these characteristics is that they enforce strict group structures on E(Fq ), in contrast with ordinary curves, whose group structures are much more flexible. Supersingular curves are fundamental in isogeny-based cryptography, as their rich endomorphism ring structures allow for flexibility and efficiency in the design of cryptographic algorithms. Furthermore, the precise control on the group structure allows for efficient isogeny computations using Velu’s formulas [43]. 2.2

Abelian Varieties

A polarization of an abelian variety A is an isogeny λ between A and its dual  induced by an ample line bundle. Such a polarization is principal whenever λ is an isomorphism. In this work we mostly focus on abelian surfaces, which are abelian varieties of dimension 2. A principally polarized abelian surface over Fq is either the Jacobian of a hyperelliptic curve of genus 2, the product of two elliptic curves over Fq , or the Weil restriction of an elliptic curve over Fq2 . All three come equipped with a canonical principal polarization. For brevity, we will often use the term abelian surface instead of principally polarized abelian surfaces. We remark, however, that the polarization is used

6

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

in only two ways: through the classification above, and results derived from it (e.g., Corollary 3.22 and Theorem 3.26); and through the Weil-pairing isotropy conditions of (1), used in the pairing-based conclusive tests in Section 5. Furthermore, in this work, we mainly focus on Jacobians of hyperelliptic curves, as supersingularity testing for Weil restrictions and products is easy: over a quadratic extension, a Weil restriction is isomorphic to a product, and a product is supersingular, and in particular superspecial, if and only if both factors are supersingular. Structure. The n-torsion of an abelian variety over a finite field are those points P ∈ A(Fq ) such that [n]P = 0. Let A[n] denote the subgroup of n-torsion points over the algebraic closure Fp . If dim A = g and n is coprime to p, then A[n] ∼ = (Z/nZ)

2g

.

The Fq -rational n-torsion A[n](Fq ) is significantly more restricted, due to isotropy conditions enforced by the Weil pairing, which is where the principal polarization is used as it identifies A with  and thereby turns the Weil pairing into a non-degenerate alternating pairing on A[n]. We follow [13, Prop. 5.78]: for a principally polarized abelian variety A/Fq of dimension g and an integer n coprime to p, let d = gcd(n, q − 1). Then we have A[n](Fq ) ,→ (Zn )g × (Zd )g .

(1)

In contrast, the p-torsion A[p] of an abelian variety is a more nuanced object, and in general has rank at most g instead of 2g, referred to as the p-rank of A. We refer to the smallest field extension Fqk such that A[n] ⊆ A(Fqk ) as the full n-torsion degree of A. This is closely related to the embedding degree k ′ ′ of n, defined by the smallest k ′ such that n | q k − 1, i.e., µn ⊆ F× . By the qk non-degeneracy of the Weil pairing en : A[n] × A[n] → µn , we have k ′ ≤ k. From the above, we can derive the general group structure of A(Fq ) as A(Fq ) ∼ = Z/n0 Z × . . . × Z/nr−1 Z where r ≤ 2g is the rank of A and ni+1 | ni for all i. We refer to n0 as the exponent of A(F Q q ), as we have [n0 ]P = 0 for all P ∈ A(Fq ), whereas the order is |A(Fq )| = ni . Supersingularity. In higher dimensions, supersingularity can be generalized in several ways. A distinguishing property for elliptic curves is the p-rank, which is 1 for ordinary curves, and 0 for supersingular curves. Similarly, in dimension 2, ordinary abelian surfaces have p-rank 2 and supersingular abelian surfaces have p-rank 0. Equivalently, supersingular abelian surfaces are isogenous, as unpolarized varieties, to a product of supersingular elliptic curves. Abelian surfaces are superspecial whenever they are isomorphic to a product of supersingular elliptic curves as unpolarized varieties. Hence, superspecial varieties are always supersingular, but not the other way around. For Jacobians of hyperelliptic curves, we say that the associated curve is supersingular, or superspecial, if the Jacobian is supersingular or superspecial, respectively.

Supersingularity and Superspeciality Verification of Abelian Surfaces

2.3

7

Characteristic Polynomial of Frobenius

Let A/Fq be an abelian variety of dimension g, then we denote by φA the characteristic polynomial of the q-Frobenius endomorphism π : A → A, also called the Weil polynomial. This polynomial captures essential information for abelian varieties: Q2g 1. We have φA (x) = i=1 (x − αi ), where the αi are the q-Weil numbers with √ |αi | = q, 2. We have φA (1) = |A(Fq )|, 3. Two varieties Q2gA and B are isogenous if and only if φA = φB , 4. If φq (x) = i=1 (x − αi ) is the Weil polynomial of a variety with respect to Q2g the q-Frobenius, then φqk (x) = i=1 (x − αik ) is the Weil polynomial with respect to the q k -Frobenius. For abelian surfaces over Fp , the characteristic polynomial is of the form φA (x) = x4 + ax3 − bx2 + apx + p2 ,

a, b ∈ Z.

(2)

Since −a is the trace of π, by an abuse of language we will refer to a as the trace of A over Fp . Most pertinent to this work is the fact that abelian surfaces are supersingular if and only if they have trace a = 0 and p | b. For a given abelian surface A, there are only two variables, so in general we can explicitly derive φA (x) if we know the evaluation of φA at two values. Bounds. Not any characteristic polynomial φA (x) is possible over Fq . In general, we get the following bounds [26], which we refer to as Weil bounds √ |a| ≤ 4 q,

√ b ≤ 2q − 2 q|a|, 1 b ≥ −2q − a2 . 4

(3) (4) (5)

The Hasse-Weil Interval. One may see from the shape of φA that an abelian √ variety A of dimension g over Fq must have at least ( q − 1)2g points, and at √ most ( q + 1)2g points. This is the Hasse–Weil interval: √ √ ( q − 1)2g ≤ |A(Fq )| ≤ ( q + 1)2g .

(6)

In general, we find that the number of points is always O(q g ) and the width of this interval is O(4gq g−1/2 ). For abelian surfaces over Fp , this gives roughly p2 √ points, and a width of 8 p(p + 1) for the interval. In this work, we will often use the following result, which we refer to as the width-bound argument. Lemma 2.1. Let A be an abelian variety over Fq of dimension g and H ⊆ A(Fq ) with |H| larger than the width of the Hasse–Weil interval. Then |A(Fq )| = n, where n is the unique multiple of |H| in the Hasse–Weil interval.

8

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Proof. The generalized width of the Hasse–Weil interval is √ √ ( q + 1)2g − ( q − 1)2g ≤ 4g · q g−1/2 √ and the lower bound of the Hasse–Weil interval is ( q − 1)2g . Thus, for any subgroup H ⊆ A(Fq ) such that |H| is larger than the width of the Hasse–Weil interval, there is only one unique multiple n of |H| in the Hasse–Weil interval. But this must then be the size of A(Fq ), as |A(Fq )| is in the Hasse–Weil interval, and a multiple of |H|. ⊔ ⊓ Extremal Abelian Varieties. An abelian variety that reaches the lower bound is called minimal, one that reaches the upper bound is called maximal. We say that an abelian variety is extremal if it is either minimal or maximal. Such extremal varieties are special, as the following result shows. Lemma 2.2. If A is an extremal abelian variety over Fp2 , then A is superspecial. Proof. By [22, Theorem 5.3], a maximal abelian variety A over Fp2 is isomorphic to a product of maximal, hence supersingular, elliptic curves over Fp2 . Thus, A is superspecial. The analogous argument holds for minimal abelian varieties. ⊔ ⊓ Twists. An abelian variety that is isomorphic to an abelian surface A over an extension field but not the base field is called a twist of A. Twists are closely related to automorphisms of the variety [40, Ch. X, Thm 2.2]. For Jacobians, any twist is induced by a twist of the associated hyperelliptic curve. Generally, when clear from context, we may refer to the twist At when we refer to the quadratic twist induced by [−1] ∈ Aut(A).

3

Supersingular Abelian Surfaces

The possible orders and group structures of abelian surfaces over Fp , and the existence of an abelian surface with a given group structure, are established in several places throughout the literature. In this section, we list and derive the essential results on which we base our later supersingularity tests. Specializing to dimension g = 2, our approach is broadly as follows: we verify supersingularity of an abelian surface by determining the characteristic polynomial φA (x). Although the order and/or group structure of A(Fp ) does not by itself fix the characteristic polynomial, when combined with the order and/or group structure of either A(Fp2 ) or At (Fp ), the characteristic polynomial φA (x) is fixed. We therefore derive the necessary results on the possible shapes of φA (x), the associated orders, and the group structures of A and its twist.3 3

The notation At in this section refers to the quadratic twist over the respective field, hence may denote different abelian surfaces depending on the base field. Furthermore, ρ refers to the associated twisting isomorphism.

Supersingularity and Superspeciality Verification of Abelian Surfaces

3.1

9

Group Structures of Abelian Surfaces

We explore the possible group structures of abelian surfaces over Fq of characteristic p.4 Surprisingly, they are quite limited, with strong restrictions imposed by both the Weil polynomial and the Weil bounds. The Weil Polynomial. Rybakov [37] showed that the Weil polynomial imposes precise limitations on the possible group structures of principally polarized abelian varieties over Fq . We reformulate this result for abelian surfaces. Lemma 3.1 (Cor. 3.1, [37]). Let A be an abelian surface over Fq with characteristic polynomial of Frobenius φA (x) = x4 + ax3 − bx2 + qax + q 2 with group structure A(Fq ) ∼ = Zn0 × Zn1 × Zn2 × Zn3 , where ni+1 | ni . Write φA (1 − x) as λ0 + λ1 x + λ2 x2 + λ3 x3 + x4 . Then, n3 | λ3 ,

n2 n3 | λ2 ,

n1 n2 n3 | λ1 ,

n0 n1 n2 n3 | λ0 .

Rewriting φA (1 − x) allows us to express the coefficients λi in terms of a and b. Corollary 3.2. Over Fq , given φA (x) = x4 + ax3 − bx2 + qax + q 2 , then λ0 = q 2 + 1 + a(q + 1) − b, λ1 = −a(q + 1) − 2(a − b + 2), λ2 = 3a − b + 6, λ3 = −(a + 4). 3.2

Group Structures of Supersingular Abelian Surfaces

We refine our characterization of group structures to the case of supersingular abelian surfaces over Fp . Whereas supersingular elliptic curves over Fp have only one possible characteristic polynomial and order, and two possible group structures, supersingular abelian surfaces now have five different characteristic polynomials and nine different group structures. Note that in this section we write b for minus the coefficient of x2 divided by p in the characteristic polynomial of Frobenius of a supersingular abelian surface. Lemma 3.3. Let A be an abelian surface over Fp . Then A is supersingular if and only if its characteristic polynomial of Frobenius is of the form φA (x) = x4 − bpx2 + p2 ,

b ∈ {−2, −1, 0, 1, 2}.

Consequently, the possible orders of supersingular abelian surfaces over Fp are   (p + 1)2 if b = −2    2   p + p + 1 if b = −1  2 |A(Fp )| = p +1 if b = 0    p2 − p + 1 if b = 1     (p − 1)2 if b = 2 4

From here onwards, we assume p > 5; there are esoteric abelian surfaces for p ≤ 5.

10

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Proof. The result on φA (x) follows from [21]. The possible orders are then derived from |A(Fp )| = φA (1). ⊔ ⊓ These five types of abelian surfaces will be crucial to many of the results in this work, and we therefore introduce the following notation. Definition 3.4. Let A be a supersingular abelian surface over Fp . When φA (x) = x4 − bpx2 + p2 , we say that A is of type b. Furthermore, when n = |A(Fp )|, i.e., n = p2 − bp + 1 for b ∈ {−2, −1, 0, 1, 2}, then n is a supersingular order. Ignoring the 2-torsion, the group structures of these abelian surfaces are simple: those with parameter b = ±2 are rank 2, whereas for b ∈ {−1, 0, 1} the groups are cyclic. Including the 2-torsion, we get the following more precise result. Theorem 3.5 ([44]). Let A/Fp be a supersingular abelian surface with p > 5. 1. If b ∈ {−1, 0, 1}, then the group structure is cyclic and: (a) if b = −1, then A(Fp ) ∼ = Z/(p2 + p + 1)Z, (b) if b = 0, then A(Fp ) ∼ = Z/(p2 + 1)Z, (c) if b = 1, then A(Fp ) ∼ = Z/(p2 − p + 1)Z, 2. if b = ±2, then the group structure is of rank at least 2 and: (a) if b = −2 and p ≡ 1 mod 4, then A(Fp ) ∼ = (Z/(p + 1)Z)2 , (b) if b = −2 and p ≡ 3 mod 4, then A(Fp ) is isomorphic to (Z/(p+1)Z)2

or

Z/(p+1)Z×Z/( p+1 2 )Z×Z/2Z

or

2 (Z/( p+1 2 )Z×Z/2Z) ,

(c) if b = 2 and p ≡ 1 mod 4, then A(Fp ) is isomorphic to (Z/(p−1)Z)2

or

Z/(p−1)Z×Z/( p−1 2 )Z×Z/2Z

or

2 (Z/( p−1 2 )Z×Z/2Z) ,

(d) if b = 2 and p ≡ 3 mod 4, then A(Fp ) ∼ = (Z/(p − 1)Z)2 . Remark 3.6. By [21], for every prime p > 5 there exists a supersingular Jacobian J with such a group structure, except for the case b = 1 for primes p ≡ 1 mod 6. Note that the reverse of Theorem 3.5 is not true: such group structures exist for non-supersingular Jacobians J /Fp too.5 Using Theorem 3.5, we can derive the group structure up to the rank of the 2-torsion given only the order of a supersingular Jacobian. We derive the rank of the 2-torsion J [2](Fp ) using the factorization of the polynomial defining the associated hyperelliptic curve.6 We say that a non-zero polynomial f ∈ Fp [x] has QN factorization type {d1 , . . . dN } over Fp if it factors as f = c i=1 fi where the factors fi are distinct, monic, irreducible over Fp , and of degree di , and c ∈ Fp is the leading coefficient. 5

For example, for p = 7, the Jacobian J of the hyperelliptic curve defined by y 2 = 4x6 + 3x5 + x4 + 5x3 + 6x2 + 5 satisfies J (Fp ) ∼ = Z/(p2 + 1)Z. 6 This rank is important in later sections, as it decides isotropy behaviour of eigenspaces, see e.g., Section 5.1 and Remark 5.4.

Supersingularity and Superspeciality Verification of Abelian Surfaces

11

Lemma 3.7 ([14]). Let J be the Jacobian over Fp of a genus-2 hyperelliptic curve C defined by y 2 = f (x), with deg f ∈ {5, 6}. Given the factorization QN f (x) = c i=1 fi (x), with fi distinct monic irreducible polynomials over Fp and leading coefficient c, let di denote the degree of fi , so that {d1 , d2 , . . . dN } is the factorization type of f over Fp . Then J [2](Fp ) is isomorphic to – ⟨1⟩, if f is irreducible, or deg(f ) = 6 and f factors as {5, 1}, {3, 3}; – (Z/2Z), if deg(f ) = 6 and f factors as {4, 1, 1}, {3, 2, 1}, {4, 2}, or deg(f ) = 5 and f factors as {4, 1}, {3, 2}; – (Z/2Z)2 , if deg(f ) = 6 and f factors as {3, 1, 1, 1}, {2, 2, 1, 1}, {2, 2, 2}, or deg(f ) = 5 and f factors as {3, 1, 1}, {2, 2, 1}; – (Z/2Z)3 , if deg(f ) = 6 and f factors as {2, 1, 1, 1, 1}, or deg(f ) = 5 and f factors as {2, 1, 1, 1}; – (Z/2Z)4 , if f splits into linear factors. Recall that we generally need two evaluations of φA (x) to reconstruct φA (x), which we use to verify the supersingularity of abelian surface. While a first evaluation is given by the order |A(Fp )| = φA (1), we can get a second evaluation of φA (x) by deriving the order of the twist, where we use that supersingular abelian varieties have trace a = 0. Lemma 3.8. An abelian surface A/Fp has trace a = 0 iff |A(Fp )| = |At (Fp )|. Proof. We get φAt (x) = φA (−x) by [41, Lem. 3]. For φA (x) = x4 + ax3 − bx2 + apx + p2 the equality of φA (1) = |A(Fp )| and φAt (1) = |At (Fp )| implies a + ap = −a − ap, thus a = 0. Conversely, if a = 0, we get φA (x) = φA (−x) = φAt (x). ⊔ ⊓ Remark 3.9. As A[2](Fp ) = At [2](Fp ), we may combine the above result with Theorem 3.5 to derive the stronger result that for supersingular A, as a = 0, we get A(Fp ) ∼ = At (Fp ). 3.3

Uniqueness of Supersingular Orders

From Lemma 3.3, we know that if A/Fp is supersingular, then its order n is of the form n = p2 − bp + 1 for b ∈ {−2, −1, 0, 1, 2}. The converse is (almost) true, except we have to look over Fp2 : if A/Fp is an abelian surface with |A(Fp2 )| = n2 for a supersingular order n, then A is supersingular. The goal of this section will be proving this result, which is a key ingredient in our supersingularity testing. At a high level, our argument is as follows. We first observe that even though for a supersingular order n the equality |A(Fp )| = n can be satisfied by both supersingular and non-supersingular abelian surfaces, for the cases b ∈ {±1, ±2} the equality |A(Fp2 )| = n2 is only satisfied by supersingular abelian surfaces. The case b = 0 is more nuanced: there exist non-supersingular abelian surfaces A with |A(Fp2 )| = (p2 + 1)2 , but such abelian surfaces are never defined over

12

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Fp . More precisely, we show that any abelian surface A/Fp with |A(Fp2 )| = n2 is supersingular. In this section, we often require the Weil polynomial of an abelian surface A over both Fp and Fp2 . When the abelian surface A is clear from context, we write the Weil polynomial over Fp as φp (x) = x4 + ap x3 − bp x2 + ap px + p2 and the Weil polynomial over Fp2 , using q = p2 , as φq (x) = x4 + aq x3 − bq x2 + aq p2 x + p4 . Note that ap , bp and aq , bq denote the (unnormalised) coefficients of φp and φq as displayed, so that A is of type b = bp /p in the sense of Definition 3.4. In the proofs of Lemma 3.10 and Lemma 3.11, it is convenient to work with the x2 -coefficients cp := −bp and cq := −bq . The case b = ±2. Lemma 2.2 resolves the case b = ±2: any abelian surface A with |A(Fp2 )| = (p ± 1)4 is either minimal or maximal, and is thus supersingular (and even superspecial). The case b = ±1. We derive the result from the central requirement that φA (1) = n2 over Fp2 , with n = p2 ± p + 1, together with the Weil bounds. Lemma 3.10. Let n = p2 ± p + 1 and let A be an abelian surface such that |A(Fp2 )| = n2 . Then the Weil polynomial of A over Fp2 is (x2 ± px + p2 )2 = x4 ± 2px3 + 3p2 x2 ± 2p3 x + p4 , and in particular A is supersingular. Moreover, if A is defined over Fp , then A is of type b = ∓1. Proof. We derive the result for n = p2 + p + 1, which requires us to show that aq = 2p and cq = 3p2 . The analogous result can be derived for n = p2 − p + 1 simply by a change of sign in the right places. With q = p2 , the Weil bounds in Eqs. (3) to (5) become |aq | ≤ 4p,

1 cq ≤ 2p2 + a2q , 4

and cq ≥ −2p2 + 2p · |aq |.

As |A(Fp2 )| = n2 = φA (1), we get aq (p2 + 1) + cq = 2p3 + 3p2 + 2p.

(7)

We now derive the two bounds aq ≥ 2p and aq ≤ 2p to conclude that aq = 2p, which directly implies cq = 3p2 . First, by cq ≤ 2p2 + 41 a2q , and substituting cq into Eq. (7), we get 1 2 a + aq (p2 + 1) − (2p3 + p2 + 2p) ≥ 0, 4 q

Supersingularity and Superspeciality Verification of Abelian Surfaces

13

where equality with 0 is reached at aq = 2p and aq = −4p2 − 2p − 4. The bound |aq | ≤ 4p excludes the second branch, so we get 2p ≤ aq ≤ 4p. Then, by cq ≥ −2p2 + 2p|aq | and substituting cq , noticing |aq | = aq as aq ≥ 2p, we get 2paq − 2p2 ≤ 2p3 + 3p2 + 2p − aq (p2 + 1), which can be rewritten to aq ≤ 2p +

p2 . (p + 1)2

This last fraction is always smaller than 1, so as aq is an integer we have that aq ≤ 2p. We conclude that aq = 2p and cq = 3p2 , i.e., bq = −3p2 , as required. Now suppose that A is the base change of an abelian surface over Fp , with Weil polynomial φp . We have that aq = 2cp − a2p ,

cq = c2p − 2a2p p + 2p2 .

(8)

Substituting into aq = 2p and cq = 3p2 , we get a2p (a2p − 4p) = 0. As p > 5, 4p is not a square, so ap = 0 and cp = p and A is of type b = −1. ⊔ ⊓ The case b = 0. This case is most interesting, as for n = p2 + 1 there exist non-supersingular abelian surfaces such that |A(Fp2 )| = n2 , in contrast with the other cases. However, we show that such abelian surfaces are never defined over Fp , except for the supersingular ones. Lemma 3.11. Let n = p2 + 1 and let A be an abelian surface over Fp with |A(Fp2 )| = n2 . Then A is supersingular, and in particular, the Weil polynomial of A over Fp is x4 + p2 . Proof. We denote the Weil polynomial for A over Fp by φp (x) and over Fp2 by φq (x). The goal is to use Lemma 3.3 and show that ap = 0 and p | cp . As |A(Fp2 )| = n2 we get from φq (1) = n2 that aq (p2 + 1) + cq = 2p2 .

(9)

Q Q By φp (x) = (x − αi ) and φq (x) = (x − αi2 ), we have that φp (x)φp (−x) = φq (x2 ). Expanding this out and comparing coefficients, we find that aq = 2cp −a2p and cq = c2p − 2a2p p + 2p2 . This allows us to rewrite Eq. (9) as a2p =

c2p + 2cp (p2 + 1) , (p + 1)2

and so from aq = 2cp − a2p , by expressing everything in terms of cp , we get cp (4p − cp ) aq = . (p + 1)2

(10)

(11)

14

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

First we bound cp . From the Weil bound in Eq. (4) we have cp ≤ 2p + 14 a2p . Together with Eq. (10), we obtain c2p − 2cp (p2 + 4p + 1) + 8p(p + 1)2 ≥ 0. Solving the quadratic in cp , we get that cp ≤ 4p or cp ≥ 2(p2 + 2p + 1). The latter is not possible due to the Weil bounds, so we find that cp ≤ 4p. Furthermore, the right-hand side of Eq. (10) should be positive, which implies that c2p + 2cp (p2 + 1) ≥ 0. Writing as cp (cp + 2p2 + 2) ≥ 0, and noting that cp + 2p2 + 2 ≥ 0 by Eq. (5), we have that cp ≥ 0. Thus, we know 0 ≤ cp ≤ 4p. Using these values for cp in Eq. (11), and noting that aq is an integer, we have aq ∈ {0, 1, 2, 3}. We now show that only aq = 0 is possible. aq = 1: From (p + 1)2 = cp (4p − cp ), we get 2 | cp . But then 1 = aq = 2cp − a2p cannot have a solution, as this requires ap odd and a2p ≡ 3 mod 4, which is impossible. aq = 2: From 2(p + 1)2 = cp (4p − cp ), we get 4 | cp . But then 2 = aq = 2cp − a2p cannot have a solution mod 8. aq = 3: To get an integer solution to the quadratic in cp from Eq. (11), the discriminant needs to be a square. This discriminant is equal to (p − 3)2 − 12 and hence only a square for p = 7. Thus, for p > 7, this case is never possible. For p = 7, the solutions cp = 12, 16 force a non-integer solution for ap in 3 = aq = 2cp − a2p . We conclude that aq = 0 and hence cq = 2p2 by Eq. (9). This is enough to show supersingularity of A, but we can even deduce from Eq. (11) that cp = 0, so that ap = 0 (from aq = 2cp − a2p ), as the case cp = 4p forces a2p = 8p, which can only happen for p = 2. ⊔ ⊓ We summarize the results of this section in the following theorem. Theorem 3.12. Let n = p2 − bp + 1 with b ∈ {−2, −1, 0, 1, 2}. – Assuming b ̸= 0, if A is an abelian surface over Fp or Fp2 such that |A(Fp2 )| = n2 , then A is supersingular. – If b = 0 and A is an abelian surface over Fp such that |A(Fp2 )| = n2 , then A is supersingular. 3.4

Structure theory of m-torsion

Our conclusive supersingularity testing in Section 5 uses the m-Weil pairing to identify the structure of the rational m-torsion, where m is the exponent of A(Fp ). The goal of this section is to show that knowing the structure of A[m] is sufficient to determine the supersingularity of A. To this end, we develop theory on the m-torsion of supersingular Jacobians, and derive the necessary results on the Weil pairing to enable this testing. To determine the full m-torsion degree of A[m], we use the following lemma.

Supersingularity and Superspeciality Verification of Abelian Surfaces

15

Lemma 3.13. Let φ(x) = x4 − bpx2 + p2 and let m be any divisor of p2 − bp + 1. Then φ(x) ≡ (x2 − 1) · (x2 − p2 ) mod m.

Remark 3.14. The minimal polynomial of the Frobenius endomorphism π is squarefree (as π is central in End0 (A), which is semisimple) and divides φ. In particular, for A of type b = ±2 we have π 2 = [±p] on A. Hence, π 2 acts trivially on A[p ∓ 1], so A[p ∓ 1] ⊆ A(Fp2 ). As φ(x) splits completely modulo m, if the roots are distinct modulo ℓ for all primes ℓ | m, then the action of Frobenius on A[m] is diagonalizable, and its order will be the lowest common multiple of the orders of the four eigenvalues ±1, ±p ∈ (Z/mZ)× . Hence, we can derive the full m-torsion degree from the embedding degree of m, and decompose A[m] accordingly. Generically, we get X 2 + X + 1 | X 3 − 1, X 2 + 1 | X 4 − 1 and X 2 − X + 1 | X 6 − 1, which gives embedding degrees 3, 4, and 6 for m-th root of unities where m is the exponent for b-type −1, 0, and 1 respectively. With a slight abuse of notation, for λ ∈ {±1, ±p} we write A[π − λ] = ker(π − λ) ∩ A[m] for the corresponding eigenspace. These are defined over the following fields. Lemma 3.15. Let A over Fp be a supersingular abelian surface of type b and exponent m. If λk ≡ 1 mod m, then A[π − λ] ⊆ A(Fpk ), and if λk ≡ −1 mod m, then A[π − λ] ⊆ At (Fpk )ρ . Furthermore: 1. The eigenspaces of λ = ±1 are A[π − 1] = A(Fp ) and A[π + 1] = At (Fp )ρ . 2. The eigenspaces of ±p are, per type b: (a) b = 2: A[π − p] = A[π − 1] = A(Fp ) and A[π + p] = A[π + 1] = At (Fp )ρ . (b) b = −2: A[π − p] = A[π + 1] = At (Fp )ρ and A[π + p] = A[π − 1] = A(Fp ). ′ (c) b = 0: A[π − p] = At (Fp2 )ρ and A[π + p] = At (Fp2 )ρ . ′ (d) b = −1: A[π − p] = A(Fp3 ) and A[π + p] = At (Fp3 )ρ . (e) b = 1: A[π − p] = At (Fp3 )ρ and A[π + p] = A(Fp3 ). Proof. For P ∈ A[π−λ] we have π k P = [λk ]P . If λk ≡ 1 mod m this equals P , so P is fixed by the pk -power Frobenius and hence P ∈ A(Fpk ). If λk ≡ −1 mod m, we have π k P = −P , so P ∈ At (Fpk ). The congruences follow from m | p2 − bp + 1. For b = ±2 we have m ∈ 2 {p ∓ 1, p∓1 2 } by Theorem 3.5, so p ≡ ±1 mod m. For b = 0 we have m = p + 1, 2 2 3 so p ≡ −1 mod m. Finally, for b = ±1 we have m = p ∓ p + 1 dividing p ± 1, hence p3 ≡ ∓1 mod m. The statements for A[π+p] follow from (−p)k = (−1)k pk . ⊔ ⊓ The subgroup generated by these four eigenspaces is almost all of A[m]; the index is a power of 2 or of 3, and is determined by the type b and the group structure of A(Fp ).

16

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Lemma 3.16. Let A be a supersingular abelian surface defined over Fp , of type b and exponent m. Let H = A[π − 1] + A[π + 1] + A[π − p] + A[π + p] ⊆ A[m] be the subgroup generated by the four eigenspaces of Lemma 3.15. Then the index of H in A[m] ∼ = (Z/mZ)4 is as follows: – If b = ±2, then H = A(Fp ) + At (Fp )ρ and  2 ∼  4 if A(Fp ) = (Z/mZ) , 4 m · |A[2](Fp )| = 8 if A(Fp ) ∼ [A[m] : H] = = Z/mZ × Z/ m 2 Z × Z/2Z,  |A(Fp )|2  2 1 if A(Fp ) ∼ = (Z/mZ × Z/2Z) , where the first two cases have m = p ∓ 1 and the third has m = p∓1 2 . – If b = 0, then [A[m] : H] = 8. – If b = −1, then [A[m] : H] = 9 if p ≡ 1 mod 3, and [A[m] : H] = 1 otherwise. – If b = 1, then [A[m] : H] = 9 if p ≡ 2 mod 3, and [A[m] : H] = 1 otherwise. L Proof. Since A[m] = ℓe |m A[ℓe ] and every eigenspace decomposes accordingly, the index of H is the product of the local indices [A[ℓe ] : H ∩A[ℓe ]] over the prime powers ℓe | m. For a given prime factor ℓ, suppose that Q 1, −1, p, −p are pairwise distinct modulo ℓ. By Lemma 3.13 we have φ(x) ≡ λ (x − λ) mod ℓe , and these factors are pairwise L coprime in (Z/ℓe Z)[x] because the differences λ − λ′ are e units. Thus, A[ℓ ] = λ ker(π − λ), where each summand is free of rank 1 over Z/ℓe Z. This implies that the local index at ℓ is 1. The only cases where this fails, i.e., 1, −1, p, −p are not pairwise distinct modulo ℓ, are: b = 0 and ℓ = 2; b = ±1 and ℓ = 3; or b = ±2, where the eigenvalues ±1 and ±p agree (in some order) modulo every ℓ | m. Consider first the case b = ±2. By Lemma 3.15 we have p ≡ ±1 mod m, so A[π − p] and A[π + p] coincide, in some order, with A[π − 1] = A(Fp ) and A[π + 1] = At (Fp )ρ ; thus H = A(Fp ) + At (Fp )ρ . As A(Fp ) ∩ At (Fp )ρ = A[2](Fp ), we have |A(Fp )|2 |A(Fp )| · |At (Fp )| = . |H| = |A[2](Fp )| |A[2](Fp )| Substituting the three group structures of Theorem 3.5 yields the three indices. Consider the case b = 0, where m = p2 +1 and A(Fp ) is cyclic by Theorem 3.5. As p2 ≡ 1 mod 8 we get m ≡ 2 mod 8, so 2 | m and the 2-Sylow subgroup of A(Fp ) is Z/2Z. All four eigenvalues are congruent modulo 2 to 1, so each eigenspace has its 2-part contained in ker(π − 1) ∩ A[2] = A[2](Fp ) ∼ = Z/2Z. So, H ∩ A[2] ∼ = Z/2Z with local index at 2 being 24 /2 = 8; other local indices are 1. In the case b = ±1, we have that m = p2 ∓ p + 1 is odd, and 3 | m if and only if p ≡ ∓1 mod 3. If 3 ∤ m, the index is 1. If 3 | m, then φ(x) ≡ (x − 1)2 (x + 1)2 mod 3. Since A(Fp ) is cyclic, we get ker(π − 1) ∩ A[3] = A[3](Fp ) ∼ = Z/3Z, and likewise ker(π + 1) ∩ A[3] ∼ = At [3](Fp ) ∼ = Z/3Z. Therefore, H ∩ A[3] has order 9 and local index at 3 is 34 /32 = 9. ⊔ ⊓

Supersingularity and Superspeciality Verification of Abelian Surfaces

17

Such a basis of eigenpoints as a subgroup of A[m] is almost symplectic as the following result on their pairing values shows. Lemma 3.17. Let A over Fp be a supersingular abelian surface of exponent m, and let P ∈ A[π − 1], Q ∈ A[π + 1], R ∈ A[π − p], S ∈ A[π + p] be eigenpoints in A[m]. Then em (P, S) and em (Q, R) are of order at most gcd(m, 2), and em (P, Q) and em (R, S) are of order at most gcd(m, p + 1). Proof. Generically, for two eigenpoints D and D′ of eigenvalue λ, λ′ respectively, we may set ζ = em (D, D′ ), and derive constraints on ζ using ′

em (π(D), π(D′ )) = ζ p and em (π(D), π(D′ )) = em (λD, λ′ D′ ) = ζ λ·λ . p −1 For example, this gives as constraints on ζP,Q = em (P, Q) that ζP,Q = ζP,Q and p+1 hence ζP,Q = 1, which implies ζP,Q ∈ µp+1 . Similarly, we get 0 ζP,R = 1,

2p ζP,S = 1,

2p ζQ,R = 1,

0 ζQ,S = 1,

and

2

p +p ζR,S = 1.

Since m and p are coprime, this implies ζP,S ∈ µ2 and ζQ,R ∈ µ2 . For ζR,S , we p+1 can remove a factor p to obtain ζR,S = 1. Thus, em (P, S), em (Q, R) ∈ µgcd(m,2) , and em (P, Q), em (R, S) ∈ µgcd(m,p+1) . ⊔ ⊓ For b = ±2, Lemma 3.17 leaves an ambiguity at 2, as it only determines the pairings between the eigenspaces of ±1 (for b = 2), or within them (for b = −2), up to µ2 . We resolve it using the trace map π + 1, which interacts with the Weil pairing as follows. Note that we will work with n = p ∓ 1 rather than with the exponent m of A(Fp ), so that statements can be made uniformly over the three group structures (since |A(Fp )| = n2 in all cases). Lemma 3.18. Let A/Fp be a supersingular abelian surface of type b = ±2, and let n = p ∓ 1. Then A(Fp ) ⊆ A[n] ⊆ A(Fp2 ), and (π + 1) A[n] = A(Fp ),

(π − 1) A[n] = At (Fp )ρ .

Moreover, for all R ∈ A[n], Q ∈ A(Fp ) and S ∈ At (Fp )ρ ,
en (π + 1)R, Q = en (R, Q)p+1 ,

en (π − 1)R, S = en (R, S)−(p+1) .

Proof. The exponent of A(Fp ) divides n, so A(Fp ) ⊆ A[n]; the same holds for At , which is again of type b = ±2. By Remark 3.14, A[n] ⊆ A(Fp2 ) and (π − 1)(π + 1) = π 2 − 1 = 0 on A[n]. On A[n], the kernel of π − 1 is A(Fp ). The kernel of π + 1 is At (Fp )ρ that is of order n2 , so (π + 1)A[n] has order n4 /n2 = n2 . It is contained in ker(π − 1) = A(Fp ), thus (π + 1)A[n] = A(Fp ). Similarly, (π − 1)A[n] = At (Fp )ρ . Moreover, en (πR, πT ) = en (R, T )p for all R, T ∈ A[n]. If Q ∈ A(Fp ), then en (πR, Q) = en (πR, πQ) = en (R, Q)p , and multiplying by en (R, Q) gives the first identity. For S ∈ At (Fp )ρ , we have πS = −S giving the second identity. ⊔ ⊓

18

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Table 3: Properties of supersingular abelian surfaces A/Fp by b-type, for p > 5. Here m denotes the exponent of A(Fp ), the embedding degree is the smallest k with m | pk − 1, and the full m-torsion field is the smallest extension of Fp over which A[m] is defined. b

Group structure A(Fp )

|A(Fp )|

Emb. deg. of m

Full m-torsion

−2

(Z/(p + 1)Z)2 or Z × Z/2Z or Z/(p + 1)Z × Z/ p+1 2 2 (Z/ p+1 Z × Z/2Z) 2

(p + 1)2

2

Fp2

−1

Z/(p2 + p + 1)Z

p2 + p + 1

3

Fp6

0

Z/(p2 + 1)Z

p2 + 1

4

Fp4

1

Z/(p2 − p + 1)Z

p2 − p + 1

6

Fp6

(p − 1)2

1

Fp2

2

2

(Z/(p − 1)Z) or Z × Z/2Z or Z/(p − 1)Z × Z/ p−1 2 2 (Z/ p−1 Z × Z/2Z) 2

An overview of these structural results is given in Table 3. Remark 3.19. For b = 1, a Jacobian with the corresponding group structure does not exist when p ≡ 1 (mod 6), as shown by Howe, Nart, and Ritzenthaler [21]. Furthermore, when p ≡ 1 mod 4, all three rows for b = −2 are equivalent, as p+1 2 is odd, and when p ≡ 3 mod 4, all three rows for b = 2 are equivalent, as p−1 2 is odd. 3.5

Superspecial Jacobians

Thus far, we have only considered the supersingular case; it is also important to understand the superspecial case, particularly for cryptographic applications. In this section, we focus in particular on Jacobians, as we will appeal to results about the associated genus-2 hyperelliptic curve, and products of supersingular elliptic curves are by definition superspecial. To show that a Jacobian is superspecial, we require two results from the literature that allow us to reduce to determining a simpler property: minimality or maximality. Essentially, superspecial Jacobians are always related to the supersingular varieties that reach the minimal or maximal number of points. The first result we need is Lemma 2.2, which relates maximality to superspeciality for abelian varieties. The next result connects this to curves. Lemma 3.20 (Thm. 2.6, [23]). Let C be a curve over Fp2 . Then C is superspecial if and only if C has a twist over Fp2 that is minimal or maximal.

Supersingularity and Superspeciality Verification of Abelian Surfaces

19

Remark 3.21. There is a significant difference in behaviour between Jacobians over Fp of order (p + 1)2 , and Jacobians over Fp2 of order (p + 1)4 . Namely, the first category contains both ordinary and supersingular Jacobians, and only the supersingular Jacobians of order (p + 1)2 become maximal, i.e., of order (p + 1)4 over Fp2 . The second category only contains supersingular, and by Lemma 2.2 superspecial, Jacobians. From this, we get a simple criterion for superspeciality of principally polarized Jacobians: a Jacobian J is superspecial if and only if the associated curve C is superspecial. Lemma 3.20 shows that this implies a maximal or minimal twist. We derive our main criterion for superspeciality as a direct corollary to Lemma 3.20. Corollary 3.22. Let A be a principally polarized abelian surface over Fp or Fp2 . Then A is superspecial if and only if A has a twist over Fp2 that is minimal or maximal. We refer to non-minimal or non-maximal superspecial Jacobians as twisted superspecial Jacobians to emphasize the dichotomy between minimal and maximal superspecial Jacobians and those Jacobians that require a twist to become minimal or maximal. For the quadratic twist J t , we know that φJ t (x) = φJ (−x), and this equals φJ (x) for superspecial Jacobians over Fp , as in the proof of Lemma 3.8. Hence, twisted superspecial Jacobians must arise from non-trivial twists over a larger extension field. Using two known results, we identify curves with additional twists and the effect on characteristic polynomials. Lemma 3.23 (Ch. X, Thm 2.2(c), [40]). Let C be a curve over a field k and let Gk denote the Galois group Gal(k/k). Then there is a bijection Twists(C/k) → H 1 (Gk , Aut(C)). We can therefore associate to any twist C ′ of C some automorphism σ ∈ Aut(C), and we will denote C ′ by C σ in such a case. Luckily, for a hyperelliptic curve C of genus 2, there are not too many options for Aut(C): We always have [−1] ∈ Aut(C), so we instead analyse the reduced automorphism group RA(C) := Aut(C)/⟨−1⟩. Bolza [6] shows that there are only 7 options for RA(C). For every option of RA(C), Cardona [9] computed the corresponding cohomology group. Recall that we are mostly interested in the change of the characteristic polynomial φC σ (x) in terms of φC (x), which is exactly what Howe, Nart, and Ritzenthaler [21] have described for minimal and maximal curves over Fp2 . Lemma 3.24 (Prop. 13.1, [21]). Let C be a minimal or maximal supersingular curve over Fp2 , so that π acts as [±p]. Let C σ be a twist of C induced by σ ∈ Aut(C), and let fσ denote the characteristic polynomial of σ. Then φC σ (x) = p4 · fσ (x/ ± p).

20

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Using [21, Table 4], we know all possible minimal polynomials of automorphisms of genus-2 curves. and may compute which possible automorphisms twist a curve of type b = ±2 into a curve of type b ∈ {−1, 0, 1}. We describe the non-trivial automorphisms τ and ρ on genus-2 hyperelliptic curves in Appendix A. Proposition 3.25. Let C be a hyperelliptic curve of genus 2 over Fp of type b = ±2 so that C/Fp2 is extremal. Then – if τ ∈ RA(C), the twist C τ over Fp2 has fτ = (x2 +1)2 , so is the base change of a type b = 0 surface over Fp , – if ρ ∈ RA(C), the twist C ρ over Fp2 has fρ = (x2 + x + 1)2 , so it is the base change of a type b = ±1 surface over Fp . From this we find that twisted superspecial curves and Jacobians are very sparse, as in general Jacobians with non-trivial automorphisms beyond [−1] are sparse in the 3-dimensional space of generic Jacobians: – τ ∈ RA(C) implies RA(C) ∼ = Z2 × Z2 , RA(C) ∼ = S4 , or RA(C) ∼ = D2×6 which implies J is (2, 2)-isogenous to a square E 2 for some curve E [19]. This describes a 1-dimensional space of Jacobians. – ρ ∈ RA(C) implies RA(C) ∼ = S3 , RA(C) ∼ = S4 , or RA(C) ∼ = D2×6 , which implies J is (2, 2)-isogenous to a product E × E ′ for some curves E and E ′ that are 3-isogenous [19]. This describes a 1-dimensional space of Jacobians. Thus, we can very quickly identify the twisted superspecial Jacobians by their automorphism groups, which can be computed efficiently directly from the curve equation or most sets of invariants, such as Igusa or Clebsch invariants [6, 38]. Summarizing, we get the following. Theorem 3.26. Let J be the Jacobian over Fp of a hyperelliptic curve C of genus 2. Then J is superspecial if and only if – J is of type b = ±2, – J is of type b = ±1 and RA(C) is equal to S3 , S4 , or D2×6 , – J is of type b = 0 and RA(C) is equal to Z2 × Z2 , S4 , or D2×6 . For completeness, we perform the same computation and characterization of twisted superspecial Jacobians over Fp2 in Appendix B.

4

Probabilistic Supersingularity Testing

In this section, we derive three main results. First, in Section 4.1, we derive a simple test for minimality or maximality of abelian varieties of any dimension g. Second, we use this result to derive a simple algorithm for superspeciality testing of Jacobians over Fp and Fp2 in Section 4.2. Third, in Section 4.4, we specialize to Jacobians over Fp and derive a Monte Carlo algorithm for supersingularity testing of Jacobians J over Fp (Algorithm 4). This last algorithm requires two specific results about Jacobians over Fp :

Supersingularity and Superspeciality Verification of Abelian Surfaces

21

1. Theorem 3.12: A supersingular Jacobian over Fp has order n = p2 − bp + 1 for b ∈ {−2, −1, 0, 1, 2}. Any abelian surface over Fp such that |A(Fp2 )| = n2 is supersingular. 2. Theorem 4.7: For an abelian surface over Fp , we can verify |A(Fp2 )| = n2 by verifying [n]P = 0 for random points P . This has only a negligible chance of false positives using a generalization of Sutherland’s argument using the width of the Hasse–Weil interval. We proved the first result in Section 3.3, which allows us to derive the second result in Section 4.3. Together, these give Algorithm 4. 4.1

Minimality and Maximality Testing for Varieties

In this section, we give an algorithm to verify minimality and maximality of abelian varieties of any dimension g over Fp or Fp2 , by generalising the algorithm for our key example (Algorithm 1) using Lemma 2.1. Similar arguments are used in later sections when we derive supersingularity tests for Jacobians over Fp , and superspeciality tests over Fp and Fp2 . Algorithm 2 Let A be an abelian variety of dimension g over Fq with q = p or $

p2 . Let P ← − A(Fp2 ). – If [p]P = ±P , return true. – Otherwise, return false Algorithm 2 checks whether A is minimal or maximal, and thus whether it is superspecial by Lemma 2.2. The failure probability is again negligible, as the following result shows. Theorem 4.1. Algorithm 2 runs in O(log p) time and returns true for any minimal or maximal abelian variety over Fq . For any non-extremal variety of dimension g, Algorithm 2 returns true with probability at most O(p−1 ). Proof. This follows directly from Lemma 2.1. We detail the maximal case; the minimal case follows similarly. For the subgroup H = A[p + 1](Fp2 ), we get that |H| divides (p + 1)2g , and thus if |H| is larger than 4gp2g−1 , then |A(Fp2 )| = (p + 1)2g and A is maximal, and therefore superspecial. So, for any non-maximal A, the subgroup H is smaller than O(4gp2g−1 ). The probability of sampling a point P ∈ A(Fp2 ) such that [p + 1]P = 0 is equal to the probability of sampling a point in H. In the non-maximal case we therefore have that the probability is 4gp2g−1 |H| ≤ = O(p−1 ). |A(Fp2 )| (p − 1)2g ⊔ ⊓

22

4.2

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Superspeciality Testing for Jacobians

By combining Theorem 4.1 with Corollary 3.22, we get the following simple test for superspeciality for Jacobians of any dimension g over both Fp and Fp2 , as long as g is small compared to p. Algorithm 3 Let J be a Jacobian of dimension g of a curve C over Fq with q = p or p2 . Let Aut(C) be the geometric automorphism group of C (i.e., automorphisms defined over Fp ). For each σ ∈ Aut(C): – Let J σ be the Jacobian of the twist C σ of C by σ over Fp2 . $

– Sample P ← − J σ (Fp2 ). – If [p]P = ±P , return true. If no J σ passes the [p]P = ±P test, return false. Algorithm 3 checks that J or any of its twists is maximal or minimal, which shows superspeciality by [22, Thm. 5.3]. Using Theorem 4.1, we show that the failure probability is again negligible. Theorem 4.2. Let p > g + 1. Then Algorithm 3 runs in O(g log p) time and returns true for any superspecial Jacobian. For any non-superspecial Jacobian of dimension g, Algorithm 3 returns true with probability at most O((g − 1) · p−1 ). Proof. By Theorem 4.1, the probability of passing the [p]P = −P test for any non-maximal Jacobian is bounded by O(p−1 ). By Hurwitz’s automorphisms theorem, we get | Aut(C)| ≤ 84(g − 1), as long as p > g + 1 [36]7 and we can bound the number of twists we have to visit by the size of Aut(C) by Lemma 3.23. Each test costs O(log p) group operations, giving a total cost of O(g log p). Furthermore, if the [p]P = −P test succeeds on any twist J σ , then J is superspecial and a union bound over the twists gives the stated probability O((g − 1) · p−1 ). The analogous argument holds replacing maximal with minimal and [p]P = −P with [p]P = P . ⊔ ⊓ 4.3

Probabilistic Order Determination over Fp

We now generalize Sutherland’s probabilistic argument to cases beyond minimal or maximal abelian surfaces. If a uniformly random point P ∈ A(Fq ) on an abelian variety A of dimension g over Fq satisfies [n]P = 0A for some n ∈ N, what can we say about the order of A(Fq )? We answer this question for abelian surfaces over Fp in Theorem 4.7: for the supersingular orders n = p2 − bp + 1, if [n]P = 0A for a random P ∈ A(Fp ) and [n]Q = 0A for a random Q ∈ At (Fp ), then it is extremely likely that A is supersingular (at least for large p). A special case is b = −2, which only needs a single test [n]P = 0A for a random P ∈ A(Fp ) to verify supersingularity. We derive these results case by case, mainly using Theorem 3.12. We rely heavily on Corollary 3.2.8 7

Roquette [36] shows this result for all curves except one, but the exceptional curve is itself a superspecial curve. 8 As in Section 3.3, the arguments here use only random sampling and scalar multiplication, so no polarization is assumed in this subsection.

Supersingularity and Superspeciality Verification of Abelian Surfaces

23

The extremal cases b = ±2. Interestingly, these differ for b = −2 and b = 2. The former needs only 1 point, whereas the latter needs 2. In both cases, we multiply by p ± 1 instead of the supersingular order (p ± 1)2 . Lemma 4.3. Let A be an abelian surface over Fp . Let P be a random point on A(Fp ). The probability that [p + 1]P = 0 is – 1, if A is supersingular of type b = −2, – O(p−1/2 ), otherwise. Proof. Let m = p+1. The probability to sample a point P with [m]P = 0 equals P :=

|A(Fp )[m]| . |A(Fp )|

Let h0 , . . . , h3 ∈ N be such that A(Fp )[m] ∼ = Zh0 × Zh1 × Zh2 × Zh3 and hi+1 | hi . From Eq. (1), h3 | h2 | 2, and we have h1 | h0 | p + 1 and h1 | λ0 , h1 | λ1 . Since λ0 = (p + 1)(p − 1 + ap ) + 2 − bp and λ1 = −ap (p + 1) − 2ap − 2(2 − bp ), this implies h1 | 2ap . √ Let W = 8 p(p + 1) denote the width of the Hasse–Weil interval over Fp . If h0 h1 ≤ W , then |A(Fp )[m]| = h0 h1 h2 h3 ≤ 4W , and therefore √
32 p(p + 1) 4W P≤ √ = = O p−1/2 . √ 4 4 ( p − 1) ( p − 1) √ Suppose instead that h0 h1 > W . If ap ̸= 0, then h1 ≤ 2|ap | ≤ 8 p by Eq. (3), √ so that h0 h1 ≤ 8 p(p + 1) = W , a contradiction. Hence, ap = 0. Now A(Fp ) contains a subgroup isomorphic to Zh0 ×Zh1 , whose order exceeds W and divides (p + 1)2 . By Lemma 2.1, |A(Fp )| = (p + 1)2 and so bp = −2p. Therefore, A is supersingular of type b = −2 and P = 1. ⊔ ⊓ Lemma 4.4. Let A be an abelian surface over Fp . The probability that [p−1]P = 0 for a random P ∈ A(Fp ) and [p − 1]Q = 0 for a random Q ∈ At (Fp ), is – 1, if A is supersingular of type b = 2, – O(p−1/2 ), otherwise. Proof. Let G = A[p − 1](Fp ) and H = At [p − 1](Fp ) with twisting isomorphism ρ : At → A. Then S = ⟨G, H ρ ⟩ is a subgroup of A(Fp2 ) whose order divides #A[p − 1] = (p − 1)4 . By the width-bound argument, if |S| ≥ 8(p3 + p), then |A(Fp2 )| = (p − 1)4 , which implies A is minimal, and hence superspecial by Lemma 2.2. In particular, it is of type b = 2 as this is the only Fp -type to lift to a minimal abelian surface over Fp2 . Thus, in the non-supersingular case we have |S| ≤ 8(p3 + p). Since G and H share only the 2-torsion, of size at most 16, and |S| = |G| · |H|/|G ∩ H|, then |G| · |H| ≤ 16 · |S| ≤ 27 · p3 + 27 · p, so at least one of |G| or |H| is smaller than 27/2 · p3/2 + ϵ. ⊔ ⊓

24

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Remark 4.5. We stress that the situation for n = p − 1 is significantly different from the situation for n = p + 1. Indeed, there exist ordinary abelian surfaces A/Fp such that [p − 1]A(Fp ) = 0. An example is given by the Jacobian JC over Fp , where p = 73, for the hyperelliptic curve C : y 2 = x6 + 68x5 + 41x4 + 31x3 + 17x2 + 11x + 51, whose rational group JC (Fp ) is isomorphic to JC (Fp ) ∼ = Z/12 × Z/12 × Z/6 × Z/6. Crucially, the proof of Lemma 4.3 uses the shape of the Weil bounds (Eq. (3)) to make the probability for non-zero a values negligible; similar arguments cannot be repeated for p − 1. The cyclic cases b = 0, ±1. All three cases are very similar. We show this for n = p2 + p + 1, the other cases follow mutatis mutandis. Lemma 4.6. Let A be an abelian surface over Fp and let n = p2 − bp + 1 with b ∈ {−1, 0, 1}. The probability that [n]P = 0 for a random P ∈ A(Fp ) and [n]Q = 0 for a random Q ∈ At (Fp ), is – 1, if A is supersingular of type b = 0, ±1, – O(p−1/2 ), otherwise. Proof. Let H = A[n](Fp ) and G = At [n](Fp ). These groups do not share points beyond the 2-torsion. We again look at S = ⟨H, Gρ ⟩, where ρ is the twisting isomorphism. Let gcd(n, p2 − 1) = d ∈ {1, 2, 3}. By Eq. (1), beyond the 2-torsion or 3-torsion, the rank of A[n](Fp2 ) is at most 2, so |S| divides d2 n2 . Suppose first that d = 1 so that |S| divides n2 . By the width-bound argument, |S| ≥ 8(p3 + p) implies |A(Fp2 )| = n2 , hence A is supersingular by Theorem 3.12. If d = 2 or 3, then we replace S by its prime-to-d part, which has order dividing n2 , and the same argument applies (with the probability bound only losing a constant factor of at most 81). We conclude that either |S| ≥ 8(p3 + p) hence A is supersingular, or |S| ≤ 8(p3 + p) and so the [n]P = 0 test succeeds on both A and At with probability O(p−1/2 ), similarly as in the proof of Lemma 4.4. ⊔ ⊓ General Theorem. We summarize the results in this section in the following theorem, which follows directly from Lemmas 4.3, 4.4 and 4.6. Theorem 4.7. Let n = p2 − bp + 1 for b ∈ {±1, 0}, and n = p ± 1 for b = ∓2. Let A be an abelian surface over Fp , P be a random point of A(Fp ) and Q be a random point of At (Fp ). Then, – if b = −2, the probability that [n]P = 0 is 1 if A is supersingular, and O(p−1/2 ) otherwise. – if b ∈ {−1, 0, 1, 2}, the probability that [n]P = 0 and [n]Q = 0 is 1 if A is supersingular, and O(p−1/2 ) otherwise.

Supersingularity and Superspeciality Verification of Abelian Surfaces

25

Algorithm 4 IsSupersingular Input: An abelian surface A defined over Fp . Output: A boolean indicating whether A is supersingular. If true, we also return |A(Fp )|. $

1: P ← − A(Fp ) \ (A[2] ∪ A[3]) $

2: Q ← − At (Fp ) \ (At [2] ∪ At [3]) 3: R ← [p]P 4: if R = −P then 5: return true, (p + 1)2 6: if R = P then 7: S ← [p]Q 8: if S = Q then 9: return true, (p − 1)2

4.4

10: T = [p]R 11: if T = −P then 12: n ← p2 + 1 13: else if T + P = ±R then 14: n ← p2 ∓ p + 1 15: else 16: return false 17: if [n]Q = 0 then 18: return true, n 19: return false

Supersingularity Testing for Abelian Surfaces over Fp

Based on Theorem 4.7, we derive a simple algorithm to verify supersingularity for abelian surfaces over Fp in IsSupersingular. Theorem 4.8. Algorithm 4 runs in O(log p) time and returns true for any supersingular abelian surface. For any non-supersingular abelian surface, Algorithm 4 returns true with probability O(p−1/2 ). Proof. As multiplication-by-p and random sampling can be performed in O(log p) time, Algorithm 4 terminates in O(log p). Correctness and probability bounds follow directly from Theorem 4.7, as long as we exclude 2- or 3-torsion. Although cryptographically such torsion occurs with negligible probability, their exclusion ensures that Algorithm 4 never misclassifies a supersingular surface.9 ⊔ ⊓ The probability that IsSupersingular returns true when A is ordinary is negligible when p is large. For example, primes p in isogeny-based cryptography are often of size 2λ bits, making the failure probability of IsSupersingular roughly 2−λ where λ is the security parameter, typically λ ∈ {128, 192, 256}. Remark 4.9. It is crucial that the points sampled in Algorithm 4 are uniformly random, otherwise an adversary may always find specific points on specific abelian surfaces that allow an ordinary abelian surface to pass this test. For validation purposes in cryptographic applications, we must therefore assume that an adversary may choose the abelian surface, but not the randomness. Remark 4.10. We stress that the use of the twist allows the full algorithm to work over Fp instead of Fp2 . Although this doesn’t affect asymptotic cost estimates, this significantly affects real-world performance. 9

For example, as gcd(p2 + p + 1, p − 1) = 3 when p ≡ 1 mod 3, such points could misclassify a supersingular Jacobian of type b = −1 as one of type b = 2.

26

5

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Conclusive Supersingularity Testing over Fp

In this section, we discuss conclusive variants of supersingularity testing for abelian surfaces over Fp , in contrast to the probabilistic methods from Section 4, as some applications may require proof that the Jacobian is supersingular. Similarly, for small characteristics p, Algorithm 4 may have a non-negligible failure rate, and conclusive testing ensures certainty. A naı̈ve approach simply verifies the explicit order of points P ∈ J (Fp ) and Q ∈ J t (Fp ), as a generalization of [12, Alg. 1], using a product tree for additional efficiency. As shown in [31] for elliptic curves, the use of pairings significantly improves this method. We generalize [31, Alg. 5] to Jacobians of genus-2 curves. Due to the existence of isotropic subgroups for g > 1, this generalization is nontrivial and requires a precise understanding of isotropy conditions on J (Fp ), explored in Sections 5.1 and 5.2 using results from Section 3.4. We furthermore analyze the requirements of discrete logarithms in µp+1 in verifying supersingularity. Lastly, in Section 5.4, we discuss a specialized variant for Jacobians where 2f divides the exponent for a large power of f , common in cryptographic applications, which allows a significant speed-up [8, Alg. 2]. 5.1

Isotropy on Supersingular Abelian Surfaces of type b = ±2

For the conclusive supersingularity verification, we will perform specific pairings in A[m] for specific values of m ∈ Z>0 . Depending on the isotropy conditions of these subgroups, the resulting pairing can be computed over Fpk or Fp2k where k is the embedding degree of m. We prove this case by case per b-type, starting with b = ±2, where we have a large rank-2 subgroup of A[m], before we discuss the cyclic cases b ∈ {−1, 0, 1}. Lemma 5.1. Let A be a supersingular abelian surface over Fp of type b = 2 and let m = p − 1 or m = p−1 2 be the exponent of A(Fp ) and let n = p − 1. (i) The subgroup generated by the eigenspaces A[π − 1] ⊆ A(Fp ) and A[π + 1] ⊆ At (Fp )ρ is of index 4 in A[m] ⊆ A(Fp2 ) if A(Fp ) ∼ = (Z/mZ)2 , of index 8 if m A(Fp ) ∼ = Z/mZ×Z/ 2 Z×Z/2Z, and of index 1 if A(Fp ) ∼ = (Z/mZ×Z/2Z)2 . (ii) For every Q ∈ A(Fp ) of even order k, there exists P ∈ A(Fp ) such that en (P, Q) has order k/2. Remark 5.2. Note that, according to Theorem 3.5, p ≡ 3 mod 4 implies that the exponent is always m = p − 1, whereas when p ≡ 1 mod 4 both m = p − 1 and m = p−1 2 can happen. Proof. (i) This follows directly from Theorem 3.5 and Lemma 3.16. (ii) As p + 1 ≡ 2 (mod n), Lemma 3.18 gives en ((π + 1)R, Q) = en (R, Q)2 for all R ∈ A[n] and Q ∈ A(Fp ). Let Q ∈ A(Fp ) have even order k. By nondegeneracy of en on A[n], the homomorphism en (·, Q) : A[n] → µn has image µk and so there is R ∈ A[n] with en (R, Q) of order k. Then P = (π + 1)R ∈ A(Fp ) satisfies that en (P, Q) = en (R, Q)2 has order k/2. ⊔ ⊓

Supersingularity and Superspeciality Verification of Abelian Surfaces

27

Lemma 5.1 shows that abelian surfaces of type b = 2 are as non-isotropic as possible, except for the 2-torsion. The case b = −2 is the exact opposite. Lemma 5.3. Let A be a supersingular abelian surface over Fp of type b = −2 and let m = p + 1 or m = p+1 2 be the exponent of A(Fp ). (i) The subgroup generated by eigenspaces A[π − 1] ⊆ A(Fp ) and A[π + 1] ⊆ At (Fp )ρ is of index 4 in A[m] ⊆ A(Fp2 ) if A(Fp ) ∼ = (Z/mZ)2 , of index 8 if m ∼ A(Fp ) = Z/mZ×Z/ 2 Z×Z/2Z, and of index 1 if A(Fp ) ∼ = (Z/mZ×Z/2Z)2 . t ρ (ii) The pairing en is trivial on A(Fp ) and on A (Fp ) . (iii) The pairing A(Fp ) × At (Fp ) → µn ,

(P, Q) 7→ en (P, Qρ ),

has left kernel A[2](Fp ) and right kernel At [2](Fp ). (iv) Let P1 , P2 ∈ A(Fp ) and Q1 , Q2 ∈ A
t (Fp ), let ζ be a primitive n-th root of unity, and let M = logζ en (Pi , Qρj ) i,j over Z/nZ. Then |im M | ≥

|⟨P1 , P2 ⟩| · |⟨Q1 , Q2 ⟩| . 4n2

Proof. (i) This follows directly from Theorem 3.5 and Lemma 3.16. (ii) Write G = A(Fp ) = A[π − 1] and Gt = At (Fp )ρ = A[π + 1]. As p + 1 ≡ 0 (mod n), Lemma 3.18 gives en ((π + 1)R, Q) = 1 for all R ∈ A[n] and Q ∈ G, and en ((π − 1)R, S) = 1 for all R ∈ A[n] and S ∈ Gt . Since (π + 1)A[n] = G and (π − 1)A[n] = Gt , both G and Gt are isotropic. (iii) Since G is isotropic of order n2 in A[n], we have that G = G⊥ , and similarly for Gt . Thus, a point P ∈ G lies in the left kernel if and only if P ∈ Gt , i.e., P ∈ G ∩ Gt = A[2](Fp ). By symmetry, the right kernel is At [2](Fp ). (iv) Write H = ⟨P1 , P2 ⟩ ⊆ G and H t = ⟨Qρ1 , Qρ2 ⟩ ⊆ Gt . The image of M is the image of the homomorphism H → Hom(H t , µn ), P 7→ en (P, ·). This is a composition of maps H → Hom(Gt , µn ) with the restriction Hom(Gt , µn ) → Hom(H t , µn ). The first map has kernel H ∩ A[2](Fp ) = H[2] by (iii). The order of the kernel is therefore at most 4 (since H is generated by two elements), and the image has order at least |H|/4. The restriction map has kernel of order [Gt : H t ] = n2 /|H t |. Hence, |im M | ≥ |H| · |H t |/(4n2 ). ⊔ ⊓ Remark 5.4. Which of the three cases in (i) of Lemma 5.1 and Lemma 5.3 applies is governed by the 2-rank of A(Fp ) alone: by the index formula of Lemma 3.16, the three group structures listed there are precisely those of 2-rank 2, 3 and 4, giving index 4, 8 and 1 respectively. When A is the Jacobian of a genus-2 curve C : y 2 = f (x), this rank is read off directly from the factorization type of f by Lemma 3.7, so the case distinction costs a single polynomial factorization rather than a group-structure computation. Moreover, Theorem 3.5 forces the 2-rank to be at least 2 when b = ±2, so a factorization type of f of 2-rank 0 or 1 already certifies that J is not supersingular of type b = ±2.

28

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

The proof of supersingularity for the case b = 2 is therefore very efficient: we only need to verify the order of pairing values ζ ∈ Fp , and both the pairing and the verification can be computed over Fp . This is because in this case, the eigenspaces 1 and p, resp. −1 and −p collapse, so that the pairing on A(Fp ) is as non-degenerate as possible. For abelian surfaces of type b = −2 the situation is reversed: for n = p+1, the pairing en is trivial on A(Fp ). Pairings between points of A(Fp ) therefore carry no information, and we instead pair points of A(Fp ) with points of At (Fp )ρ . A single pairing en (P, Qρ ) of order k only shows that A(Fp ) and At (Fp ) contain cyclic subgroups of order k, which is too small for the width-bound argument. We therefore take P1 , P2 ∈ A[n](Fp ) and Q1 , Q2 ∈ At [n](Fp ) and compute the four pairings ζi,j = en (Pi , Qρj ). We can compute a matrix M = (logζ ζi,j ) with discrete logarithms in µn 10 , and then determine the size of its image. By Lemma 5.3(iv), points generating large subgroups of A(Fp ) and At (Fp ) give a large image for each of the three possible group structures. √ Corollary 5.5. Let A be an abelian surface over Fp . Write W = 8 p(p + 1), the width of the Hasse–Weil interval over Fp . – Let n = p−1, and let P1 , P2 ∈ A[n](Fp ) and Q1 , Q2 ∈ At [n](Fp ). If en (P1 , P2 ) and en (Q1 , Q2 ) have orders k, k ′ with k 2 , k ′2 > W , then A is supersingular of type b = 2. – Let n = p+1, let ζ be a primitive n-th root of unity, and let P1 , P2 ∈ A[n](Fp ) and Q1 , Q2 ∈ At [n](Fp ). Let ζi,j = en (Pi , Qρj ), where ρ is the twisting isomorphism. If the matrix M = (logζ ζi,j )i,j over Z/nZ satisfies |im M | > W , then A is supersingular of type b = −2. Conversely, let A be supersingular of type b = ±2 and let n = p ∓ 1. For p large enough, there exist P1 , P2 ∈ A(Fp ) and Q1 , Q2 ∈ At (Fp ) satisfying the corresponding condition above. Proof. First let n = p − 1. If en (P1 , P2 ) has order k then |⟨P1 , P2 ⟩| ≥ k 2 > W . Moreover, |⟨P1 , P2 ⟩| divides n2 , so |A(Fp )| = (p − 1)2 by Lemma 2.1. The same argument applied to Q1 , Q2 gives |At (Fp )| = (p − 1)2 . It follows that A is supersingular of type b = 2. Now let n = p + 1. We have that |im M | ≤ |⟨P1 , P2 ⟩| and, as the images of M and M T have the same size, we have |im M | ≤ |⟨Qρ1 , Qρ2 ⟩| = |⟨Q1 , Q2 ⟩|. Both orders divide n2 = (p + 1)2 and (by hypothesis) |im M | > W , so Lemma 2.1 gives |A(Fp )| = |At (Fp )| = (p + 1)2 . For the converse, note that by Theorem 3.5, each of the three possible group structures of A(Fp ) contains a subgroup generated by two elements of order at least n2 /4, and the same holds for At (Fp ) ∼ = A(Fp ). Moreover, A(Fp ) contains a point of order at least n/2. Let A be of type b = 2, so n = p−1, and let Q ∈ A(Fp ) be of maximal order k0 ∈ {n, n/2}. By Lemma 5.1(ii), there is P ∈ A(Fp ) with 10

For most applications in isogeny-based cryptography, smoothness of p + 1 is a common assumption, thus discrete logarithms are efficient.

Supersingularity and Superspeciality Verification of Abelian Surfaces

29

en (P, Q) of order k = k0 /2 ≥ n/4, and similarly on At of order k ′ ≥ n/4. Now
2 k 2 ≥ p−1 > W for p > 218 . A similar argument holds for type b = −2. If 4 moreover A(Fp ) ∼ = (Z/nZ)2 , which by Remark 5.4 can be read off from the 2rank of A(Fp ), then any bases give k = k ′ = n/2 for b = 2, resp. |im M | ≥ n2 /4 for b = −2 by Lemma 5.3(iv), and the conditions hold for p > 210 . ⊔ ⊓ Remark 5.6. The converse statement ensures that such a test passes for supersingular surfaces. For cryptographic applications, primes always satisfy these bounds as they are in the range of hundreds of bits. In both cases (b = ±2), product trees and Lucas sequences can be used to speed up the verification [31], and many operations can remain over Fp as both points lie on the same Fp rational Kummer surface. 5.2

Isotropy on Cyclic Supersingular Abelian Surfaces

Due to their cyclic structure, similar pairing-based techniques for abelian surfaces of type b ∈ {−1, 0, 1} would immediately verify the full group structure of A(Fp ) and At (Fp ), i.e., if P ∈ A(Fp ) and Q ∈ At (Fp ) have a pairing of order n, this verifies both A(Fp ) and At (Fp ) have a subgroup of order n. Unfortunately, such pairings will always be trivial, as in general the n-th roots of unity only live in Fp3 , Fp4 or Fp6 . To perform conclusive supersingularity verification, we must therefore extend the field we work in. Lemma 5.7 (The case b = 0). Let A be an abelian surface over Fp of type b = 0 and let m = p2 + 1 be the exponent of A(Fp ). (i) The subgroup generated by the four eigenspaces A[π − 1] ⊆ A(Fp ), A[π + 1] ⊆ ′ At (Fp )ρ , A[π − p], A[π + p] ⊆ At (Fp2 )ρ generate a subgroup of index 8 of the full m-torsion A[m] ⊆ A(Fp4 ). (ii) Let P ∈ A[π − 1] and Q ∈ A[π + 1], then em (P, Q) is trivial. (iii) For any generators P, Q, R, S of the four eigenspaces (see above), the pairings em (P, R) and em (Q, S) have order exactly m/2. Proof. (i) follows from Theorem 3.5 and Lemma 3.16. Write m = 2m′ with m′ odd (possible as p2 ≡ 1 mod 8). As in the proof of Lemma 3.16, A(Fp ) is cyclic and every eigenspace meets A[2] in A[2](Fp ) = ⟨T ⟩ ∼ = Z/2Z. (ii) By Lemma 3.17, em (P, Q) ∈ µ2 , and its value is e2 ([m′ ]P, [m′ ]Q) = e2 (T, T ) = 1. (iii) The same computation gives e2 ([m′ ]P, [m′ ]R) = 1, so em (P, R) has order dividing m′ . For the converse, note that [A[m] : H] = 8 is a power of 2, so H ⊇ A[m′ ] and the four eigenspaces restrict to a basis of A[m′ ] ∼ = (Z/m′ Z)4 . By Lemma 3.17 the pairings em (P, Q), em (P, S), em (Q, R), em (R, S) all have order dividing 2, hence are trivial on m′ -torsion. The Gram matrix of em′ on this basis therefore has only the entries em′ (P, R) and em′ (Q, S) off the diagonal, and non-degeneracy of em′ forces both to be primitive. Thus, em (P, R) has order exactly m′ = m/2, and likewise for em (Q, S). ⊔ ⊓

30

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

The cases b = ±1 have similar issues: here m = p2 ∓p+1 is divisible by 3 exactly when p ≡ ∓1 mod 3, and in that case the eigenvalues 1, −1, p, −p are no longer distinct modulo 3, resulting in pairings of order m/3. However, this will still be enough to give a proof of supersingularity. Lemma 5.8 (The case b = 1). Let A be an abelian surface over Fp of type b = 1 and let m = p2 − p + 1 be the exponent of A(Fp ). (i) The subgroup generated by the four eigenspaces A[π − 1] ⊆ A(Fp ), A[π + 1] ⊆ At (Fp )ρ , A[π − p] ⊆ At (Fp3 )ρ , and A[π + p] ⊆ A(Fp3 ) generate a subgroup of index 9 if p ≡ 2 mod 3, and of index 1 otherwise, of the full m-torsion A[m] ∼ = (Z/mZ)4 ⊆ A(Fp6 ). (ii) Let P ∈ A[π − 1] and Q ∈ A[π + 1]. Then em (P, Q) is trivial or has order 3. (iii) For any generators P, Q, R, S of the four eigenspaces above, the pairings em (P, R) and em (Q, S) have order m/3 or m. Proof. (i) This follows directly from Theorem 3.5 and Lemma 3.16. Note 3 | m if and only if p ≡ 2 mod 3 and m is odd. (ii). Since gcd(m, 2) = 1 and gcd(m, p + 1) ≤ 3 by Lemma 3.17, we get em (P, Q) ∈ µ3 . (iii). Write m = 3e m′ with 3 ∤ m′ . Arguing as in Lemma 5.7(iii), the index in (i) is a power of 3, so the four eigenspaces restrict to a basis of A[m′ ]. By Lemma 3.17, the pairings em (P, Q), em (P, S), em (Q, R), em (R, S) all have order dividing 3, hence are trivial on m′ -torsion. The non-degeneracy of em′ forces em′ (P, R) to be primitive. The 3-part is not determined: modulo 3 the eigenvalues ±1, ±p collapse in pairs, and e3 need not vanish between the two resulting order 3 eigengroups.11 If 3 ∤ m, then e = 0 and the order is m. A similar argument holds for em (Q, S). ⊔ ⊓ Lemma 5.9 (The case b = −1). Let A be an abelian surface over Fp of type b = −1 and let m = p2 + p + 1 be the exponent of A(Fp ). (i) The subgroup generated by the four eigenspaces A[π − 1] ⊆ A(Fp ), A[π + 1] ⊆ ′ At (Fp )ρ , A[π − p] ⊆ A(Fp3 ), and A[π + p] ⊆ At (Fp3 )ρ generate a subgroup of index 9 if p ≡ 1 mod 3, and of index 1 otherwise, of the full m-torsion A[m] ∼ = (Z/mZ)4 ⊆ A(Fp6 ). (ii) Let P ∈ A[π − 1] and Q ∈ A[π + 1]. Then em (P, Q) is trivial. (iii) For any generators P, Q, R, S of the four eigenspaces above, the pairings em (P, R) and em (Q, S) have order m/3 or m. Proof. As for Lemma 5.8, where gcd(m, p + 1) = 1 gives triviality in (ii).

⊔ ⊓

Corollary 5.10. Let A be an abelian surface over Fp , let b ∈ {−1, 0, 1}, let n = p2 − bp + 1. Let P ∈ A[n](Fp ), Q ∈ At [n](Fp ) and R, S ∈ A[n],12 and 11

Experiments suggest the 3-part of em (P, R) and em (P, Q) is trivial, i.e., that em (P, R) has order exactly m/3; Corollary 5.10 does not depend on this. 12 In practice, R and S are taken in the eigenspaces as in Lemma 3.15, so that they are defined (possibly on a twist) over Fpk , where k is the embedding degree of n, and all pairing values lie in µn ⊆ F× . pk

Supersingularity and Superspeciality Verification of Abelian Surfaces

31

suppose that ζ1 = en (P, R) and ζ2 = en (Qρ , S) have orders k1 and k2 with k1 k2 > 8 gcd(n, 2) · (p3 + p). Then A is supersingular of type b. Conversely, let A be supersingular of type b ∈ {−1, 0, 1} and p > 27 , and let P ∈ A[π − 1], Qρ ∈ A[π + 1], R ∈ A[π − p] and S ∈ A[π + p] be generators of the four eigenspaces. Then these points satisfy the above condition. Proof. We have k1 | ord(P ) and k2 | ord(Q), so the subgroup H = ⟨P, Qρ ⟩ ⊆ A(Fp2 ) satisfies |H| =

ord(P ) ord(Q) k1 k2 ≥ > 8(p3 + p), |⟨P ⟩ ∩ ⟨Qρ ⟩| gcd(2, n)

which is the width of the Hasse–Weil interval over Fp2 . Moreover, |H| divides n2 , so Lemma 2.1 gives |A(Fp2 )| = n2 . As A is defined over Fp , Theorem 3.12 shows that A is supersingular of type b. For the converse, A(Fp ) has exponent n. If b = 0, then k1 = k2 = n/2 by Lemma 5.7, and the condition n2 /4 > 16(p3 + p) holds for p ≥ 67. If b = ±1, then n is odd and k1 , k2 ≥ n/3 by Lemma 5.8 and Lemma 5.9, and n2 /9 > 8(p3 + p) holds for p ≥ 79. ⊔ ⊓ Remark 5.11. In Corollary 5.10, the points R and S only serve as witnesses: a pairing en (P, R) of order k1 certifies that P has order at least k1 , and similarly for Q. Supersingularity then follows from the width bound on ⟨P, Qρ ⟩. Such witnesses cannot be found in A(Fp2 ), as pairings between points of A(Fp2 ) take 2 values in µn ∩ F× p2 = µgcd(n,p −1) , which has order at most 3. This is why we pass to Fpk , where non-degeneracy of en guarantees that suitable witnesses exist. Proof of Superspeciality. The above results give a proof on the type b of J , and therefore also on φJ (x). Again, following Lemma 2.2, whenever b = ±2 this immediately also proves that J is superspecial, and otherwise, following Theorem 3.26, we compute the automorphism group of the associated hyperelliptic curve. 5.3

Conclusive testing of extremal abelian surfaces over Fp2

The pairing-based approach for abelian surfaces of type b = ±2 directly extends to conclusive pairing-based superspeciality verification of minimal and maximal abelian surfaces over Fp2 . However, in these situations, we should no longer assume Fp -rationality of any points, and hence no longer have the isotropy conditions on J (Fp ) and J t (Fp ) to our advantage. Given a to-be-verified basis B = {P1 , . . . , P4 } of J (Fp2 ), our approach is to use pairings to determine the size of H = ⟨P1 , . . . , P4 ⟩, which implies minimality or maximality as soon as |H| is larger than the width of the Hasse-Weil interval. We describe a simple informal algorithm for maximal abelian surfaces, and the variant for minimal abelian surfaces is self-evident. Algorithm 5 Let A be an abelian surface over Fp2 , and g ∈ µp+1 ⊆ F∗p2 a fixed generator of µp+1 . Repeat the following steps until termination.

32

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders $

1. Sample 4 random points P1 , . . . , P4 ← − A(Fp2 ) 2. If [p + 1]Pi ̸= 0A for any i, return false 3. Compute ζi,j = ep+1 (Pi , Pj ) and set Z = (logg (ζi,j )) as a matrix over Z 4. Compute the factors di of the Smith normal form of Z Q4 invariant p+1 5. Set NZ = i=1 gcd(d . If NZ > 8p3 +8p, return true. Otherwise, repeat. ,p+1) i Lemma 5.12. Algorithm 5 returns true only for maximal supersingular abelian surfaces over Fp2 , and false otherwise. Proof. If [p + 1]Pi ̸= 0A for any i, then A is clearly non-maximal. Then, when the four points Pi span a subgroup H with |H| > 8p3 + 8p by the width-bound argument on the Hasse–Weil interval, we have that A must have order (p + 1)4 , i.e., maximal. We can measure the size of H using the image of Z as a linear map. This can be done effectively13 using the invariants d1 , . . . , d4Q of the Smith p+1 normal form of Z as a matrix over Z: the image of Z is then of size gcd(di ,p+1) . ⊔ ⊓ Remark 5.13. Given a prime p, it is theoretically possible to derive the expected number of iterations required in Algorithm 5. Experimental data for primes of the form p = 2k ·5−1 shows that we succeed on the first try with probability over 99% already from k = 18. Thus, in practical applications, Algorithm 5 works on the first try. Remark 5.14. We have written Algorithm 5 with simplicity in mind, however, theoretically, as Algorithm 5 samples random points, it may never terminate as the algorithm could sample low-order points over and over with exponentially small probability. This may be resolved by deterministically sampling points that span an increasingly larger subgroup consistently. For example, if A is a Jacobian J , the deterministic sampling of divisors reduces to deterministically sampling points (x0 , y0 ) on the associated hyperelliptic curve C, which can be done by sampling x0 = ω n for a generator ω of k ∗ and increasing n. However, in practice, such an algorithm is tedious to work with, and does not significantly speed-up validation in practical situations. 5.4

Conclusive Testing for Cryptographic Primes

Isogeny-based cryptography often relies on efficient computations of (2, 2)-isogenies, hence the base field Fp or Fp2 is chosen so that a large power of 2 divides p − 1 or p + 1, and one then works with principally polarized abelian surfaces with group structure (p − 1)k , resp. (p + 1)k , where k = 2 when working over Fp , or k = 4 when working over Fp2 . This allows one to efficiently compute long chains of (2, 2)-isogenies using rational maximally isotropic (2f , 2f )-subgroups, with 2f | p±1. This large amount of rational 2• -torsion allows us to simplify conclusive testing significantly, by a generalisation of a similar supersingularity test 13

See https://math.stackexchange.com/questions/3252961/ image-of-a-linear-transformation-with-a-matrix-in-mathbb-z-m.

Supersingularity and Superspeciality Verification of Abelian Surfaces

33

for elliptic curves [8, Alg. 2]. The core idea is to use the 2• -torsion instead of a 2• -pairing to show that both A and At have a certain group structure, no matter what the isotropy conditions on this 2• -torsion are. In fact, as we drop the pairing, the results in this subsection do not require the principal polarization either: they rely only on the orders of rational points and the width-bound argument of Lemma 2.1. We analyse these cases first over Fp and then over Fp2 , to give a conclusive test of extremality, hence, superspeciality, hence supersingularity. Over Fp . We describe this in more detail for abelian surfaces of type b = −2, that is, assuming A(Fp ) has order (p + 1)2 . If P and Q have order 2f and
2 [2f −1 ]P ̸= [2f −1 ]Q, then ⟨P, Q⟩ ∼ = Z/2f Z gives us a subgroup of size 22f √ in A(Fp ). By the width-bound argument, when 22f > 8 · p · (p + 1), which is satisfied as soon as f > 23 + 34 log2 p, the order of A(Fp ) must be (p + 1)2 . The next lemma generalizes this argument when relaxing the assumption that P, Q have full order 2f . Lemma 5.15. Let A be an abelian surface over Fp and let f be the largest integer such that 2f | p + 1. Let P, Q ∈ A[2f ](Fp ) of order 2kP and 2kQ respectively, with kP ≥ kQ . If [2kP −1 ]P ̸= [2kQ −1 ]Q and kP + kQ > 3 + 23 log2 p, then A is supersingular. Proof. Since [2kP −1 ]P ̸= [2kQ −1 ]Q, we have that ⟨P, Q⟩ ∼ = Z2kP × Z2kQ ,→ A(Fp )[p + 1]. Let A[p + 1](Fp ) ∼ = Zh0 × Zh1 × Zh2 × Zh3 with hi+1 | hi . Then we √ have that h0 ·h1 ≥ 2kP +kQ > 8 p(p+1). The argument in the proof of Lemma 4.3 shows that ap = 0 and |A(Fp )| = (p + 1)2 , so A is supersingular of type b = −2. ⊔ ⊓ $

Finding such points P and Q is simple: randomly sampling P, Q ← − A(Fp ), and using [h]P, [h]Q where h = p+1 almost always works on the first try, as f 2 such points almost always have order 2f or 2g with g only a bit smaller than f . Thus, for f close to log2 p, the condition on kQ is almost always satisfied. Interestingly, one can also sample directly in A(Fp ) \ [2]A(Fp ), see e.g. [15, 32], to enforce kQ = f or kQ = f − 1, depending on the exponent of A. In total, this gives a highly efficient conclusive proof of supersingularity using only simple and efficient Fp -arithmetic for primes such that 2f | p + 1 and f ≈ log2 p. The case b = 2 follows similarly as Lemma 5.15, by repeating the above procedure for both A(Fp ) and At (Fp ) with 2f | p − 1. Over Fp2 . We again explain the argument only for the maximal case where A(Fp2 ) has order (p + 1)4 , and omit the analogous minimal case. Lemma 5.16. Let A be an abelian surface over Fp2 , let f be the largest integer such that 2f | p + 1 and let P1 , P2 , P3 , P4 ∈ A[p + 1] be such that Qi := [ p+1 ]P P2f i has order 2ki for 1 ≤ i ≤ 4, and the points [2ki −1 ]Qi span A(Fp2 )[2]. If ki > 3 + 3 log2 p, then A is maximal, hence superspecial. Proof. As for Lemma 5.15, now requiring 2

P

ki

> 8p(p2 + 1).

⊔ ⊓

34

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Sampling such a generating set {P1 , . . . , P4 } can be done efficiently but is rather technical, see [32, Thm. 1]. Nevertheless, similar to the Fp -case, sampling random points P1 , . . . , P4 is highly likely to succeed on a first try, as long as the 2-adic order of each of P1 , . . . P4 exceeds 43 (1 + log2 p), and the 2-torsion points below Pi span A[2], so that they are independent.

6

Benchmarking Results

We now compare the performance of our algorithms, which we have implemented in Magma [7], to existing methods in the literature to verify supersingularity. We are not aware of other probabilistic methods to verify supersingularity. We therefore compare both IsSupersingular as well as the pairing-based conclusive methods to point counting on A. For superspeciality, we compare to the computation of the Cartier-Manin matrix (via CartierRepresentation) in Magma. Lastly, we also compare the speed-up achieved for primes of the form p = c · 2f − 1 for Jacobians of type b = −2, using the 2• -torsion test from Lemma 5.15, as this situation is common in isogeny-based cryptography. Performance of probabilistic approaches. For superspeciality, we track the average computation time to probabilistically verify superspeciality of 100 supersingular Jacobians over Fp for primes p from 29 up to 211 with Algorithm 3. We compare this to the computation of the Cartier–Manin matrix in Magma. For supersingularity, we track the average computation time to probabilistically verify supersingularity of 1000 supersingular Jacobians over Fp , for primes p from 29 up to 211 with IsSupersingular (Algorithm 4). We compare this to a point counting approach based on Lemma 3.8 in Magma. The results are given in Fig. 1.

Algorithm 3 CartierRepresentation

IsSupersingular Point Counting Average time (µs, log10 scale)

Average time (s, log10 scale)

100

10−1

10−2

103

102

10−3 20

40

60

80

100

120 140 Prime p

160

180

200

220

(a) Superspeciality: Algorithm 3 vs. Cartier–Manin matrix computation.

20

40

60

80

100

120 140 Prime p

160

180

200

220

(b) Supersingularity: IsSupersingular vs. point counting.

Fig. 1: Performance of probabilistic verification: average time to test 100 Jacobians for superspeciality (left), 1000 for supersingularity (right).

Supersingularity and Superspeciality Verification of Abelian Surfaces

35

Performance of conclusive approaches. For supersingularity, we track the average total computation time to conclusively verify supersingularity of 100 supersingular Jacobians of type b = −2 over Fp , for primes p of the form p = c2f − 1 with c ∈ {5, 3 · 5, 32 · 5, 3 · 5 · 7}. We first compare the pairing-based methods from Section 5 to the point counting approach based on Lemma 3.8 in Magma, for p from 29 up to 188743679 ≈ 227 (f between 2 and 22). We then show the improvement of the 2• -torsion test (Lemma 5.15) over the conclusive test from Section 5 in Figure 2, for p from 213 up to 2297 (f from 9 up to 293).

Pairing Point Counting

107 Average time (µs, log10 scale)

Average time (µs, log10 scale)

108 7

10

106 105 104 103 2

10

23

26

29

212 215 218 221 Prime p (log2 scale)

224

227

(a) Conclusive: pairing-based approach vs. point counting.

106 105 104 103 102 2−16

Pairing 2• -Torsion Test 226

268

2110 2152 2194 Prime p (log2 scale)

2236

2278

2320

(b) Conclusive, on primes p = c2f − 1: pairing method vs. the 2• -torsion test from Lemma 5.15.

Fig. 2: Performance of conclusive verification: average time to test 100 Jacobians.

7

Future Work

This work covers probabilistic and conclusive supersingularity and superspeciality testing in dimension 2 over Fp . A natural direction for follow-up work is to determine similar efficient criteria for supersingular abelian varieties of dimension g > 2, which comes down to a specific case of the Ekedahl–Oort stratification of particular interest to cryptography. Similarly, the case of abelian surfaces over Fp2 has only been partially answered by this work, as the results in Sections 4 and 5 translate easily to Fp2 for the Jacobians of type b ∈ {±1, ±2}. The exploration of supersingularity verification for abelian surfaces with other Weil polynomials is left for future work. Furthermore, the following specializations of the approaches in this work are possible. Kummer surfaces. When using Kummer surfaces, we do not distinguish P and −P . This means we must specialize certain results in this work to such a specific setting, as some results require this precision. For example, we may find ordinary abelian surfaces with |J (Fp )| = (p + 1)2 and |J t (Fp )| = (p − 1)(p + 1). This

36

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

does not seem too problematic, but a more careful examination of such cases is required to claim with certainty that our probabilistic tests remain convincing. Note that the conclusive tests from Section 5 remain applicable, as such pairings directly verify the group structure instead of the order. Optimized arithmetic. In this work, we have refrained from a detailed analysis of the cost of scalar multiplication and pairings on Jacobians, and instead have simply written [n]P or en (P, Q). In practice, one may apply well-known techniques, such as differential addition chains or cubical arithmetic, to determine a precise cost of our algorithms in terms of finite field operations, as has been done in the case of elliptic curves [2, 8, 30, 31]. Non-ordinary abelian surfaces. To complete the efficient Ekedahl-Oort classification for abelian surfaces over Fp , one may study the case of non-ordinary abelian surfaces, i.e., p-rank 1. As such abelian surfaces have similarly specific Weil polynomials, similar methods as proposed in this work should apply, although with different technical derivations and pairing properties.

References [1]

Marius A. Aardal, Gora Adj, Diego F. Aranha, Andrea Basso, Isaac Andrés Canales Martı́nez, Jorge Chávez-Saab, Maria Corte-Real Santos, Pierrick Dartois, Luca De Feo, Max Duparc, Jonathan Komada Eriksen, Tako Boris Fouotsa, Décio Luiz Gazzoni Filho, Basil Hess, David Kohel, Antonin Leroux, Patrick Longa, Luciano Maino, Michael Meyer, Kohei Nakagawa, Hiroshi Onuki, Lorenz Panny, Sikhar Patranabis, Christophe Petit, Giacomo Pope, Krijn Reijnders, Damien Robert, Francisco Rodrı́guez-Henrı́quez, Sina Schaeffler, and Benjamin Wesolowski. SQIsign. Tech. rep. National Institute of Standards and Technology, 2025. url: https://sqisign.org (cit. on p. 1). [2] Gustavo Banegas, Valerie Gilchrist, and Benjamin Smith. “Efficient supersingularity testing over GF(p) and CSIDH key validation”. In: Transactions on Mathematical Cryptology 2.1 (2022), pp. 21–35 (cit. on pp. 2, 36). [3] Andrea Basso, Giacomo Borin, Wouter Castryck, Maria Corte-Real Santos, Riccardo Invernizzi, Antonin Leroux, Luciano Maino, Frederik Vercauteren, and Benjamin Wesolowski. “PRISM: Simple and Compact Identification and Signatures from Large Prime Degree Isogenies”. In: PublicKey Cryptography - PKC 2025 - 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12-15, 2025, Proceedings, Part III. Ed. by Tibor Jager and Jiaxin Pan. Vol. 15676. Lecture Notes in Computer Science. Springer, 2025, pp. 300– 332. isbn: 978-3-031-91825-4. doi: 10.1007/978- 3- 031- 91826- 1\_10. url: https://doi.org/10.1007/978- 3- 031- 91826- 1%5C_10 (cit. on p. 1).

Supersingularity and Superspeciality Verification of Abelian Surfaces

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

37

Andrea Basso, Pierrick Dartois, Max Duparc, Jonathan Komada Eriksen, Sabrina Kunzweiler, Michael Meyer, Giacomo Pope, Krijn Reijnders, Damien Robert, Ryan Rueger, and Sina Schaeffler. MIKE: a fast and compact post-quantum NIKE. In preparation. (cit. on p. 1). Andrea Basso and Luciano Maino. “POKÉ: A Compact and Efficient PKE from Higher-Dimensional Isogenies”. In: Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part II. Ed. by Serge Fehr and Pierre-Alain Fouque. Vol. 15602. Lecture Notes in Computer Science. Springer, 2025, pp. 94– 123. isbn: 978-3-031-91123-1. doi: 10.1007/978- 3- 031- 91124- 8\_4. url: https://doi.org/10.1007/978- 3- 031- 91124- 8%5C_4 (cit. on p. 1). Oskar Bolza. “On binary sextics with linear transformations into themselves”. In: American Journal of Mathematics (1887), pp. 47–70 (cit. on pp. 19, 20). Wieb Bosma, John Cannon, and Catherine Playoust. “The Magma algebra system I: The user language”. In: Journal of Symbolic Computation 24.3-4 (1997), pp. 235–265 (cit. on p. 34). Fabio Campos, Jorge Chávez-Saab, Jesús-Javier Chi-Domı́nguez, Michael Meyer, Krijn Reijnders, Francisco Rodrı́guez-Henrı́quez, Peter Schwabe, and Thom Wiggers. “Optimizations and Practicality of High-Security CSIDH”. In: IACR Communications in Cryptology 1.1 (Apr. 9, 2024). issn: 30065496. doi: 10.62056/anjbksdja (cit. on pp. 2, 26, 33, 36). Gabriel Cardona. “On the number of curves of genus 2 over a finite field”. In: Finite Fields and Their Applications 9.4 (2003), pp. 505–526. issn: 1071-5797. doi: https://doi.org/10.1016/S1071- 5797(03)00039X. url: https : / / www . sciencedirect . com / science / article / pii / S107157970300039X (cit. on p. 19). Wouter Castryck and Thomas Decru. “An efficient key recovery attack on SIDH”. In: Annual international conference on the theory and applications of cryptographic techniques. Springer. 2023, pp. 423–447 (cit. on p. 1). Wouter Castryck, Adrian Dina, Péter Kutas, and Gioella Lorenzon. Postquantum commutative group actions from oriented superspecial abelian surfaces. In preparation. (cit. on p. 1). Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes. “CSIDH: An Efficient Post-Quantum Commutative Group Action”. In: Advances in Cryptology - ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part III. Ed. by Thomas Peyrin and Steven D. Galbraith. Vol. 11274. Lecture Notes in Computer Science. Springer, 2018, pp. 395–427. isbn: 978-3-030-03331-6. doi: 10.1007/978-3-030-03332-3\_15. url: https: //doi.org/10.1007/978-3-030-03332-3%5C_15 (cit. on pp. 1, 2, 26).

38

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren. Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC press, 2005 (cit. on p. 6). Gunther Cornelissen. “Two-torsion in the Jacobian of hyperelliptic curves over finite fields”. In: Archiv der Mathematik, v.77, 241-246 (2001) 77 (Sept. 2001). doi: 10.1007/PL00000487 (cit. on p. 11). Maria Corte-Real Santos and Krijn Reijnders. “Return of the Kummer: a Toolbox for Genus-2 Cryptography”. In: IACR Communications in Cryptology 2.4 (Jan. 8, 2026). issn: 3006-5496. doi: 10.62056/a0zogyl7s (cit. on p. 33). Thomas Decru and Krijn Reijnders. Expander properties of superspecial isogeny digraphs with level structure. Cryptology ePrint Archive, Paper 2026/500. 2026. url: https : / / eprint . iacr . org / 2026 / 500 (cit. on p. 41). Sanath Devalapurkar and John Halliday. “The Dieudonné modules and Ekedahl-Oort types of Jacobians of hyperelliptic curves in odd characteristic”. In: arXiv preprint arXiv:1712.04921 (2017) (cit. on p. 4). Javad Doliskani. “On division polynomial PIT and supersingularity”. In: Applicable Algebra in Engineering, Communication and Computing 29.5 (2018), pp. 393–407 (cit. on p. 2). Enric Florit and Benjamin Smith. “An atlas of the Richelot isogeny graph”. In: Theory and Applications of Supersingular Curves and Supersingular Abelian Varieties. Vol. B90. RIMS Kôkyûroku Bessatsu. Res. Inst. Math. Sci. (RIMS), Kyoto, 2022, pp. 195–219. url: http://hdl.handle.net/ 2433/276282 (cit. on pp. 20, 41). Pierrick Gaudry and Éric Schost. “Genus 2 point counting over prime fields”. In: Journal of Symbolic Computation 47.4 (2012). Special Issue for Joachim von zur Gathen at 60, pp. 368–400. issn: 0747-7171. doi: https://doi.org/10.1016/j.jsc.2011.09.003. url: https://www. sciencedirect . com / science / article / pii / S0747717111001386 (cit. on p. 4). Everett W Howe, Enric Nart, and Christophe Ritzenthaler. “Jacobians in isogeny classes of abelian surfaces over finite fields”. In: Annales de l’Institut Fourier. Vol. 59. 1. 2009, pp. 239–289 (cit. on pp. 10, 18–20). Bruce W Jordan, Allan G Keeton, Bjorn Poonen, Eric M Rains, Nicholas Shepherd-Barron, and John T Tate. “Abelian varieties isogenous to a power of an elliptic curve”. In: Compositio Mathematica 154.5 (2018), pp. 934–959 (cit. on pp. 2, 8, 22). Ahmad Kazemifard, Alireza Naghipour, and Saeed Tafazolian. “A note on superspecial and maximal curves”. In: Bulletin of the Iranian Mathematical Society 39.3 (2013), pp. 405–413 (cit. on p. 18). Jean Kieffer. Counting points on abelian surfaces over finite fields with Elkies’s method. 2022. arXiv: 2203 . 02009 [math.NT]. url: https : / / arxiv.org/abs/2203.02009 (cit. on p. 4).

Supersingularity and Superspeciality Verification of Abelian Surfaces

[25]

[26] [27]

[28] [29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

39

Luciano Maino, Chloe Martindale, Lorenz Panny, Giacomo Pope, and Benjamin Wesolowski. “A direct key recovery attack on SIDH”. In: Annual international conference on the theory and applications of cryptographic techniques. Springer. 2023, pp. 448–471 (cit. on p. 1). Stefano Marseglia. “Weil polynomials of small degree”. In: Indagationes Mathematicae (2025) (cit. on p. 7). Ben Moonen. “Computing discrete invariants of varieties in positive characteristic I. Ekedahl-Oort types of curves”. In: Journal of Pure and Applied Algebra 226.11 (2022), p. 107100 (cit. on p. 4). Frans Oort. “A stratification of a moduli space of abelian varieties”. In: Moduli of abelian varieties. Springer, 2001, pp. 345–416 (cit. on p. 4). Jonathan Pila. “Frobenius maps of abelian varieties and finding roots of unity in finite fields”. In: Mathematics of Computation 55.192 (1990), pp. 745–763 (cit. on p. 4). Giacomo Pope, Krijn Reijnders, Damien Robert, Alessandro Sferlazza, and Benjamin Smith. “Simpler and Faster Pairings from the Montgomery Ladder”. In: IACR Communications in Cryptology 2.2 (July 7, 2025). issn: 3006-5496. doi: 10.62056/ah2i893y6 (cit. on p. 36). Krijn Reijnders. “Effective Pairings in Isogeny-based Cryptography”. In: LATINCRYPT 2023. Springer. 2023, pp. 109–128. doi: 10.1007/978-3031-44469-2\_6 (cit. on pp. 2, 26, 29, 36). Krijn Reijnders. “The Tate Profile”. In: Progress in Cryptology - LATINCRYPT 2025 - 9th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2025, Medellin, Colombia, October 1-3, 2025, Proceedings. Springer. 2025 (cit. on pp. 33, 34). Damien Robert. “Breaking SIDH in polynomial time”. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer. 2023, pp. 472–503 (cit. on p. 1). Damien Robert. Fast pairings via biextensions and cubical arithmetic. Cryptology ePrint Archive, Paper 2024/517. 2024. url: https : / / eprint . iacr.org/2024/517 (cit. on p. 2). Damien Robert. “The module action for isogeny based cryptography”. In: IACR Cryptol. ePrint Arch. 2024 (2024), p. 1556. url: https://eprint. iacr.org/2024/1556 (cit. on p. 1). Peter Roquette. “Abschätzung der Automorphismenanzahl von Funktionenkörpern bei primzahlcharakteristik”. In: Mathematische Zeitschrift 117.1 (1970), pp. 157–163 (cit. on p. 22). Sergey Rybakov. “The groups of points on abelian varieties over finite fields”. In: Central European Journal of Mathematics 8.2 (2010), pp. 282– 288. doi: 10.2478/s11533- 010- 0003- x. url: https://doi.org/10. 2478/s11533-010-0003-x (cit. on p. 9). Tanush Shaska. “Determining the automorphism group of a hyperelliptic curve”. In: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation. 2003, pp. 248–254 (cit. on p. 20).

40

[39] [40] [41] [42]

[43] [44]

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

Jia Shi. Lifting L-polynomials of genus 2 curves. 2026. arXiv: 2508.11028 [math.NT]. url: https://arxiv.org/abs/2508.11028 (cit. on p. 4). Joseph H Silverman. The arithmetic of elliptic curves. Vol. 106. 2. Springer, 2009 (cit. on pp. 5, 8, 19). Andrew Sutherland. “A generic approach to searching for Jacobians”. In: Mathematics of Computation 78.265 (2009), pp. 485–507 (cit. on p. 11). Andrew V Sutherland. “Identifying supersingular elliptic curves”. In: LMS Journal of Computation and Mathematics 15 (2012), pp. 317–325 (cit. on pp. 1, 3). Jacques Vélu. “Isogénies entre courbes elliptiques”. In: Comptes-Rendus de l’Académie des Sciences 273 (1971), pp. 238–241 (cit. on p. 5). Hui June Zhu. “Group structures of elementary supersingular abelian varieties over finite fields”. In: Journal of Number Theory 81.2 (2000), pp. 292– 309 (cit. on p. 10).

Supersingularity and Superspeciality Verification of Abelian Surfaces

A

41

Non-trivial Automorphisms of Jacobians

In general, automorphisms of two-dimensional Jacobians are induced by automorphisms of the associated hyperelliptic curves of genus 2. Any Jacobian will have the automorphism [−1], and one therefore often analyzes the reduced automorphism group RA(C), resp., RA(J ). For dimension 2, the non-trivial reduced automorphism groups are wellunderstood. An overview of these is given by Florit and Smith [19], and summarized in [16, App. A]. We follow the latter to describe those non-trivial automorphisms used in this work: τ , ρ, ω, ζ (5) , and ζ (6) . We denote a primitive n-th root of unity in F∗q by ζn . – The automorphism τ can be described as x 7→ 1/x on a suitable model for C, which always exists. Its image in RA(C) has order 2, and its lifts to Aut(C) satisfy τ 2 = ι, the hyperelliptic involution. (2ζ3 +1)(v 2 −1)x+3(v+1)2 – The automorphism ρ can be described as x 7→ 3(v−1) 2 x+(2ζ +1)(v 2 −1) for 3 some v ∈ Fq on a suitable model for C, which always exists. It has order 3. √

2+1) √ – The automorphism ω can be described as x 7→ (x−( on a suitable model 2−1)x+1 for C, which always exists. It has order 4. – The automorphism ζ (5) can be described as x 7→ ζ5 x on the curve C : y 2 = x5 − 1. It has order 5. – The automorphism ζ (6) can be described as x 7→ ζ6 x on the curve C : y 2 = x6 + 1. It has order 6.

B

Classification of Superspecial Jacobians over Fp2

We may repeat a similar computation as we performed in Section 3.5 for Jacobians over Fp2 . Namely, given a maximal, resp., minimal, Jacobian, we may compute the characteristic polynomial of a non-quadratic twist C σ for a non-trivial automorphism σ ∈ RA(C). This gives us the list of characteristic polynomials of twisted superspecial curves, resp., Jacobians, over Fp2 . Similar to the case over Fp , we may use the results in [16, 19] to determine the partial RA(C) from these results, or a similar characterization of such Jacobians in terms of the associated (2, 2)-isogenous product of elliptic curves. Over Fp2 , we write that J is of type (a, b) if φJ (x) = x4 − apx3 + bp2 x2 − ap3 x + p4 . The quadratic twist maps (a, b) 7→ (−a, b), hence we may classify these up to ±a. Theorem B.1. Let J be a Jacobian over Fp2 . Then J is superspecial if and only if – J is minimal or maximal, or – J /Fp2 is a twisted superspecial

42

Maria Corte-Real Santos, Gioella Lorenzon, and Krijn Reijnders

1. of type (0, −2), e.g. φJ (x) = (x − p)2 (x + p)2 , and σ ∈ RA(C) (whose lift in Aut(C) is an involution not equal to the hyperelliptic involution). 2. of type (±2, 3), e.g. φJ (x) = (x2 ± px + p2 )2 , and ρ ∈ RA(C) 3. of type (0, 2), e.g. φJ (x) = (x2 + p2 )2 , and τ ∈ RA(C) 4. of type (±1, 1), e.g. φJ (x) = (x4 ± px3 + p2 x2 ± p3 x + p4 ), and ζ (5) ∈ RA(C) 5. of type (0, 1), e.g. φJ (x) = (x2 −px+p2 )(x2 +px+p2 ), and ζ (6) ∈ RA(C) 6. of type (0, 0), e.g. φJ (x) = (x4 + p4 ), and ω ∈ RA(C) Superspeciality Verification. With the above result, superspeciality verification over Fp2 is surprisingly easy: either check that J is minimal or maximal using the results from Section 4, or compute the automorphism group of the associated hyperelliptic curve, and find a minimal or maximal twist. Lifting F Qp Curves. Recall that a curve over Fp with characteristic polynomial φ(x) = (x − αi ) lifts to a curve over Fp2 with characteristic polynomial φ(x) = Q (x − αi2 ). This gives us that curves of type b = ±2 over Fp become of type (±4, 6) over Fp2 , curves of type b = ±1 become type (±2, 3), and curves of type 0 become type (0, 2).

Related documents

• Supersingularity and Superspeciality Verification of Abelian Surfaces#1157195
• Ekedahl-Oort strata meeting the supersingular locus#1084921
• A Computational Framework for the Moduli of Supersingular Abelian Varieties#821458
• Apollonian structure in the Abelian sandpile#364424
• Heavenly Elliptic Curves over Cubic Number Fields#1130296