🔢 mathematics

Equivalent computational problems for superspecial abelian surfaces

This paper establishes reductions and equivalences between various computational problems concerning the endomorphism rings of principally polarized superspecial abelian surfaces, specifically linking the computation of Ibukiyama-Katsura-Oort matrices to that of unpolarized isomorphisms.

Original authors: Mickaël Montessinos

Published 2026-01-27

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mickaël Montessinos

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

The Big Picture: A Digital Locksmith's Dilemma

Imagine you are a master locksmith. In the world of modern cryptography (the art of secret codes), there is a special type of "lock" based on shapes called Abelian Surfaces. These are complex, multi-dimensional geometric objects that exist over finite fields (think of them as a universe with a limited number of points, like a pixelated grid).

Specifically, the paper focuses on Superspecial Abelian Surfaces. These are the "perfect" locks in this universe. They are so special that, mathematically speaking, they all look the same if you ignore their internal "polarization" (a specific orientation or twist). It's like having a million identical-looking golden spheres; they are all the same shape, but they might be painted with different patterns or have different internal gears.

The security of future encryption systems relies on the fact that it is very hard to figure out the internal gears (the Endomorphism Ring) of these locks just by looking at the outside. If you can figure out the gears, you can break the lock.

The Problem: Different Ways to Describe the Same Key

The author, Mickaël Montessinos, asks a fundamental question: If you have one way of describing the internal gears of these locks, can you easily convert it into any other way of describing them?

In the paper, the author identifies three main ways to "describe" or "know" these locks:

The Blueprint (The Ibukiyama-Katsura-Oort Matrix): This is a specific mathematical table (a matrix) that acts like a blueprint. It tells you exactly how the lock is twisted and oriented. In the world of cryptography, this is the "input" needed for certain algorithms to work.
The Gear List (The Endomorphism Ring): This is a list of 16 specific "moves" or operations that can be performed on the lock without breaking it. If you know these 16 moves, you know the internal structure of the lock.
The Map (Unpolarised Isomorphism): This is a map that shows you how to travel from a "reference lock" (a standard, known lock) to your specific lock. It tells you how to transform one into the other.

The Main Discovery: They Are All the Same

The paper proves that these three descriptions are mathematically equivalent.

Think of it like this:

If you have the Blueprint (the Matrix), you can instantly build the Gear List.
If you have the Gear List, you can instantly draw the Blueprint.
If you have the Map (knowing how to get from the reference lock to yours), you can figure out both the Blueprint and the Gear List.

The author shows that if you can solve any one of these problems efficiently, you can solve all of them efficiently. This is a huge deal because it means cryptographers don't need to worry about which "representation" of the lock is the hardest to crack; they are all equally hard (or equally easy).

How the Author Did It (The "How-To")

The paper is divided into two main scenarios, depending on how the lock is built:

Scenario A: The Lock is a "Product" (Two simple locks stuck together)
Imagine your complex lock is just two smaller, simpler locks (elliptic curves) glued together.

The author shows that if you know the gears of the two small locks, you can easily figure out the gears of the big lock.
Conversely, if you have the blueprint of the big lock, you can break it down to find the gears of the small locks.
Analogy: It's like knowing the recipe for a cake (the big lock) is just knowing the recipes for the flour and the eggs (the small locks) multiplied together.

Scenario B: The Lock is a "Jacobian" (A complex, single shape)
Sometimes the lock isn't two simple locks glued together; it's a single, complex shape (like a hyperelliptic curve).

Here, the math is trickier. The author proves that if you have the Blueprint, you can still find the Gear List.
However, going the other way (from Gears to Blueprint) requires a bit of extra information. It's like having a list of ingredients but needing a specific chef's note to know exactly how to arrange them on the plate.
The "Orientation" Trick: The author introduces a concept called "orientation." Imagine two people holding the same map. One is holding it right-side up; the other is holding it upside down. They both see the same roads, but the directions are flipped. The author proves that if you can detect if your "map" is flipped (using how the lock reacts to tiny changes called "differentials"), you can correct it and find the true Blueprint.

The "KLPT" Algorithm: The Magic Tool

The paper relies heavily on a tool called the KLPT algorithm.

Analogy: Imagine you are trying to walk from City A to City B, but you can only take steps of specific sizes (like 2 steps, 4 steps, 8 steps). The KLPT algorithm is a magical GPS that tells you the exact sequence of steps to get there, even if the terrain is weird.
The author uses this tool to show that you can "walk" from a known reference lock to any unknown lock, and in doing so, you can translate the "Blueprint" into the "Gear List" and vice versa.

What the Paper Does NOT Say

It is important to stick to what the paper claims:

It does not say that these locks are currently broken. It says that if you can solve one of these math puzzles, you can solve the others.
It does not propose a new encryption system. It analyzes the mathematical relationships between existing concepts.
It does not claim that all these problems are equally easy in every single case. For the "Jacobian" (complex shape) case, converting from gears to the blueprint requires a specific type of "good" gear list, not just a basic one.

Summary

In simple terms, this paper is a translation guide for a very complex mathematical language. It proves that three different ways of describing the "internal structure" of a special type of cryptographic lock are actually just different languages for the same thing. If you can speak one of these languages (solve one problem), you can instantly translate it into the others. This helps cryptographers understand the true difficulty of breaking these future-proof security systems.

