PaperlayerView exact revision on arXiv

Source-linked AI summary

Supersingularity and Superspeciality Verification of Abelian Surfaces

Maria Corte-Real Santos, Gioella Lorenzon, Krijn Reijnders

arXiv:2610.01924v1math.NTcs.CR

TL;DR

Higher-dimensional isogeny protocols rely on supersingular abelian varieties, but efficient verification for abelian surfaces has been lacking. The paper develops probabilistic and conclusive verification algorithms, supported by structural analysis of supersingular Jacobians. Its Monte Carlo supersingularity test for abelian surfaces over Fp runs in O(log p), and the work also identifies important limits on the covered settings.

  • Problem

    Efficient verification of supersingularity and superspeciality for abelian surfaces over finite fields is lacking, despite the importance of these varieties in isogeny-based cryptography.

    Source: §1 · pp. 1–2

  • Method

    The authors analyze supersingular and superspecial Jacobian structures and use those results to develop probabilistic and conclusive verification algorithms.

    Source: Contributions · p. 3, §3.2 · p. 11, §3.3 · p. 11

  • Results

    The Monte Carlo supersingularity test for abelian surfaces over Fp runs in O(log p), and the minimality algorithm has false-positive probability O(p^-1) for large primes.

    Source: §1 · p. 2, Contributions · p. 3

  • Takeaways & Limitations

    Supersingularity validation is a crucial security check for higher-dimensional isogeny-based protocols.

    Source: §1 · p. 1

    The work focuses on dimension 2 over Fp; the Fp2 case is only partially addressed, and dimension g > 2 remains future work.

    Source: §7 · p. 35

Abstract

from arXiv · show

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 $\mathbb{F}_p$ 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 $\mathbb{F}_p$. 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.

1 Introduction

Higher-dimensional isogeny protocols rely on supersingular, often superspecial, abelian varieties, making their validation important to security. This work develops probabilistic and conclusive verification algorithms, supported by structural results on supersingular and superspecial Jacobians.

1 Introduction

  • Supersingular principally polarized abelian varieties underpin higher-dimensional isogeny protocols, and omitting validation would create a significant attack vector.The introduction names SQIsign, PRISM, MIKE, and POK´E as examples of protocols relying on higher-dimensional isogenies.Source: §1 · p. 1
  • Earlier elliptic-curve tests use random-point checks or order bounds, while other approaches use division polynomials and pairings.The cited examples include Sutherland, CSIDH, Doliskani, and.Source: §1 · pp. 1–2
  • Prior methods for dimension-2 supersingularity rely on point counting or L-polynomial computation, which the authors describe as prohibitively slow for cryptographic primes.The related-work discussion also identifies Schoof–Pila [29] and Cartier-Manin or Hasse-Witt matrix approaches.Source: §1 · p. 2, Contributions · pp. 4–5
  • The paper gives probabilistic and conclusive algorithms for verifying supersingularity and superspeciality of abelian surfaces over Fp.The Monte Carlo supersingularity test runs in O(log p); the conclusive algorithms have structural requirements.Source: Contributions · p. 3
  • The structural analysis describes possible orders over Fp2, group structures over Fp, and a classification of superspecial Jacobians using genus-2 curve automorphisms.These results underlie the probabilistic and conclusive tests.Source: Contributions · p. 3
  • The work also gives algorithms for minimality and maximality in any dimension and for testing superspeciality of Jacobians over Fp.It also gives a similar superspecial-Jacobian result over Fp2.Source: Contributions · p. 3

2 Preliminaries

The preliminaries establish the finite-field and abelian-variety notation, distinguish supersingularity from superspeciality, and introduce Frobenius polynomials and point-count bounds used later.

2.1 Supersingular Elliptic Curves

  • Supersingular elliptic curves have p-rank 0 and Frobenius trace divisible by p, properties that impose stricter group structures than on ordinary curves.Their endomorphism rings are maximal orders in quaternion algebras; the paper also notes their cryptographic relevance and efficient isogeny computations using Vélu’s formulas.Source: §2.1 · p. 5

2.2 Abelian Varieties

  • A principally polarized abelian surface is a genus-2 hyperelliptic Jacobian, a product of elliptic curves, or a Weil restriction from Fq2.A principal polarization is an isomorphism from an abelian variety to its dual; the polarization also supplies the Weil-pairing isotropy conditions used in conclusive tests.Source: §2.2 · pp. 5–6
  • For principally polarized varieties, the Weil pairing restricts rational n-torsion, while the p-torsion rank is at most the dimension and is called the p-rank.The finite-group structure is expressed through invariant factors, with the largest factor giving the exponent of A(Fq).Source: §2.2 · p. 6
  • A supersingular abelian surface has p-rank 0 and is isogenous to a product of supersingular elliptic curves, whereas superspeciality requires it to be isomorphic to such a product.Superspeciality therefore implies supersingularity; the paper calls a hyperelliptic curve supersingular or superspecial when its Jacobian has the corresponding property.Source: §2.2 · p. 6

