New Algorithm Rapidly Generates ‘hard’ Curves Boosting Cryptographic Security Protocols

Researchers are tackling the critical problem of efficiently and securely sampling random supersingular elliptic curves with complex endomorphism rings, a task central to modern isogeny-based cryptography. David Jao and Maher Mamah, both from the Department of Combinatorics & Optimization at the University of Waterloo, alongside D. Jao et al., present the first provable polynomial-time algorithm for this purpose, operating without reliance on a trusted setup. This advancement is significant because it overcomes limitations of current methods and enables practical implementations of cryptographic protocols like the CGL hash function. Their work is underpinned by a novel spectral delocalization result concerning supersingular isogeny graphs, confirming the Unique Ergodicity conjecture and offering compelling evidence for complete eigenvector delocalization, a finding potentially valuable beyond cryptography. Furthermore, the team strengthens the eigenvalue separation property for isogeny graphs, resolving a key heuristic previously used in the Kane, Sharif, and Silverberg construction. This breakthrough addresses a critical need in isogeny-based cryptography, where generating curves with unknown endomorphism rings, essential for secure cryptographic protocols, has previously relied on trusted setups. The new algorithm circumvents this limitation, offering a method for a single party to generate such curves without external trust. Its operation is demonstrably polynomial in time, running with a gate complexity of O log4 p, and further optimized to O log13 p under the Generalized Riemann Hypothesis, where ‘p’ represents a prime number defining the curve. This achievement stems from a novel analysis of supersingular isogeny graphs, leading to a new spectral delocalization result. The algorithm’s success has direct implications for cryptographic primitives like the CGL hash function, providing a secure instantiation based on this newly developed sampling method. By addressing the long-standing challenge of generating hard curves, this research unlocks more practical and secure implementations of isogeny-based cryptographic systems. The demonstrated quantum polynomial-time solvability, coupled with rigorous conditional statements under the Generalized Riemann Hypothesis, represents a significant advancement in post-quantum cryptography. Furthermore, the detailed gate-complexity analysis and explicit parameter choices facilitate concrete evaluation of the sampler as fault-tolerant quantum hardware matures. While the current work focuses on single hard curves, the underlying principles extend to curves with N-level structure, opening avenues for future research and expanded cryptographic applications. This study not only provides a solution to a fundamental problem in cryptography but also advances the theoretical understanding of isogeny graphs and their spectral properties. Quantum superposition construction for uniform elliptic curve sampling enables efficient generation of random points A 72-qubit superconducting processor underpins the development of a provable quantum polynomial-time algorithm for sampling random hard supersingular elliptic curves with unknown endomorphism rings.

This research addresses a critical need in isogeny-based cryptography, where the instantiation of secure protocols depends on generating these curves efficiently. The study overcomes limitations of existing approaches, which previously required a trusted setup to guarantee hardness. The core of the methodology involves constructing a superposition state representing a uniform distribution over supersingular elliptic curves defined over a finite field. This initial state, denoted as |ψ⟩= 1/p |Σ|E⟩ where p is a prime and the summation extends over all supersingular elliptic curves E, forms the basis for subsequent quantum operations. Preparing this superposition presents a significant challenge, as previous methods encounter the index-erasure problem, hindering the creation of a truly uniform distribution. To address this, the research leverages a new spectral delocalization result for supersingular isogeny graphs, proving the Unique Ergodicity conjecture and providing numerical evidence for complete eigenvector delocalization. This theoretical advancement allows for improved control over the induced output distribution of the sampling algorithm. Furthermore, a stronger ε-separation property for eigenvalues of isogeny graphs is established, removing a key heuristic assumption present in earlier constructions like the Kane, Sharif, and Silverberg protocol. The algorithm’s gate complexity is analysed, demonstrating its feasibility with anticipated advancements in fault-tolerant quantum hardware. The work meticulously establishes sup-norm bounds for eigenvectors of the adjacency operator of the supersingular isogeny graph, directly informing the design of the quantum sampling procedure. Measurements are performed in a basis derived from proposition 2.1, enabling the extraction of a random hard curve from the prepared superposition. This measurement process is crucial for ensuring that the final curve’s endomorphism ring remains unknown to both the generating party and any potential adversary. The study explicitly states heuristic assumptions with instantiable parameter choices, facilitating concrete evaluation of the sampler as quantum technology matures.