Technical Summary: Equivalent Computational Problems for Superspecial Abelian Surfaces

1. Problem Statement
This work addresses the computational complexity of determining the endomorphism ring of principally polarised superspecial abelian surfaces (PPSAS) over a finite field $\mathbb{F}_q$ (where $q=p^2$ ). While the problem of computing the endomorphism ring of supersingular elliptic curves (dimension 1) has been extensively studied and proven equivalent to the Isogeny Path Problem, the higher-dimensional case (dimension 2) presents distinct challenges.

In dimension 2, all unpolarised superspecial abelian varieties are isomorphic to $E^2$ for a supersingular elliptic curve $E$ . Consequently, their endomorphism rings are all isomorphic to $M_2(\mathcal{O})$ , where $\mathcal{O}$ is a maximal order in the quaternion algebra $B_{p,\infty}$ . Therefore, the "known endomorphism ring" is not a unique identifier of the variety's structure but rather a representation of the ring itself. The paper investigates the equivalence between various computational representations of this structure, specifically:

The Ibukiyama-Katsura-Oort (IKO) matrix: A Hermitian matrix in $M_2(\mathcal{O})$ characterizing the principal polarisation.
Effective/Good representations of the endomorphism ring: Algorithms that evaluate a basis of endomorphisms (and potentially their Rosati involution).
Unpolarised isomorphisms: Computing an isomorphism between two PPSAS.

2. Methodology
The paper employs algorithmic reductions to establish equivalences between these problems, relying heavily on the KLPT2 algorithm (a generalization of the KLPT algorithm to dimension 2) and the theory of orientations of maximal orders.

Reductions via Isogeny Chains: To compute unpolarised isomorphisms from a PPSAS (specifically a Jacobian of a genus 2 curve) to a product of elliptic curves, the author constructs a chain of $(2,2)$ -isogenies. By leveraging the known endomorphism rings of the elliptic curves, the algorithm computes an unpolarised automorphism that transforms the kernel of a $(2,2)$ -isogeny into a form allowing the recovery of a product structure.
Orientation and Rosati Involution: To recover the IKO matrix from an endomorphism ring, the paper utilizes the concept of orientations. An orientation is defined as a surjective homomorphism from the endomorphism ring to $M_2(\mathbb{F}_q)$ induced by the action of endomorphisms on global differentials. The paper proves that an isomorphism between endomorphism rings is induced by an unpolarised isomorphism of the underlying varieties if and only if it preserves these orientations.
Correction Mechanism: Since an isomorphism of rings may not be induced by a variety isomorphism (it may differ by an outer automorphism), the proposed algorithm checks the action on differentials. If the orientation is not preserved, the algorithm applies a specific outer automorphism (conjugation by a generator of a specific ideal) to correct the isomorphism, thereby recovering the correct Rosati involution and the IKO matrix.

3. Key Contributions and Results
The paper establishes the following equivalences and reductions under the Generalized Riemann Hypothesis (GRH) and the assumptions required for the KLPT2 algorithm:

Case 1: Products of Supersingular Elliptic Curves:
If a PPSAS is presented as a product of two supersingular elliptic curves, the following problems are proven equivalent:
1. Computing the IKO matrix.
2. Computing an effective representation of the endomorphism ring (a basis of endomorphisms).
3. Computing an unpolarised isomorphism from a reference product (e.g., $E_0^2$ ) to the target surface.
4. Computing a "good" representation (including Rosati involution data).
Case 2: General PPSAS (including Jacobians):
For a general PPSAS (including those presented as Jacobians of genus 2 curves):
- Computing the IKO matrix is equivalent to computing a good representation of the endomorphism ring.
- Computing an effective representation of the endomorphism ring reduces to computing the IKO matrix.
- Computing an unpolarised isomorphism to another PPSAS with a known IKO matrix reduces to computing the IKO matrix.
- Note: The paper explicitly states that while reductions exist, the equivalence between computing the IKO matrix and computing a good representation for Jacobians is not fully proven in the same bidirectional sense as the product case, though strong reductions are provided.

4. Significance and Claims
The author claims that this work clarifies the landscape of computational hardness assumptions for cryptographic schemes based on higher-dimensional isogenies. By establishing these equivalences, the paper demonstrates that the security of such schemes relies on the difficulty of computing the IKO matrix, just as one-dimensional schemes rely on the difficulty of computing maximal orders or isogeny paths.

The paper notes a practical limitation: while the reduction from the endomorphism ring (with additional information) to the IKO matrix is polynomial-time, it is not currently practical due to large constant factors in the complexity of computing isomorphisms between central simple algebras.

The work distinguishes itself from concurrent research (specifically [20]) by explicitly proving the equivalence between the IKO matrix and the endomorphism ring computation in the context of products of elliptic curves, whereas other works focus on Hermitian modules without establishing this specific equivalence.

5. Limitations and Open Problems
The author acknowledges that the neat equivalence diagram holds primarily when restricting to products of supersingular elliptic curves. For Jacobian surfaces, the equivalence between all considered problems is not fully established. The paper leaves as an open problem the identification of more appropriate representations of maps from Jacobian varieties that would allow for a complete equivalence diagram in the general case.