2.3 Characteristic Polynomial of Frobenius

  • The Weil polynomial records Frobenius data and point counts; an abelian surface over Fp is supersingular exactly when its trace a is 0 and p divides b.For dimension g, the Hasse–Weil interval ranges from (√q − 1)^(2g) to (√q + 1)^(2g); a subgroup larger than its width determines the unique possible group order.Source: §2.3 · p. 7
  • Minimal or maximal abelian varieties over Fp2 are superspecial, and a twist is a variety isomorphic to the original over an extension but not over the base field.For Jacobians, twists come from twists of the associated hyperelliptic curve.Source: §2.3 · p. 8

3 Supersingular Abelian Surfaces

This section develops structural criteria for verifying supersingularity of abelian surfaces, using group orders, point counts over F_p^2, and m-torsion structure organized by Frobenius eigenspaces. It also gives superspeciality criteria based on minimal or maximal twists and genus-2 curve automorphisms.

3.1 Group Structures of Abelian Surfaces

  • Rybakov’s Weil-polynomial constraints restrict abelian-surface group structures through divisibility conditions on the polynomial coefficients.The section reformulates those constraints for abelian surfaces and notes that Weil bounds further limit the possibilities.Source: §3.1 · p. 9

3.2 Group Structures of Supersingular Abelian Surfaces

  • Supersingular abelian surfaces over F_p have five possible characteristic polynomials and nine group structures, with order n = p^2 − bp + 1 for b ∈ {−2, −1, 0, 1, 2}.For p > 5, the b ∈ {−1, 0, 1} cases have cyclic groups; b = ±2 gives rank at least 2, with structures depending on p modulo 4.Source: §3.2 · pp. 9–10
  • For genus-2 hyperelliptic Jacobians, the factorization type of the defining polynomial determines the rational 2-torsion group J[2](F_p).The listed cases range from trivial rational 2-torsion for irreducible polynomials to (Z/2Z)^4 when the polynomial splits into linear factors.Source: §3.2 · p. 11
  • An abelian surface over F_p has trace a = 0 exactly when its order equals that of its quadratic twist; for supersingular surfaces, the two groups are isomorphic.The paper uses twist order as a second evaluation of the Weil polynomial alongside |A(F_p)|.Source: §3.2 · p. 11

3.3 Uniqueness of Supersingular Orders

  • For supersingular orders n = p^2 − bp + 1, counts |A(F_p^2)| = n^2 identify supersingularity when b ≠ 0 over F_p or F_p^2, and when b = 0 over F_p.For b = ±2, such a surface is minimal or maximal; for b = ±1 the count forces supersingularity, and the b = 0 case is restricted to surfaces defined over F_p.Source: §3.3 · pp. 12–14

3.4 Structure theory of m-torsion

  • The section develops m-torsion theory to show that knowing A[m] suffices to determine supersingularity, enabling a conclusive test using the m-Weil pairing.Here m is the exponent of A(F_p), and the pairing is used to identify the structure of rational m-torsion.Source: §3.4 · p. 14
  • Frobenius eigenspaces in m-torsion lie in fields determined by eigenvalue congruences, with their field and twist assignments depending on b-type.For λ=±1, A[π−1]=A(Fp) and A[π+1]=At(Fp)ρ. For ±p, the assignments are: b=2, the same respective groups; b=−2, swapped; b=0, At(Fp2)ρ and At(Fp2)ρ′; b=−1, A(Fp3) and At(Fp3)ρ′; b=1, At(Fp3)ρ and A(Fp3).Source: §3.4 · p. 15
  • The subgroup generated by the four eigenspaces is nearly all of A[m], with index a power of 2 or 3 determined by b-type and A(Fp).The index is 8 for b=0; for b=−1 it is 9 if p≡1 mod 3 and 1 otherwise, while for b=1 it is 9 if p≡2 mod 3 and 1 otherwise.Source: §3.4 · pp. 15–16
  • Pairings between m-torsion eigenpoints have bounded order: e_m(P,S) and e_m(Q,R) divide gcd(m,2), while e_m(P,Q) and e_m(R,S) divide gcd(m,p+1).Source: §3.4 · p. 17

