🔢 mathematics

Refined Humbert Invariants in Supersingular Isogeny Degree Analysis

This paper introduces refined Humbert invariants for superspecial abelian surfaces to develop efficient algorithms for polarization isomorphism and geometric classification, while establishing new theoretical bounds and experimental insights for isogeny-based cryptography.

Original authors: Eda Kırımlı, Gaurish Korpal

Published 2026-07-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Eda Kırımlı, Gaurish Korpal

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where the security of your digital secrets doesn't rely on the difficulty of factoring huge numbers, but on the sheer complexity of navigating a vast, invisible maze. This is the frontier of post-quantum cryptography, a field preparing for a future where supercomputers might break today's codes. In this maze, the "walls" are made of special shapes called supersingular elliptic curves, and the "paths" connecting them are called isogenies. Think of these paths as secret tunnels. If you know the map, you can walk through quickly; if you don't, you're stuck wandering in the dark. For years, mathematicians have been trying to figure out the shortest possible tunnel between any two points in this maze. Knowing the length of the shortest path is crucial because if the path is too short, the maze isn't secure. But calculating these lengths has been like trying to measure the distance between two cities by walking every single street in between—slow, tedious, and prone to getting lost.

This paper, written by Eda Kirimli and Gaurish Korpál, introduces a clever new shortcut. Instead of walking the tunnels, they developed a way to look at the "fingerprint" of the maze itself. They use a mathematical tool called a "refined Humbert invariant," which acts like a unique ID card for the shape of the surface where these tunnels live. By analyzing these ID cards, the authors can instantly tell if a path exists and how long it is, without having to build the path first. They didn't just theorize about this; they built a computer program to test it on hundreds of different maze configurations. Their findings suggest that no matter how you arrange the maze, the shortest tunnel between any two points will never be longer than a specific limit related to the size of the maze (specifically, the square root of a prime number $p$ divided by the square root of 2). They also discovered that while some tunnel lengths are rare, the shortest ones appear surprisingly often. This work doesn't break the current codes, but it gives cryptographers a much sharper ruler to measure the safety of their mazes, ensuring they are built strong enough to withstand future attacks.

The Paper's Core Discovery

The authors focus on a specific type of mathematical object called a "principally polarized superspecial abelian surface." To use our analogy, imagine this as a super-complex, multi-dimensional version of a donut shape that serves as the foundation for the cryptographic maze. The paper's main achievement is the first-ever successful computation of "refined Humbert invariants" for these surfaces. Previously, these invariants were like theoretical ghosts—mathematicians knew they existed and were important, but no one had figured out how to actually calculate them for these specific shapes.

The authors created a step-by-step recipe (an algorithm) to calculate these invariants. Once they had the numbers, they used them to solve three major puzzles:

The Shape Detective: They built a test to determine the "geometric type" of the surface. Is it a simple product of two smaller shapes (like two donuts stuck together), or is it a more complex, single shape (like a twisted, single-loop surface)? This distinction is vital because different shapes have different security properties. Their method uses the invariant to check if the number "1" appears in a specific pattern; if it does, the shape is a simple product; if not, it's the complex kind.
The Tunnel Length Limit: They proved a new, tighter upper bound on the length of the shortest tunnel (isogeny) between any two supersingular elliptic curves. Previous estimates were looser, but the authors demonstrated mathematically that the shortest path will never exceed $\frac{\sqrt{p}}{\sqrt{2}}$ . They didn't just prove this on paper; they ran simulations for primes $p$ up to 659 (specifically those where $p \equiv 11 \pmod{12}$ ) and found that the actual shortest paths were consistently below this limit, often around $0.67\sqrt{p}$ .
The Frequency Map: They analyzed how often these shortest tunnels appear. Their experiments showed that the minimum isogeny degree (the length of the shortest tunnel) is not a rare fluke; it happens frequently across the different configurations they tested.

What They Did and Didn't Do

