Supersingularity and Superspeciality Verification of Abelian Surfaces

arXiv:2610.01924 · math.NT, cs.CR · Submitted 2026-10-01 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Supersingularity and Superspeciality Verification of Abelian Surfaces".

Elias: Supersingular abelian surfaces are essential for isogeny-based cryptography, and this work provides efficient algorithms to verify supersingularity and superspeciality for these objects over finite fields.

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So, wrapping up the discussion on "Supersingularity and Superspeciality Verification of Abelian Surfaces," the paper by Corte-Real Santos, Lorenzon, and Reijnders presents a set of new verification tools for these objects. The main thrust is developing both efficient Monte Carlo tests and conclusive algorithms to verify supersingularity over F p, alongside methods to check minimality, maximality, and superspeciality for abelian varieties of any dimension.

Elias: That's right; the authors give us a probabilistic O(p) test for general supersingularity and a conclusive test when the order is smooth. They also provide specific conditions—like checking if pP = plus or minus P or using pairing checks in F p squared —that can confirm minimality, maximality, and superspeciality with very low failure probabilities.

Priya: What this means in the broader context is that researchers now have concrete ways to computationally determine the structural properties of these surfaces, which informs how we build and trust the mathematical foundations of post-quantum cryptography.

Nadia: It gives us a way to efficiently confirm whether an object is supersingular or superspecial, which directly impacts the security assumptions in protocols like those relying on isogenies.

Elias: The implication for cryptographers is that they can implement faster checks during protocol setup or key generation, provided they are willing to accept the appropriate level of probabilistic certainty depending on which algorithm you choose.

Nadia: Overall, this work provides practical algorithms that help us move past the theoretical difficulty of verifying supersingularity in a concrete setting.

Elias: Precisely; it moves the discussion from just establishing existence to actually testing these properties efficiently, which is crucial for real-world implementation.

Priya: It’s an important contribution because it bridges the gap between abstract algebraic theory and practical computational verification methods for these specific objects.

Conclusion: Nadia: So we're wrapping up our discussion on "Supersingularity and Superspeciality Verification of Abelian Surfaces," focusing now on who wrote this and what it actually means for us in practice.

Elias: I think it’s important to remember that the authors are Corte-Real Santos, Lorenzon, and Reijnders; they're the ones who put these verification algorithms together.

Priya: From a privacy perspective, the core idea here is giving us tools to confirm if an abelian surface has those specific supersingular or superspecial properties over finite fields.

Nadia: Exactly; it’s about moving from just believing something is true to actually proving it using these new methods for verification.

Elias: The implication for cryptography, particularly the lattice-based systems that rely on isogenies, is that we can perform these checks much more efficiently during setup or key exchange processes.

Priya: And the real impact is in establishing stronger theoretical guarantees about the security of these constructions when working over specific finite fields.

Nadia: It gives us a concrete way to ensure the mathematical objects we use in those systems have the right structure for secure operation.

Elias: We need to keep thinking about which parameters might still allow an attacker to bypass these checks, though, because there are always edge cases in these types of proofs.

Priya: That's what I'm interested in next—we should talk about those specific failure probabilities and what that means for real-world data analysis.

Nadia: Right, so we’re going to look closer at those probabilistic limits and how they translate into actual security assurances for the systems we build.

Maria Corte-Real Santos, Gioella Lorenzon, Krijn Reijnders

Ecole Normale Sup´erieure de Lyon · COSIC, KU Leuven

math.NT, cs.CR

Submitted: 2026-10-01

Updated: 2026-10-01

Code: https://github.com/KULeuven-COSIC/supersingularity-and-superspeciality

License: http://creativecommons.org/licenses/by-sa/4.0/

Importance score: 88/100

The gist: Supersingular abelian surfaces are essential for isogeny-based cryptography, and this work provides efficient algorithms to verify supersingularity and superspeciality for these objects over finite

Key concepts