3.5 Superspecial Jacobians

  • A principally polarized abelian surface over Fp or Fp2 is superspecial exactly when it has a twist over Fp2 that is minimal or maximal.For principally polarized Jacobians, the associated curve is superspecial precisely when the Jacobian is superspecial; superspecial curves have a minimal or maximal twist over Fp2.Source: §3.5 · pp. 18–19
  • Twisted superspecial curves and Jacobians are very sparse, and their automorphism groups can be computed efficiently from curve equations or most invariant sets to identify twisted superspecial Jacobians quickly.Source: §3.5 · p. 20
  • A genus-2 hyperelliptic Jacobian over Fp is superspecial exactly when its b-type and reduced automorphism group satisfy the stated conditions.The conditions are b=±2; b=±1 with RA(C) equal to S3, S4, or D2×6; or b=0 with RA(C) equal to Z2 × Z2, S4, or D2×6.Source: §3.5 · p. 20

4 Probabilistic Supersingularity Testing

This section develops probabilistic tests for extremality, superspeciality, and supersingularity, using structural results on supersingular Jacobians and point-group orders. Its tests cover varieties of any dimension and abelian surfaces over Fp, with stated logarithmic runtime and small false-positive probabilities.

4.3 Probabilistic Order Determination over Fp

  • Supersingular Jacobians over Fp have orders p^2 − bp + 1 for b ∈ {−2, −1, 0, 1, 2}; these structural results support the probabilistic tests.The section's order tests use random points on an abelian surface and its dual to check candidate orders.Source: §4 · p. 21, §4.3 · p. 22

4.1 Minimality and Maximality Testing for Varieties

  • O(log p) time: Algorithm 2 always accepts minimal or maximal varieties and accepts a non-extremal variety with probability at most O(p^-1).The test applies to abelian varieties of any dimension over Fp or Fp2.Source: §4.1 · p. 21

4.2 Superspeciality Testing for Jacobians

  • O(g log p) time: for p > g + 1, Algorithm 3 accepts every superspecial Jacobian and accepts a non-superspecial one with probability at most O((g − 1) · p^-1).It tests whether the Jacobian or one of its twists is minimal or maximal.Source: §4.2 · p. 22

4.3 Probabilistic Order Determination over Fp

  • For b = −2, one [n]P = 0 test accepts supersingular surfaces with probability 1 and non-supersingular ones with probability O(p^-1/2); for b ∈ {−1, 0, 1, 2}, both A and its twist are tested.Here n = p^2 − bp + 1 for b ∈ {−1, 0, 1}, and n = p ± 1 for b = ∓2; the extremal cases use p ± 1 rather than (p ± 1)^2.Source: §4.3 · pp. 23–24

4.4 Supersingularity Testing for Abelian Surfaces over Fp

  • O(log p) time and false-positive probability O(p^-1/2): Algorithm 4 always accepts supersingular abelian surfaces and rarely accepts non-supersingular ones.The algorithm uses uniformly random points; excluding 2- or 3-torsion ensures it never misclassifies a supersingular surface.Source: §4.4 · p. 25

5 Conclusive Supersingularity Testing over Fp

This section develops conclusive tests for supersingularity and extremality of abelian surfaces over finite fields, using pairings or point orders in different settings. It also discusses termination and practical considerations for sampling in an earlier testing algorithm.

5 Conclusive Supersingularity Testing over Fp

  • The conclusive method generalizes pairing-based verification to genus-2 Jacobians, analyzes isotropy and discrete-log requirements, and offers a speed-up when 2^f divides the exponent for a large power of f [8, Alg. 2].Conclusive testing provides certainty where probabilistic methods may fail, including at small p.Source: §5 · p. 26

5.1 Isotropy on Supersingular Abelian Surfaces of type b = ±2

  • For type b = 2, pairing orders k and k′ with k^2, k′^2 > W certify supersingularity; for type b = −2, |im M| > W does so, where W = 8√p(p + 1).For sufficiently large p, supersingular surfaces of either type admit points satisfying the corresponding test.Source: §5.1 · p. 28

5.2 Isotropy on Cyclic Supersingular Abelian Surfaces

  • For type b = 0, cross-eigenspace pairings have order exactly m/2, while for b = ±1 they have order m/3 or m, where m is the exponent of A(Fp).For b = 0, m = p^2 + 1; for b = 1, m = p^2 − p + 1; and for b = −1, m = p^2 + p + 1. The eigenspaces and pairings are taken over extensions as specified by each type.Source: §5.2 · pp. 29–30
  • For cyclic types b ∈ {−1, 0, 1}, pairing values of orders k1 and k2 with k1k2 > 8 gcd(n, 2) · (p^3 + p) certify supersingularity, with n = p^2 − bp + 1.Conversely, the stated condition holds for supersingular surfaces when p > 27; the test uses field extensions because relevant pairings over Fp may be trivial.Source: §5.2 · pp. 29–31

