🔢 mathematics

Computing Isomorphisms between Products of Supersingular Elliptic Curves

This paper presents an efficient probabilistic Las Vegas algorithm that, under the Generalized Riemann Hypothesis, computes isomorphisms between products of supersingular elliptic curves in polynomial time by leveraging the Deuring correspondence to translate the problem into solving algebraic equations over quaternion orders.

Original authors: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer

Published 2026-07-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Pierrick Gaudry, Julien Soumier, Pierre-Jean Spaenlehauer

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 you have two magical boxes, each containing a pair of special, glowing orbs called "supersingular elliptic curves." These orbs are the building blocks of a very complex, high-dimensional shape known as an abelian variety. A famous mathematical rule called the Deligne-Ogus-Shioda theorem tells us that no matter how different these two boxes look on the outside, if they are built from the same type of magical orbs, they are actually identical inside. It's like saying two different-looking Lego castles are actually built from the exact same set of bricks, just arranged differently.

But here's the catch: the theorem says they are the same, but it doesn't tell you how to turn one castle into the other. It's like being told two locked safes contain the same treasure, but without the combination or the map to move the treasure from one to the other. For a long time, figuring out this "combination" was considered a nearly impossible puzzle, especially because the internal structure of these orbs (their "endomorphism rings") is incredibly hard to crack.

This paper is about finally finding the map. The authors, Pierrick Gaudry, Julien Soumier, and Pierre-Jean Spaenlehauer, present a new method to explicitly compute the transformation that turns one pair of these orb-boxes into another. They don't just guess; they provide a step-by-step recipe (an algorithm) that works efficiently, provided you already know the secret "blueprints" (the endomorphism rings) of the orbs.

The Magic Trick: Turning Geometry into Algebra
The authors' secret weapon is something called the "Deuring correspondence." Think of this as a universal translator. It takes the difficult, geometric problem of moving these glowing orbs around and translates it into a much friendlier language: algebra involving "quaternion numbers."

Imagine the orbs are moving through a 4-dimensional maze. Instead of trying to navigate the maze directly, the authors use the translator to convert the maze into a set of equations on a piece of paper. Specifically, they turn the problem of finding the right path into solving a system of quadratic and linear equations. It's like realizing that instead of climbing a mountain, you can just solve a math problem that tells you exactly where the summit is.

The Recipe: Breaking it Down
The paper focuses on the case where you have two pairs of orbs (dimension 2), which serves as the foundation for handling larger groups. Their algorithm works like a two-step dance:

The First Step: They figure out how to build a "matrix of isogenies." In our analogy, an isogeny is a specific type of magical tunnel connecting two orbs. They show how to take a starting set of tunnels and complete the picture to form a perfect, reversible transformation.
The Second Step: They use a clever trick involving "low-discriminant" subrings. Imagine some of the orbs have a special, simple internal pattern (like a low-discriminant imaginary quadratic order). If you have access to this simple pattern, you can solve the equations much faster.

The paper proves that if you have these blueprints, their algorithm can find the transformation in "expected polynomial time." This is a fancy way of saying the time it takes grows reasonably with the size of the problem, rather than exploding into infinity. They rely on a big mathematical assumption called the Generalized Riemann Hypothesis (GRH) to guarantee this speed, which is a common safety net in this field.

What They Don't Do (And What They Rule Out)
It's important to note what this paper doesn't claim. They are not saying that anyone can easily break the encryption systems built on these curves. In fact, the paper explicitly states that computing the endomorphism ring (the blueprints) in the first place is a "hard" problem that keeps cryptographic systems secure. Their work assumes you already have these blueprints. If you don't have the blueprints, their algorithm can't help you.

They also clarify that they are not solving the problem for any random abelian variety. They are specifically solving it for "superspecial" varieties, which are products of supersingular elliptic curves. They also don't claim to have solved the problem for all possible dimensions in one giant leap; instead, they solve the 2-dimensional case and show how to stack that solution to handle larger groups (dimension $g \ge 2$ ).

The Proof and the Tools
The authors didn't just theorize; they built a working prototype. They implemented their algorithm in a computer algebra software called Magma. However, they are careful to explain that their code currently outputs the "kernel ideals" (the mathematical descriptions of the tunnels) rather than the physical tunnels themselves. To get the actual tunnels, you would need to run a separate, standard conversion step, which they note is also efficient.

The paper is rigorous. They don't just suggest this might work; they provide a formal proof that their method is correct and that it runs in the time they claim, assuming the GRH holds true. They even developed new mathematical tools along the way, like a "quasi-linear quaternionic method" to divide one magical tunnel by another, which is a bit like having a specialized wrench that fits perfectly into the 4-dimensional gears of the problem.

In short, this paper takes a theorem that says "these two things are the same" and turns it into a practical instruction manual for "here is exactly how you turn one into the other," provided you have the right keys to start with. It's a significant step forward in understanding the hidden architecture of these complex mathematical shapes, using a blend of ancient algebra and modern computing power.

