⚛️ quantum physics

CRT-Decomposed $Σ$ -Protocols for CSIDH

This paper presents a CRT-decomposed $\Sigma$ -protocol for CSIDH that achieves perfect completeness, zero-knowledge, and efficient straight-line extraction in the QROM without heuristic assumptions, while rigorously verifying its algebraic correctness and demonstrating that its security currently relies on future parameters with large prime factors due to a significant reduction in classical attack cost when CRT hop curves are published.

Original authors: I. Dey, I. Cherkaoui

Published 2026-09-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: I. Dey, I. Cherkaoui

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

In the digital world, privacy often relies on a delicate balance: a user wants to prove they have the right to spend money or access a service without revealing their identity or the specific details of the transaction. This is the realm of blind signatures, a cryptographic tool that allows a bank to certify a coin without ever seeing where it will be spent. For decades, the security of these systems has rested on mathematical puzzles involving large numbers, but the rise of powerful quantum computers threatens to solve those puzzles, rendering current privacy protections obsolete. To counter this, scientists are turning to a different kind of mathematics based on the geometry of elliptic curves, specifically a method called isogeny-based cryptography. This approach uses a unique type of movement between curves that is easy to perform in one direction but incredibly difficult to reverse, creating a foundation for security that quantum machines cannot easily break. However, building practical systems on this foundation has been difficult because the standard methods for proving knowledge of a secret key often rely on a process that fails when facing quantum adversaries.

A team of researchers at South East Technological University in Ireland has developed a new way to construct these proofs that avoids the fatal weaknesses of previous methods. Their work focuses on a specific system known as CSIDH, which uses a mathematical structure called a class group to move between elliptic curves. The researchers discovered that when the internal structure of this group is fully known, as it is for a specific version called CSIDH-512, it can be broken down into smaller, independent pieces using a classic mathematical principle known as the Chinese Remainder Theorem. Instead of treating the secret key as a single, monolithic block, they designed a protocol that proves knowledge of each small piece separately. This structural change allows the system to extract the secret key directly from the proof using simple arithmetic, rather than relying on a complex, repetitive guessing game that quantum computers can disrupt.

The core of their achievement is a new type of interactive proof that is both perfectly complete and perfectly secure against eavesdropping. In this system, a prover and a verifier exchange messages to confirm that the prover knows a secret key without revealing the key itself. The researchers proved that if a prover can successfully answer two different challenges for the same step, the secret can be recovered instantly by subtracting the answers and performing a single division. This process, which they call algebraic extraction, happens in a straight line without the need to rewind or restart the interaction. This is a critical distinction because previous security proofs for similar systems relied on rewinding the attacker to a previous state to force a mistake, a technique that is impossible to justify against a quantum computer that cannot be paused or copied. By removing this step, the new protocol offers a path to security that holds up even in a future where quantum computers are common.

To ensure their design was not just a theoretical idea, the team implemented the entire system on a computer using the exact parameters of the CSIDH-512 group. They verified the mathematical logic of the protocol over ten thousand random instances, confirming that the algebraic steps worked exactly as predicted every time. They also ran simulations to measure how the system would behave under attack. These tests confirmed that the security of the system follows the expected mathematical laws, with the difficulty of breaking it growing predictably as the number of rounds increases. However, the researchers were also careful to identify the limits of their approach. They demonstrated that while breaking the problem into smaller pieces makes the extraction of the secret possible, it also exposes the system to a specific type of attack that reduces the difficulty of breaking the key. For the current CSIDH-512 parameters, this reduction lowers the security from a level requiring approximately 2^128.6 group action evaluations to about 2^67.3 evaluations, a significant drop that renders the current parameters insufficient for 128-bit classical security.

Consequently, the researchers conclude that while their construction is mathematically correct and structurally complete, it is not yet safe for immediate deployment on the current CSIDH-512 parameters. The system works perfectly, but the very feature that makes it efficient—the exposure of intermediate steps—also makes it vulnerable to a known attack method. The solution, they argue, lies in future parameter sets where the mathematical components are much larger. If the group is built from prime factors that are individually very large, the security loss from exposing the intermediate steps becomes negligible, and the system would remain secure. The paper also compared their method to existing schemes, noting that while their signatures are currently larger, the trade-off is a security model that does not degrade when facing quantum threats. The work stands as a rigorous demonstration that algebraic structure can replace complex, error-prone security proofs, provided the underlying numbers are chosen with enough care to withstand the new vulnerabilities the structure introduces.

Technical Summary: CRT-Decomposed Σ-Protocols for CSIDH Class Group Actions

Problem Statement
The paper addresses a critical weakness in the security proofs of isogeny-based blind signatures and identification protocols, specifically those built on the CSIDH (Commutative Supersingular Isogeny Diffie-Hellman) group action. Current state-of-the-art schemes (e.g., CSI-Otter, Tanuki) rely on interactive identification protocols whose security reductions depend on the forking lemma. This lemma requires "rewinding" a quantum adversary to extract a secret key, a process that incurs a quadratic security loss and is theoretically invalid against quantum adversaries whose internal states cannot be cloned. Consequently, these proofs force the use of larger, slower parameters to compensate for the loss. The paper seeks to eliminate this rewinding step by leveraging the algebraic structure of the CSIDH class group to enable straight-line extraction.

Methodology
The authors construct a zero-knowledge proof of knowledge (Σ-protocol) that exploits the Chinese Remainder Theorem (CRT) structure of the CSIDH ideal class group. This approach is applicable only when the group structure is exactly known, a condition currently met only by CSIDH-512.