5.3 Conclusive testing of extremal abelian surfaces over Fp2

  • Algorithm 5 returns true only for maximal supersingular abelian surfaces over Fp2, and experiments found first-try success above 99% for p = 2^k·5 − 1 from k = 18.The test uses pairings to measure the generated subgroup and compares its size with the Hasse–Weil interval width.Source: §5.3 · pp. 31–32
  • Random sampling in the earlier conclusive algorithm could theoretically fail to terminate, while deterministic sampling is tedious and does not significantly speed up practical validation.For a Jacobian, deterministic sampling can use curve points with x0 = ω^n for a generator ω of k* and increasing n.Source: §5.3 · p. 32

5.4 Conclusive Testing for Cryptographic Primes

  • The cryptographic-prime tests replace 2-power pairings with rational 2-power torsion and point-order bounds, so they do not require principal polarization.The resulting extremality test implies superspeciality and then supersingularity; the motivation is that cryptographic fields provide large rational 2-power torsion.Source: §5.4 · pp. 32–33
  • Over Fp, distinct 2-power torsion points whose order exponents satisfy the stated logarithmic bound certify supersingularity; random sampling makes the test highly efficient when 2^f divides p + 1 and f is close to log2 p.For the b = -2 case, Lemma 5.15 requires kP + kQ > 3 + (3/2)log2 p; the b = 2 case applies the procedure to both A(Fp) and its twist when 2^f divides p − 1.Source: §5.4 · p. 33
  • Over Fp2, four points whose derived 2-torsion spans A(Fp2)[2] certify maximality, hence superspeciality, when their order exponents exceed the lemma’s stated logarithmic bound.Random sampling is likely to succeed when each point has sufficiently large 2-adic order and the points below them span A[2] independently.Source: §5.4 · pp. 33–34

6 Benchmarking Results

The section benchmarks probabilistic and conclusive verification against existing methods, with separate comparisons for superspeciality and supersingularity. It also evaluates a 2^•-torsion test on a specified family of primes.

Performance of probabilistic approaches

  • Probabilistic superspeciality testing is timed on 100 Jacobians and compared with Cartier–Manin matrix computation; supersingularity testing is timed on 1000 Jacobians and compared with point counting.The measurements cover primes from 2^9 to 2^11.Source: §6 · p. 34, Figure 1 · p. 34

Performance of conclusive approaches

  • Conclusive verification is compared with point counting for 100 Jacobians of type b = −2 over primes p = c2^f − 1, with f from 2 to 22.The tested values of c are 5, 3 · 5, 3^2 · 5, and 3 · 5 · 7.Source: §6 · p. 35
  • For primes p = c2^f − 1, the 2^•-torsion test is compared with the pairing method over f from 9 to 293.These measurements cover primes from 2^13 to 2^297.Source: §6 · p. 35

7 Future Work

The work addresses testing in dimension 2 over Fp and identifies broader cases for future study. It also notes implementation-cost and Kummer-surface qualifications.

Future work

  • The results cover probabilistic and conclusive supersingularity and superspeciality testing in dimension 2 over Fp; higher dimensions and other Weil polynomials remain open directions.The case of abelian surfaces over Fp2 is only partially addressed, with results translating easily for Jacobians of types b ∈ {±1, ±2}.Source: §7 · p. 35

Kummer surfaces

  • For Kummer surfaces, identifying P and −P requires specialized results, and the probabilistic tests need further examination before their reliability can be claimed with certainty.Conclusive tests remain applicable because their pairings verify group structure rather than order.Source: §7 · pp. 35–36

Optimized arithmetic

  • The paper does not analyze scalar-multiplication and pairing costs in finite-field operations, though established techniques could provide such estimates.Examples named include differential addition chains and cubical arithmetic.Source: §7 · p. 36

Non-ordinary abelian surfaces

  • Non-ordinary abelian surfaces of p-rank 1 are left for future study; similar methods may apply, but require different technical derivations and pairing properties.Source: §7 · p. 36

A Non-trivial Automorphisms of Jacobians

The appendix describes non-trivial reduced automorphisms used for genus-2 Jacobians. It gives representative curve actions and orders for several automorphisms.

A Non-trivial Automorphisms of Jacobians

B Classification of Superspecial Jacobians over Fp2

The appendix characterizes superspecial Jacobians over Fp2 through extremality or specified twisted superspecial cases. It gives a verification route using minimal or maximal Jacobians and curve automorphisms.

Classification of Superspecial Jacobians over Fp2

Superspeciality Verification

  • Superspeciality over Fp2 can be verified by testing minimality or maximality, or by computing the associated curve's automorphism group and finding a minimal or maximal twist.Source: B Classification of Superspecial… · p. 42

Lifting Fp Curves

Loading 2610.01924v1…