Supersingularity: A property of an abelian variety (like a surface) over a finite field where its characteristic polynomial of Frobenius has a specific form. The paper uses Monte Carlo algorithms to probabilistically check this property in very few steps, which is vital for verifying cryptographic objects.
Superspeciality: A stronger condition than supersingularity, implying the abelian variety has a very specific structure related to its endomorphism ring. Superspecial varieties are often associated with simpler structures and are important for certain cryptographic constructions.
Characteristic Polynomial of Frobenius: This is a polynomial derived from the action of the Frobenius map on an abelian variety over a finite field. The paper shows that supersingular surfaces must have this polynomial take a particular form, like x⁴ - bpx² + p², where 'b' is restricted to small integer values.
Pairing-Based Method: A technique using bilinear maps (pairings) from the abelian variety to multiplicative groups. This method allows for conclusive verification of maximality and supersingularity, especially for surfaces over Fp², by checking conditions on the size of images derived from these pairings.

Terminology

Verification — 50× in this paper · explained in 2 episodes
Nadia — 7× in this paper · explained in 2 episodes
Trace — 7× in this paper · explained in 2 episodes
Elias — 6× in this paper · explained in 2 episodes
Generalization — 6× in this paper · explained in 13 episodes
Degeneracy — 4× in this paper · explained in 3 episodes
Core — 3× in this paper · explained in 2 episodes
Benchmarking — 2× in this paper · explained in 3 episodes
Benchmark — 1× in this paper · explained in 2 episodes
Theoretical Guarantees — 1× in this paper · explained in 2 episodes

Summary

Supersingular abelian surfaces are essential for isogeny-based cryptography, and this work provides efficient algorithms to verify supersingularity and superspeciality for these objects over finite fields. The gist: an efficient Monte Carlo algorithm to verify if an abelian surface over Fp is supersingular in O(log p) with negligible failure probability, and a conclusive algorithm if the order is smooth.

Verification of Extremality (Minimality/Maximality)

The paper develops algorithms to efficiently verify whether an abelian variety of any dimension is minimal or maximal, which implies superspeciality. Algorithm 2 checks this property by sampling points: If [p]P = ±P, return true. This algorithm runs in O(log p) time and returns true for any minimal or maximal abelian variety over Fq. The failure probability for a non-extremal variety is at most O(p−1).

Structural Analysis of Supersingular Orders

The research analyzes the structure of supersingular Jacobians over Fp, deriving key results that underpin the testing algorithms. This analysis establishes that supersingular abelian surfaces are characterized by specific forms of their characteristic polynomial: A is supersingular if and only if its characteristic polynomial of Frobenius is of the form φA(x) = x4 − bpx2 + p2, where b ∈ ε-2, -1, 0, 1, or 2. The possible orders are explicitly listed based on the parameter b: (p + 1)2 if b = −2, p2 + p + 1 if b = −1, etc.

Superspeciality Testing for Jacobians

The paper provides a conclusive algorithm for testing superspeciality of Jacobians over Fp, Algorithm 3. This algorithm generalizes the minimality/maximality test by checking twists: Let J be a Jacobian of dimension g of a curve C over Fq with q = p or p2. It returns true if J or any of its twists is maximal or minimal, which shows superspeciality by Lemma 2.2. The runtime is O(g log p), and the failure probability is at most O((g − 1)·p−1).

Conclusive Testing for Abelian Surfaces over Fp2

For abelian surfaces over Fp2, the paper presents a conclusive pairing-based method (Algorithm 5) to verify maximality. This algorithm samples four random points and checks if "NZ > 8p3 + 8p, which implies the surface is maximal and thus superspecial. The proof relies on the width-bound argument" applied to the Hasse–Weil interval over Fp2, ensuring that if this condition is met, A must have order (p + 1)4.

Conclusive Testing for General Supersingularity

Algorithm 4 provides a Monte Carlo test for supersingularity of abelian surfaces over Fp in O(log p) time. This algorithm relies on Theorem 4.7, which states that if random points P and Q satisfy specific conditions related to the supersingular orders n = p2 − bp + 1 or n = p ± 1, then it is extremely likely that A is supersingular (at least for large p).

Conclusive Testing using Pairings