Technical Summary: Computing Isomorphisms Between Products of Supersingular Elliptic Curves

Problem Statement
The paper addresses the computational realization of the Deligne-Ogus-Shioda theorem, which guarantees that for any integer $g \ge 2$ , all dimension- $g$ superspecial abelian varieties defined over a finite field $\mathbb{F}_q$ are isomorphic (as unpolarized abelian varieties). Specifically, the authors tackle Problem 1.1: Given two sets of supersingular elliptic curves $E_1, \dots, E_g$ and $E'_1, \dots, E'_g$ defined over $\mathbb{F}_q$ , compute an explicit $\mathbb{F}_q$ -isomorphism between their products $E_1 \times \cdots \times E_g$ and $E'_1 \times \cdots \times E'_g$ .

The authors note that this is generally a difficult problem because computing the endomorphism ring of a supersingular curve is considered hard, a difficulty that underpins the security of certain cryptographic constructions. Consequently, this work operates under the specific assumption that the endomorphism rings of the input curves are already known and efficiently represented.

Methodology and Approach
The paper leverages the Deuring correspondence, which establishes an anti-equivalence between the category of supersingular elliptic curves over $\mathbb{F}_q$ and the category of invertible left modules over maximal orders in the quaternion algebra $B_{p,\infty}$ . This allows the authors to translate the geometric problem of computing isogenies into an algebraic problem involving quaternion orders.

The core strategy involves reducing the computation of isomorphisms to solving systems of linear and quadratic equations over the integers derived from norm equations. The approach relies on two primary technical pillars:

Quaternionic Division: The authors develop a quasi-linear method (Proposition 4.6) to divide an endomorphism by an isogeny within the quaternion algebra. This involves solving a system of linear equations over $\mathbb{Z}$ to find the basis of a resulting ideal.
Kani's Formula and Kernel Conditions: A key theoretical contribution is a necessary and sufficient criterion (Theorem 5.3) to determine if a pair of separable isogenies can form the first column of an isomorphism matrix. This criterion relies on a refined version of Kani's formula for the degree of isogenies between products of curves (Proposition 4.8), which ensures the resulting map is indeed an isomorphism by verifying degree constraints.

The algorithm proceeds by induction on the dimension $g$ . The base case ( $g=2$ ) is handled by Algorithm 6, which constructs a $2 \times 2$ matrix of isogenies representing the isomorphism. For $g > 2$ , Algorithm 1 recursively reduces the problem to computing a $(g-1)$ -dimensional isomorphism and a 2-dimensional isomorphism.

Key Contributions and Results

Polynomial-Time Algorithm: The authors present Algorithm 1, a probabilistic Las Vegas algorithm that computes the desired isomorphism. Under the Generalized Riemann Hypothesis (GRH), the algorithm runs in expected time that is linear in $g$ and polynomial in $\log(p)$ .
Explicit Construction: The paper provides a constructive proof of the Deligne-Ogus-Shioda theorem in the context of known endomorphism rings. The output is a $g \times g$ matrix of isogenies, represented efficiently via ideals in $B_{p,\infty}$ .
Subroutines:
- A method to construct an isomorphism matrix given its first column.
- A technique to compute isomorphisms of the form $E_2 \to E'_1 \times E$ when a non-scalar low-discriminant endomorphism is available.
Implementation: A proof-of-concept implementation in Magma is provided, which computes the quaternionic part of the isomorphism (outputting four kernel ideals). The authors note that recovering the explicit isogenies from these ideals can be done using existing algorithms (e.g., IdealToIsogeny) with polynomial-time complexity.

Significance and Claims
The paper claims to provide the first efficient algorithm for explicitly computing isomorphisms between products of supersingular elliptic curves, provided the endomorphism rings are known. The authors position this work as a foundational tool for higher-dimensional isogeny-based cryptography.

Specifically, the paper highlights two potential applications within the existing literature:

Access to Low-Discriminant Subrings: The ability to compute isomorphisms between a general superspecial abelian variety and a product of curves with known low-discriminant endomorphism subrings (such as $E_0$ where $p \equiv 3 \mod 4$ ) could facilitate access to these subrings, which are relevant in specific cryptographic settings.
Representation of Polarized Abelian Varieties: The algorithms contribute to the toolbox for the Ibukiyama-Katsura-Oort correspondence, which represents superspecial principally polarized abelian surfaces via $2 \times 2$ quaternion matrices. The authors suggest their methods can be used to compute this representation for surfaces that are not Jacobians of genus-2 curves.

The authors maintain a modest stance, emphasizing that their results are contingent on the input of known endomorphism rings and that the complexity bounds rely on GRH. They do not claim to break existing cryptographic schemes but rather to solve a specific algebraic problem that arises in the study of superspecial varieties.

Technical Summary: Computing Isomorphisms Between Products of Supersingular Elliptic Curves

More like this