The authors explicitly ruled out the need for "brute-force" methods. In the past, to find the shortest tunnel, one might have had to compute the entire "endomorphism ring" (a complex algebraic structure describing all possible symmetries of the curve) or try to construct the isogenies directly. The authors show that these heavy computations are unnecessary. By using the refined Humbert invariants, they can determine the geometric type and the degree map (which tells the length of the tunnels) without ever explicitly computing the endomorphism rings or constructing the isogenies themselves.

They also clarified that while they can enumerate all possible "principal polarizations" (different ways to orient the surface), not every polarization leads to a unique invariant. Some different orientations result in the same mathematical fingerprint. Their algorithm accounts for this, filtering out duplicates to find the truly unique invariants.

How Sure Are They?

The paper presents a mix of rigorous proof and experimental verification.

Proven: The upper bound on the minimum isogeny degree ( $\frac{\sqrt{p}}{\sqrt{2}}$ ) is a mathematical proof. The logic follows from the properties of quadratic forms and Minkowski's inequality, a standard tool in geometry.
Verified by Simulation: The claim that the actual maximum of these minimums is approximately $0.67\sqrt{p}$ is supported by experimental evidence. The authors ran their algorithms on all primes $p$ between 10 and 659 (where $p \equiv 11 \pmod{12}$ ). The data collected in their tables and figures strongly supports the theoretical bound, showing that the observed values never exceeded the proven limit.
Suggested: The paper suggests that this approach offers a new perspective on the "fixed-degree isogeny problem" (finding a path of a specific length). They propose that computing these invariants could help solve problems in the "intermediate" range of degrees where other algorithms struggle, but they present this as a promising direction for future work rather than a fully solved problem.

In short, Kirimli and Korpál have handed cryptographers a new, high-tech measuring tape. They proved that the maze has a hard ceiling on how long the shortest path can be, and they showed that this ceiling is lower than previously thought. While they haven't broken the maze, they've given us a much better understanding of its dimensions, which is the first step in building a fortress that can truly withstand the quantum age.

Technical Summary: Refined Humbert Invariants in Supersingular Isogeny Degree Analysis

Problem Statement
The paper addresses a gap in the computational theory of superspecial abelian surfaces, specifically regarding the refined Humbert invariants introduced by Kani in 1994. While these invariants are known to underpin hard isogeny problems relevant to post-quantum cryptography, no prior work had successfully computed them for superspecial surfaces or enumerated their principal polarizations. The authors focus on principally polarized superspecial abelian surfaces (specifically products of supersingular elliptic curves $E_1 \times E_2$ ) to bridge this gap. The core challenge involves translating geometric data (divisors and polarizations) into computable arithmetic objects (integral quadratic forms) to analyze isogeny degrees without explicitly constructing isogenies or computing full endomorphism rings.

Methodology
The authors develop a computational framework based on the interplay between the Néron-Severi group $NS(A)$, intersection theory, and quaternion Hermitian forms.

Mathematical Formulation:
- For a principally polarized abelian surface $(A, \theta)$ , the refined Humbert invariant $q(A, \theta)$ is defined as a positive-definite quadratic form on the polarized Néron-Severi group $NS(A, \theta) = NS(A)/\mathbb{Z}\theta$ .
- When $A = E_1 \times E_2$ , divisors in $NS(A)$ can be represented as triples $(a, b, \phi)$ where $\phi \in \text{Hom}(E_1, E_2)$ . The intersection product is computed using a specific bilinear form derived from the degree map $q_{E_1, E_2}$ .
- A key relationship (Lemma 2) links the refined Humbert invariant to the degree map: $q(A, \theta) \cong x^2 + 4q_{E_1, E_2}$ . This allows the extraction of the degree map (which encodes isogeny degrees) directly from the invariant.
Algorithmic Pipeline:
- Enumeration of Polarizations (Algorithm 2): The authors enumerate principal polarizations on $E \times E$ by mapping them to positive-definite unimodular Hermitian matrices over a maximal order $\mathcal{O}$ of the quaternion algebra $B_p$ . They utilize a "simultaneous isometry" criterion based on auxiliary trace forms to identify isomorphic polarizations and reduce the search space.
- Computation of Invariants (Algorithm 1): For each polarization, the authors construct a $6 \times 6$ semi-definite matrix representing the quadratic form $\tilde{q}(A, \theta)$ . Using Simon's indefinite LLL algorithm, they reduce this to a $5 \times 5$ positive-definite matrix representing the quintic refined Humbert invariant.
- Verification: The Kannan-Fincke-Pohst algorithm is used to verify that the invariant represents the value 1, confirming the polarization is reducible (i.e., the surface is a product of elliptic curves).
- Uniqueness Check (Algorithm 3): The pipeline aggregates results, filtering for unique isometry classes of invariants using lattice isometry tests (Plesken–Souvignier algorithm).
Complexity: The authors analyze the runtime, estimating the dominant cost of enumerating polarizations as $O(p^5)$ under the conjecture that the search bound $A_{max} = O(p)$ .