The conclusive testing section discusses pairing-based methods to verify supersingularity, particularly for types b = ±2. It demonstrates that if the matrix M derived from pairings satisfies "im M > W, where W is the width of the Hasse–Weil interval, then A is supersingular of type b = 2." This method requires computing discrete logarithms in µn and utilizes a generalized approach to handle non-trivial isotropy conditions.

Classification via Automorphism Groups

For conclusive verification over Fp2, Theorem B.1 provides a classification for superspecial Jacobians based on their characteristic polynomial and the geometric automorphism group RA(C). A Jacobian J is superspecial if it belongs to one of six types, such as type (0, -2), e.g. φJ (x) = (x − p)2(x + p)2, or type (±2, 3), e.g. φJ (x) = (x2 ± px + p2)2. This allows for efficient verification by computing the automorphism group of the associated hyperelliptic curve C.

Benchmarking and Performance

The paper compares various algorithms, including Algorithm 3 against the computation of the Cartier–Manin matrix for superspeciality, and IsSupersingular against point counting for supersingularity. The results show that the 2•-torsion test (Lemma 5.15) over Fp is a significant speed-up compared to conclusive tests from Section 5 when applied to primes where "2f p + 1 and f ≈ log2 p.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper, Supersingularity and Superspeciality Verification of Abelian Surfaces, which provides novel, efficient algorithms for verifying supersingularity and superspeciality of abelian varieties (specifically Jacobians) over finite fields.

Here are the specific improvements that can be made to AI systems by leveraging the methodologies and results presented in this paper:

)Specific Improvements for AI Systems:

Generation of Secure, High-Dimensional Cryptographic Primitives:
Enhanced Security Validation for Lattice/Isogeny-Based Cryptography:
Automated Classification of Algebraic Structures in Post-Quantum Systems:

)Detailed Capabilities of the Improved AI System:

Generation of Secure, High-Dimensional Cryptographic Primitives:

A specialized AI system could be trained to utilize the derived efficient verification algorithms (Algorithm 4 and Algorithm 5).

It can automatically generate candidate supersingular abelian surfaces over finite fields with specific desired orders, ensuring they possess the required supersingularity properties (e.g., checking if a surface is of type 'b' using its characteristic polynomial coefficients).
It can efficiently search for minimal or maximal varieties (Algorithm 2) to ensure that generated cryptographic keys or parameters are structurally optimal for security proofs (i.e., ensuring they are superspecial).

Enhanced Security Validation for Lattice/Isogeny-Based Cryptography:

The paper provides tools to verify the security assumptions underpinning isogeny-based cryptography, particularly related to SIDH/SIKE and related schemes.

The AI can perform rapid probabilistic supersingularity testing (Algorithm 4) on candidate abelian surfaces derived from isogeny computations, drastically reducing the time spent on manual or slow point-counting verification.
It can conduct conclusive verification (Section 5) to provide mathematical certainty about the supersingularity of a Jacobian, which is critical for rigorous security audits in protocols relying on these objects.
The system can leverage the results concerning twist classification (Theorem B.1) to classify the structure of Jacobians over extension fields like Fp2, which is essential for understanding and mitigating side-channel attacks that might exploit field extension properties.

Automated Classification of Algebraic Structures in Post-Quantum Systems:

The paper establishes a robust framework for classifying abelian varieties based on their Ekedahl–Oort stratification (Section 2) and the structure of their torsion groups (Lemma 3.15).

The AI can automatically analyze the Weil polynomial coefficients and group structures to immediately classify an unknown abelian variety into one of the five supersingular types (Type b = -2, -1, 0, 1, or 2) over Fp.
For Jacobians of genus 2 curves (Section 3.5), the AI can use the factorization type of the curve's defining polynomial to immediately determine its superspeciality status without performing computationally expensive matrix computations (like computing the Cartier-Manin matrix).
It can efficiently compute and classify geometric automorphism groups (RA(C)) using known results from classification tables (Table 3) and specific properties of genus-2 curves, allowing for a rapid assessment of whether a Jacobian is superspecial based on its automorphism group structure.

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 F p is supersingular in O(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 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.