THE QUANTUM INTELLIGENCER

Quantum Polynomial-Time Sampling of Hard Supersingular Elliptic Curves via Spectral Delocalization In Plain English: Some new types of online security systems rely on special kinds of invisible number patterns called 'supersingular elliptic curves' that are extremely hard to crack—even for future quantum computers. But to make these systems secure, we need to pick these patterns randomly in a way that no one can reverse-engineer. Until now, this required a trusted third party. This paper shows how a quantum computer could generate these secure patterns on its own, quickly and safely. This matters because it could help build more trustworthy and decentralized security tools for the future internet. Summary: This paper presents the first provable quantum polynomial-time algorithm for sampling random supersingular elliptic curves with unknown endomorphism rings—so-called 'hard' curves—which are essential for the security of isogeny-based cryptographic protocols such as the Charles-Goren-Lauter (CGL) hash function. Current methods require a trusted setup, but the authors eliminate this need by leveraging quantum computation and new results in the spectral theory of ℓ-isogeny graphs. The algorithm runs in $\tilde{O}(\log^4 p)$ quantum gate complexity heuristically, and in $\tilde{O}(\log^{13} p)$ under the Generalized Riemann Hypothesis (GRH), making it efficient for practical cryptographic parameters. The theoretical foundation of the algorithm is a proof of the Quantum Unique Ergodicity (QUE) conjecture for supersingular isogeny graphs, which implies that eigenfunctions are uniformly distributed across the graph. This spectral delocalization ensures that quantum sampling mixes rapidly and produces uniformly random hard curves. The authors also present numerical evidence suggesting complete eigenvector delocalization, a stronger property that may have broader implications. Additionally, they prove an improved $\varepsilon$-separation property for eigenvalues of isogeny graphs, surpassing the heuristic assumption used in the quantum money scheme of Kane, Sharif, and Silverberg, thus placing that construction on firmer theoretical ground. These results not only enable secure, trustless instantiation of isogeny-based cryptography but also advance the mathematical understanding of isogeny graphs. The work demonstrates that quantum algorithms can solve foundational problems in computational number theory with cryptographic relevance, potentially reshaping assumptions about hardness in post-quantum security. Key Points: - The paper introduces the first provable quantum polynomial-time algorithm for sampling hard supersingular elliptic curves without trusted setup. - The algorithm runs in $\tilde{O}(\log^4 p)$ heuristically and $\tilde{O}(\log^{13} p)$ under GRH. - It enables secure, trustless instantiation of isogeny-based cryptographic primitives like the CGL hash function. - The authors prove the Quantum Unique Ergodicity (QUE) conjecture for supersingular $\ell$-isogeny graphs. - Numerical evidence supports complete eigenvector delocalization in these graphs. - A stronger $\varepsilon$-separation of eigenvalues is proven, removing a key heuristic in prior quantum money schemes. - Results bridge quantum computing, spectral graph theory, and post-quantum cryptography. - The work challenges assumptions about the hardness of isogeny problems in the presence of quantum adversaries. Notable Quotes: - "We present the first provable quantum polynomial-time algorithm that samples a random hard supersingular elliptic curve with high probability." - "Our analysis relies on a new spectral delocalization result for supersingular $\ell$-isogeny graphs: we prove the Quantum Unique Ergodicity conjecture..." - "...we further provide numerical evidence for complete eigenvector delocalization - this theoretical result may be of independent interest." - "Along the way, we prove a stronger $\varepsilon$-separation property for eigenvalues of isogeny graphs than that predicted in the quantum money protocol of Kane, Sharif, and Silverberg, thereby removing a key heuristic assumption in their construction." Data Points: - Quantum gate complexity: $\tilde{O}(\log^4 p)$ heuristically. - Quantum gate complexity: $\tilde{O}(\log^{13} p)$ under the Generalized Riemann Hypothesis (GRH). - The algorithm samples supersingular elliptic curves over $\mathbb{F}_{p^2}$ for large prime $p$. - The spectral gap and eigenvalue separation are improved beyond prior heuristic estimates used in quantum money protocols. - Numerical experiments support eigenvector delocalization across graphs of varying sizes and characteristics. Controversial Claims: - The claim that a quantum algorithm can efficiently sample hard supersingular curves may challenge the foundational hardness assumptions underlying isogeny-based cryptography, suggesting potential vulnerabilities in post-quantum schemes that rely on such assumptions. - The assertion that complete eigenvector delocalization occurs in supersingular isogeny graphs, while supported by numerical evidence, remains conjectural and could be debated without a full proof. - The heuristic gate complexity of $\tilde{O}(\log^4 p)$ depends on unproven assumptions about the spectral properties of isogeny graphs, which may be contested in the absence of unconditional proofs. Technical Terms: - Supersingular elliptic curve, isogeny graph, endomorphism ring, quantum polynomial-time algorithm, spectral delocalization, Quantum Unique Ergodicity (QUE), eigenvector delocalization, $\varepsilon$-separation, Generalized Riemann Hypothesis (GRH), Charles-Goren-Lauter (CGL) hash function, post-quantum cryptography, isogeny-based cryptography, quantum gate complexity, eigenvalue distribution, spectral graph theory —Ada H. Pemberley Dispatch from The Prepared E0