Key Contributions

First Computation and Enumeration: The paper presents the first algorithm to compute refined Humbert invariants for principally polarized superspecial surfaces and the first enumeration of their principal polarizations.
Decision Algorithm for Isomorphism: A decision algorithm is provided to determine if two given principal polarizations on a superspecial surface are isomorphic, solving a problem previously lacking a dedicated algorithm for this specific context.
Geometric Type Determination: An efficient criterion is established to distinguish whether a principally polarized superspecial surface is the Jacobian of a genus-2 curve or a product of two elliptic curves. This is achieved by checking if the refined Humbert invariant represents the value 1 (Proposition 2).
Upper Bound on Minimum Isogeny Degree: The authors prove a new upper bound for the maximum of the minimum isogeny degrees between any pair of supersingular elliptic curves. They show that for a generic prime $p$ , this value $d$ satisfies:
$d \leq \sqrt{\frac{p}{2}}$
This bound is independent of the specific endomorphism ring structures of the curves.
Fixed-Degree Isogeny Perspective: The paper offers a new approach to the fixed-degree isogeny problem. By computing refined Humbert invariants, one can derive the degree map $q_{E_1, E_2}$ directly. This addresses the "intermediate" range of isogeny degrees (between small lattice-reduction methods and large KLPT-type algorithms) without requiring explicit endomorphism rings.

Results

Experimental Verification: The authors implemented their algorithms in Julia (using the Oscar/Nemo/Hecke packages) for all primes $p \equiv 11 \pmod{12}$ up to $p = 659$ .
Bound Validation: The experimental data confirms the theoretical bound $d \leq \sqrt{p/2} \approx 0.7071\sqrt{p}$ . The observed maximum minimum degrees were approximately $0.67\sqrt{p}$ , closely matching the theoretical constant.
Frequency Analysis: Experiments on the distribution of minimum isogeny degrees reveal that repetitions are common, and the minimum degree is frequently achieved within the proven bounds.
Data Completeness: For smaller primes, the algorithms successfully enumerated all $H$ principal polarizations (where $H$ is the class number of the principal genus) and identified all unique reducible refined Humbert invariants, matching theoretical predictions.

Significance and Claims
The paper claims to close a significant theoretical and computational gap in the study of superspecial abelian surfaces. By providing the first concrete methods to compute refined Humbert invariants, the authors enable:

A more efficient analysis of isogeny problems without the computational overhead of full endomorphism ring calculations.
A rigorous, unconditional upper bound on the minimum isogeny degree between supersingular curves, improving upon previous heuristic or less precise bounds.
A practical tool for analyzing the security and properties of isogeny-based cryptographic schemes (such as SQIsign) by characterizing the distribution of isogeny degrees and the geometric types of the underlying surfaces.

The authors remain modest regarding the immediate cryptographic impact, noting that while the method avoids explicit endomorphism rings, the computational complexity ( $O(p^5)$ for enumeration) currently limits its application to small primes. However, the theoretical framework and the derived bounds provide a new perspective on the hardness of isogeny problems.

The Paper's Core Discovery

What They Did and Didn't Do

How Sure Are They?

More like this