⚛️ quantum physics

Isogeny Graphs in Superposition and Quantum Onion Routing

This paper proposes a post-quantum secure quantum onion routing scheme that leverages abelian ideal class group actions and isogeny graphs to enable layered symmetric encryption with both local and non-local key exchanges, offering implementation paths via universal quantum oracles and continuous-time quantum walks.

Original authors: Eleni Agathocleous, Tobias Hartung, Karl Jansen, Lukas Mansour

Published 2026-02-03

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Eleni Agathocleous, Tobias Hartung, Karl Jansen, Lukas Mansour

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 Idea: A Quantum "Secret Handshake" for Anonymous Messages

Imagine you want to send a secret letter to a friend, but you don't want anyone in between (like the post office or a neighbor) to know who you are or where the letter is going. In the digital world, we currently use a system called Onion Routing (like the Tor network).

How it works classically:
Think of your message as a letter wrapped in multiple layers of plastic.

You (Alice) wrap the letter in three layers. The first layer is addressed to the first relay, the second to the middle relay, and the third to your friend (Bob).
Relay 1 peels off the first layer. They see the address for Relay 2, but they don't know who Alice is or who Bob is.
Relay 2 peels off the second layer. They see the address for Bob, but they don't know Alice.
Bob peels off the last layer and reads the letter.

The Quantum Problem:
The authors of this paper tried to build this same system for quantum computers. However, there is a major snag.

In the classical world, we use "Public Key" encryption (like a lockbox where anyone can lock it, but only the owner has the key to open it). This is great for onion routing because you can lock layers without knowing the owner's secret key yet.
In the quantum world, the laws of physics say that most operations must be reversible. This makes "Public Key" encryption very hard to layer up like an onion. Usually, quantum encryption requires both parties to already share a secret key, which defeats the purpose of an anonymous network.

The Solution: The "Magic Garden" of Math

To solve this, the authors propose a new way to build the "locks" for the onion layers. Instead of using standard locks, they use a concept from advanced number theory called Ideal Class Group Actions.

The Analogy: The Magic Garden
Imagine a giant garden with a specific number of unique flowers (let's say 11 flowers, though in reality, there are billions).

There is a special "Magic Wand" (the Class Group Action).
If you wave the wand at a flower, it instantly transforms it into a different flower in the garden.
The Secret: The wand is reversible. If you wave it once, Flower A becomes Flower B. If you wave it again (or use the "reverse wand"), Flower B goes back to Flower A.
The Hard Part: If I show you Flower A and tell you it became Flower B, it is incredibly difficult for a computer (even a super-powerful quantum one) to figure out how many times or which specific way the wand was waved to get from A to B. This is the "hard problem" that keeps the system secure.

How the "Quantum Onion" Works

The authors propose a protocol where the "layers" of the onion are these magic wand transformations.

The Setup: Everyone agrees on a starting flower (a public "j-invariant").
The Chain:
- Carol (Receiver) picks a secret number of wand-waves. She transforms the starting flower and sends the result to Bob.
- Bob picks his own secret number of wand-waves. He transforms Carol's flower and sends it to Alice.
- Alice (Sender) picks her secret number of wand-waves. She transforms Bob's flower.
The Return Trip:
- Alice sends the flower back to Bob. Bob uses his "reverse wand" to undo his own waves. He sends it to Carol.
- Carol uses her "reverse wand" to undo her waves.
The Result: Because the magic wand is "commutative" (the order you wave it doesn't matter, only the total number of waves), Carol ends up with a flower that has been transformed only by Alice's secret waves.
The Message: Alice uses this final flower as a "key" to unlock a quantum message she sent along with the flower. Carol uses the flower to unlock the message.

Why is this special?
In the middle of this process, the "flower" is not just a single object; it is a Quantum Superposition.

Imagine the flower isn't just one specific type, but a shimmering cloud of all possible flowers at once.
As the message travels through the network, it travels as this cloud.
If a spy (Bob or a hacker) tries to peek at the flower to see what it is, the cloud collapses into a single random flower. They learn nothing about the path or the secret key. They only see a random flower, which gives them no clues about who sent the message or where it's going.

Two Ways to Build the "Magic Wand"

The paper suggests two ways to actually build this system on a computer:

The Universal Oracle (The "Black Box"): Imagine a magical machine that, when you feed it a flower and a secret number, instantly shows you the new flower. The authors show how to build a quantum circuit that acts like this machine using standard quantum gates.
The Continuous Walk (The "Quantum Stroll"): Instead of a machine, imagine the flower "walking" along a path in the garden. The authors suggest using Continuous-Time Quantum Walks. This is like the flower being a wave that ripples through the garden simultaneously, exploring all paths at once. This is a more "native" quantum approach, which they are exploring in a separate paper.

The "Onion" Example (The 5-Actor Demo)

To prove this works, the authors wrote a small computer program (using Qiskit) with 5 people: Alice, Bob, Carol, Dave, and Eve.

Alice wants to send a message to Eve.
Bob, Carol, and Dave are the middlemen.
They use a tiny version of the "Magic Garden" with only 11 flowers to keep the math simple.
The program simulates the "cloud" of flowers traveling up and down the chain.
The Result: Eve successfully receives the secret key (the specific flower Alice created) without Bob, Carol, or Dave ever knowing what the final key was. They only saw random flowers or clouds of flowers.

Why This Matters (According to the Paper)

Security: The math behind the "Magic Wand" is believed to be unbreakable, even by future quantum computers. This makes it a candidate for "Post-Quantum" cryptography.
Anonymity: Because the data travels as a superposition, no single relay can link the sender to the receiver.
Simplicity: The whole system relies on just one type of math problem (the Class Group Action), making it easier to build and less prone to errors than mixing different encryption types.

In short: The paper invents a new way to send secret messages through a network of strangers using quantum physics and advanced math. It replaces the "locks and keys" of today with a "magic garden" where the path is hidden in a cloud of possibilities, ensuring that even if someone tries to peek, they only see a random flower.

Technical Summary: Isogeny Graphs in Superposition and Quantum Onion Routing

Problem Statement
The paper addresses the fundamental challenge of constructing a Quantum Onion Routing (QOR) scheme. Classical onion routing achieves anonymity by layering encryption so that no single relay can link a sender to a destination. However, a direct quantum analogue faces a core obstacle: quantum operations are unitary and thus reversible, implying that any encryption scheme where a message is encoded as a quantum state and encrypted via a key-dependent function must inherently be symmetric. Classical onion routing relies heavily on public-key encryption to establish layered keys; in a quantum setting, asymmetric encryption is difficult to layer if the message is a genuine quantum state. Furthermore, existing quantum key distribution (QKD) or quantum public-key schemes often require distinct underlying problems, complicating the integration of a unified, layered protocol.

Methodology
The authors propose a QOR scheme based on symmetric quantum encryption instantiated via the abelian ideal class group action from the Theory of Complex Multiplication. The protocol leverages the hardness of the vectorization problem (inverting the group action), which is believed to remain difficult even for quantum adversaries, underpinning post-quantum schemes like CSIDH.

The methodology involves three primary components:

Key Establishment:
- Local Session Keys: Neighboring nodes in the communication chain (e.g., guard, middle, exit) establish shared secret keys via a Diffie-Hellman exchange using the ideal class group action.
- Global Session Key: The sender and receiver establish a global key to facilitate the final decryption step.
Graph-Theoretic Foundation: The protocol maps the ideal class group action to isogeny graphs. Specifically, the authors utilize the isomorphism between the isogeny graph and the Cayley graph of the ideal class group. They analyze these graphs through the lens of association schemes and their Bose–Mesner algebra. This algebraic structure ensures that the unitary operators corresponding to different group actions commute, a critical property for allowing multiple layers of encryption to be applied and removed in any order (commutativity of layers).
Implementation Paths: The paper outlines two theoretical implementation paths:
- Universal Quantum Oracle: A path using a universal oracle that evaluates the class group action with polynomially many quantum resources.
- Continuous-Time Quantum Walks (CTQWs): An intrinsically quantum approach where the group action is interpreted as a walk on the isogeny graph Hamiltonian. This path is noted as being developed in a companion paper.

Protocol Mechanics
The proposed protocol (Procedure 1 and 2) involves a sender (Alice), intermediaries (Bob, etc.), and a receiver (Carol).

Initialization: A public $j$ -invariant $j_0$ is fixed.
Layering: The receiver generates a secret group element and sends a transformed state to the first intermediary. Each intermediary applies their secret group action (encryption) to the state.
Superposition and Hiding: To prevent traffic analysis and cloning attacks, the protocol utilizes superposition. The receiver prepares a uniform superposition over a subset of the isogeny cycle. The message is encrypted using a circuit derived from the sender's $j$ -invariant.
Transmission: The quantum state (containing the encrypted message and the evolving $j$ -invariant) is passed through the chain. Each node applies their unitary operator (encryption) and passes the state forward.
Decryption: The receiver, retaining an "index register" that tracks the superposition steps, performs a final measurement and uncomputation (inverse operations) to recover the sender's $j$ -invariant ( $j_A$ ). This $j_A$ is then used to decrypt the message via the inverse circuit $C(j_A)^{-1}$ .

Key Contributions and Results

Symmetric Quantum Onion Routing: The paper successfully constructs a QOR scheme that relies solely on symmetric encryption layers derived from the ideal class group action, bypassing the need for quantum public-key encryption for the onion layers.
Algebraic Formalization: The authors connect isogeny graphs to association schemes, utilizing the Bose–Mesner algebra to formally prove the commutativity of the unitary operators. This mathematical grounding is essential for the feasibility of layered quantum encryption.
Security Analysis: The security relies on the hardness of the vectorization problem for the ideal class group action. The paper argues that in the quantum setting, intermediate $j$ -invariants are not accessible without measurement (which yields random results), and the protocol design ensures only the receiver performs the final measurement.
Implementation Demonstration: The paper provides a Qiskit example involving five actors (A, B, C, D, E). While deliberately small and exponential in resources (using a class group of order 11 over $\mathbb{F}_{311}$ ), this example explicitly illustrates the mechanics of the protocol, including the use of "mapper oracles" and the handling of index registers.
Security Considerations: The authors discuss potential attacks, such as imperfect cloning and measurement at multiple points. They conclude that breaking the scheme requires solving the underlying vectorization problem, and even if the $j$ -invariant is recovered, the message remains protected by the Diffie-Hellman encryption layer.

Significance and Claims
The paper claims to overcome the intrinsic obstacles of quantum onion routing by basing the entire scheme on a single, hard mathematical problem (the ideal class group action) compatible with both classical and quantum cryptographic needs.

Feasibility: It demonstrates that layered symmetric quantum encryption is possible by exploiting the commutative nature of the ideal class group action.
Interdisciplinary Bridge: The work advances the intersection of post-quantum cryptography and quantum computing by implementing an isogeny-based scheme within a quantum protocol execution routine.
Modesty: The authors are modest regarding efficiency. They explicitly state that the Qiskit example is designed to illustrate mechanics rather than efficiency. They acknowledge that the implementation of the class group action oracles is an active research area and that the CTQW approach is developed in a companion work. The paper does not claim to have solved the efficiency problem of large-scale isogeny computations but rather provides the theoretical framework and a proof-of-concept for the routing protocol itself.

In summary, the paper proposes a novel, theoretically sound framework for quantum onion routing that utilizes the algebraic properties of isogeny graphs to enable secure, layered, symmetric quantum encryption, supported by a concrete (though small-scale) quantum circuit implementation.