CRT Decomposition: The class group $C\ell(\mathcal{O})$ of order $N$ is decomposed into independent cyclic components corresponding to the prime power factors of $N$ . The secret key $s$ is split into components $s_i$ modulo each prime factor $q_i$ .
Hop Curves: The protocol publishes a chain of "hop curves" ( $F_0, \dots, F_k$ ) representing the intermediate states of the group action. Each hop $i$ corresponds to a vectorization problem within a specific subgroup $\langle h_i \rangle$ of order $q_i$ .
Protocol Structure: The protocol consists of $k$ hops, each executed in $t$ parallel rounds. In each round, the prover commits to a random displacement, the verifier issues a binary challenge ( $c \in \{0,1\}$ ), and the prover responds with a value $z$ .
Algebraic Extraction: Unlike standard proofs that require rewinding to find two accepting transcripts with different challenges, this protocol allows the secret to be recovered via a closed-form algebraic formula. Given two accepting transcripts for the same commitment, the secret component is simply the difference of the responses ( $z_0 - z_1$ ), followed by modular inversion and CRT recombination.
QROM Compilation: Because each round admits exactly two responses, the protocol is compatible with Unruh's transform. This allows the conversion of the interactive protocol into a non-interactive proof of knowledge in the Quantum Random Oracle Model (QROM) with straight-line extraction, completely avoiding the forking lemma.

Key Contributions
The paper makes five primary contributions:

Formal Definition: It formalizes weak extractability for cryptographic group actions, defining a security notion where an extractor can recover the secret using only ring operations (no lattice reduction or heuristics) from accepting transcripts.
Protocol Construction ( $\Pi_{CRT}$ ): It constructs a protocol proving four properties:
- Perfect Completeness: Honest provers always succeed.
- Perfect Special HVZK: Transcripts reveal no information about the secret, even to unbounded observers.
- 2-Special Soundness: The secret is algebraically recoverable from two transcripts via simple subtraction and modular inversion.
- Knowledge Error: The probability of a prover succeeding without the key is $2^{-t}$ .
Machine Verification: The authors implemented the algebraic layer over the exact 258-bit modulus of CSIDH-512. They verified 10,000 random instances, confirming that the algebraic extraction works perfectly and that the protocol logic holds without computing actual isogenies.
Delimiting Results (Negative Results):
- Challenge Space Limit: The CRT decomposition does not enlarge the per-round challenge space; binary challenges remain necessary unless multiple curves are published, which increases key size.
- Security Cost: Publishing the intermediate hop curves reduces the classical security of key recovery from $\approx 2^{128.6}$ to $\approx 2^{67.3}$ group action evaluations. This is because the problem decomposes into independent vectorization instances in subgroups, solvable via meet-in-the-middle attacks on the largest component.
QROM Security: The paper proves that the protocol, when compiled via Unruh's transform, yields a non-interactive proof with online extraction in the QROM, removing the multiplicative forking-lemma loss.

Results and Quantitative Analysis

Instantiation: The scheme is instantiated on CSIDH-512. The class group has 5 prime factors (bit lengths: 2, 6, 21, 96, 135).
Security Bounds:
- Classical: The security is capped by the largest prime factor ( $q_{max} \approx 2^{135}$ ). The meet-in-the-middle attack cost is $O(\sqrt{q_{max}}) \approx 2^{67.3}$ . The paper notes that CSIDH-512 does not achieve 128-bit classical security under this construction due to the published hop curves.
- Quantum: Security is bounded by Kuperberg-style sieves, similar to other CSIDH schemes.
Performance:
- Signature Size: For $t=128$ rounds and $k=5$ components, the signature size is approximately 24.1 KiB (compared to 263 B for CSI-FiSh and 8 KiB for CSI-Otter).
- Computation: The algebraic extraction and simulation are sub-microsecond. The dominant cost remains the isogeny evaluation (projected at 40 ms per action), making the total signing time roughly 25.6 seconds for the full protocol.
Simulation: Monte Carlo simulations confirmed that the soundness error matches the theoretical $2^{-t}$ bound within 95% confidence intervals.

Significance and Claims
The paper claims that the construction is structurally complete and correct for known-structure class groups like CSIDH-512. Its primary significance lies in providing a quantum-safe security reduction for isogeny-based proofs of knowledge by eliminating the rewinding step, which is a known vulnerability in post-quantum security proofs.

However, the authors are explicit about the trade-offs:

Modesty on Security: The scheme is not quantitatively secure at the 128-bit level for CSIDH-512 due to the security degradation caused by publishing hop curves. The authors state that the construction is "quantitatively secure only on future parameter sets whose class number has large prime factors" (e.g., where each factor is $\ge 256$ bits).
No Magic Bullet: The CRT decomposition does not reduce the number of rounds required for soundness; it merely changes the extraction mechanism.
Future Work: The paper leaves the construction of a blind signature based on this proof of knowledge and the tight reduction of its unforgeability to the endomorphism ring problem as future work.

In summary, the paper presents a mathematically rigorous, machine-verified protocol that solves the "rewinding problem" for CSIDH-based proofs of knowledge, offering a path to QROM-secure blind signatures, but at the cost of larger signature sizes and reduced classical security for current parameter sets.

Technical Summary: CRT-Decomposed Σ-Protocols for CSIDH Class Group Actions

More like this