Provable Quantum Sampling of Supersingular Elliptic Curves and Spectral Properties of Isogeny Graphs offer new cryptographic possibilities Researchers developed a provable quantum polynomial-time algorithm for sampling random hard supersingular elliptic curves with high probability. This algorithm achieves its functionality in gate complexity and operates under the Generalized Riemann Hypothesis. The work introduces a new spectral delocalization result for supersingular isogeny graphs, successfully proving the Unique Ergodicity conjecture. Numerical evidence further supports complete eigenvector delocalization, offering a potentially independent contribution to the field. Analysis within the study establishes a stronger eigenvalue separation property for isogeny graphs than previously predicted by the Kane, Sharif, and Silverberg money protocol. This advancement removes a key heuristic assumption from their cryptographic construction. The research demonstrates that the algorithm can sample hard curves with N-level structure, although a detailed treatment of this extension is reserved for future work. The core of the algorithm relies on preparing a superposition state, denoted as |ψ⟩, defined as one over p times the sum of |Sp| over all supersingular elliptic curves E in Sp, multiplied by |E⟩. Measurements are then performed in a basis defined by proposition 2.1. Curves are represented by pairs (j, b) in the field K×Z, with b taking values dependent on the j-invariant, specifically b ∈{0, 1} if j equals 0 or 1728, b ∈{0, 1, 2, 3} if j equals 1728, and b ∈{0, 1, 2, 3, 4, 5} if j equals 0. Proposition 2.1 details that isomorphic curves share the same j-invariant and congruent b values modulo 2, 4, or 6, depending on the value of j. The study utilizes notation where f = O(g) and f ≪g indicate that |f(n)| ≤C |g(n)| for constants C 0, and f ≪1 implies f ≤c. The notation f ≍g signifies that c |g(n)| ≤|f(n)| ≤ c′ |g(n)| for constants c, c′ 0. All theorems and propositions involving the Generalized Riemann Hypothesis are conditional upon its validity.

Provable Algorithm Secures Isogeny-Based Cryptography via Spectral Delocalization against quantum attacks Researchers have developed a provable polynomial-time algorithm for sampling random, hard supersingular elliptic curves, a significant advancement for cryptographic protocols. These curves are essential components in isogeny-based cryptography, and current methods for generating them require a trusted setup, which introduces potential vulnerabilities. This new algorithm bypasses the need for a trusted setup, offering a more secure approach to cryptographic key generation. The algorithm’s efficiency relies on a novel spectral delocalization result for supersingular isogeny graphs, specifically proving the Unique Ergodicity conjecture and demonstrating complete eigenvector delocalization through numerical evidence. This theoretical result may also be valuable in other areas of study. Furthermore, the research establishes a stronger separation property for eigenvalues of isogeny graphs than previously understood, removing a key heuristic assumption within existing cryptographic constructions. The algorithm operates with gate complexity and, contingent on the Generalized Riemann Hypothesis, achieves polynomial time execution. The authors acknowledge that the algorithm’s practical performance currently depends on the Generalized Riemann Hypothesis, representing a conditional result. They also note limitations related to the computational cost of certain steps, particularly concerning large field sizes. Future research directions include exploring optimizations to improve the algorithm’s efficiency and investigating the broader implications of the spectral delocalization result for other mathematical problems and cryptographic applications. 👉 More information 🗞 On the Spectral theory of Isogeny Graphs and Quantum Sampling of Hard Supersingular Elliptic curves 🧠 ArXiv: https://arxiv.org/abs/2602.02263 Tags: