Source-linked AI summary
Constructing elliptic curve isogenies in quantum subexponential time
Andrew M. Childs, David Jao, Vladimir Soukharev
TL;DR
Constructing an isogeny between ordinary elliptic curves with the same cardinality and endomorphism ring was known to require exponential classical time, with no prior nontrivial quantum algorithm. The paper reduces the task to an abelian hidden shift problem and supplies subexponential isogeny evaluation under GRH, yielding a subexponential-time quantum algorithm and challenging the viability of isogeny-based cryptosystems.
Problem
Constructing isogenies between given horizontally isogenous elliptic curves was believed computationally difficult, with the fastest known classical algorithm exponential and no prior nontrivial quantum algorithm.
Method
The paper reduces isogeny construction to an injective abelian hidden shift problem and develops subexponential evaluation of the isogeny star operator under GRH.
Results
The paper obtains a subexponential-time quantum algorithm for constructing isogenies, with runtime bounded by Lq(1/2) under GRH.
Takeaways & Limitations
The result raises serious questions about the viability of isogeny-based cryptosystems in the context of quantum computers.
Takeaways & Limitations
The algorithm assumes GRH and, in its input formulation, assumes the discriminant of the endomorphism order is given.
Abstract
from arXiv · showhide
Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny between them, but finding such an isogeny is believed to be computationally difficult. The fastest known classical algorithm takes exponential time, and prior to our work no faster quantum algorithm was known. Recently, public-key cryptosystems based on the presumed hardness of this problem have been proposed as candidates for post-quantum cryptography. In this paper, we give a subexponential-time quantum algorithm for constructing isogenies, assuming the Generalized Riemann Hypothesis (but with no other assumptions). Our algorithm is based on a reduction to a hidden shift problem, together with a new subexponential-time algorithm for evaluating isogenies from kernel ideals (under only GRH), and represents the first nontrivial application of Kuperberg's quantum algorithm for the hidden shift problem. This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream quantum-resistant cryptosystems such as lattice-based cryptosystems.
1 Introduction
The paper presents the first subexponential-time quantum algorithm for constructing isogenies between horizontally isogenous elliptic curves, assuming only GRH. It combines a hidden-shift reduction with subexponential isogeny evaluation, while addressing space requirements and cryptographic implications.
- Motivation: The isogeny-construction problem has an exponential-time fastest known classical algorithm and previously lacked a nontrivial quantum algorithm.Its presumed difficulty underlies proposed isogeny-based public-key cryptosystems.
- Main result: The paper gives a subexponential-time quantum algorithm for constructing isogenies, with runtime bounded by Lq(1/2) under GRH alone.The result applies to two given horizontally isogenous elliptic curves.
- Implications: The result raises serious questions about isogeny-based cryptosystems, which already perform poorly compared with lattice-based quantum-resistant cryptosystems.The paper nevertheless presents isogenies as a distinct cryptosystem family worth analyzing.
- Contributions: The main reduction transforms isogeny construction into an injective abelian hidden shift problem, enabling use of Kuperberg’s algorithm.The paper identifies this as Kuperberg’s first nontrivial application outside the black-box setting.
- Contributions: A second contribution evaluates the isogeny star operator in subexponential time, making the hidden-shift hiding functions computable under only GRH.The runtime analysis avoids the additional heuristic assumptions used by earlier subexponential algorithms and relies on Cayley-graph expansion.
- Space requirements: The straightforward Kuperberg-based algorithm uses superpolynomial space, but a Regev-based variant gives polynomial-space quantum isogeny construction in time Lq(1/2).The extension to arbitrary finite abelian groups is needed because the relevant class group is not always cyclic.
2 Isogenies
This section defines horizontal isogenies and models curves with a fixed endomorphism ring as a class-group action. Under GRH, expansion of an associated Cayley graph supports near-uniform sampling by short products of small prime ideals.
- Definitions: An isogeny is an algebraic morphism between elliptic curves that maps the point at infinity to itself, and its degree is its degree as an algebraic map.The endomorphism ring consists of isogenies from a curve to itself and forms a ring under addition and composition.
- Ordinary curves: Over finite fields, ordinary elliptic curves have endomorphism rings that are imaginary quadratic orders, while supersingular curves have endomorphism-ring rank four.The paper restricts attention to ordinary curves, which dominate current isogeny-based cryptographic proposals.
- Horizontal isogenies: A horizontal isogeny joins curves with the same endomorphism ring, and a separable horizontal isogeny is specified up to isomorphism by its source curve and kernel.Ideal classes equivalent in the class group induce the same isogeny up to isomorphism.
- Class-group action: The isogeny star operator is a free and transitive action of the ideal class group on isomorphism classes of curves with fixed endomorphism ring.Thus these curve classes form a principal homogeneous space over the class group.
- Isogeny graphs under GRH: Under GRH, random walks in a Cayley graph generated by small prime ideals become sufficiently dispersed to support the paper’s runtime analysis.The graph uses the class group and a multiset of prime ideal classes and inverses.
- Isogeny graphs under GRH: The theorem remains valid after redefining the generating set, with the proof absorbing the excluded primes into the error term.This extension is formalized through the stated corollary and its parameter conditions.
3 The group action inverse problem
The group action inverse problem asks for the ideal class mapping one elliptic-curve j-invariant to another. Its presumed infeasibility underpins the security of isogeny-based cryptosystems, while the paper develops a quantum subexponential algorithm for evaluating such quotients.
- The task is to find an ideal class [b] such that [b] ∗ j(E) = j(E′), given the two j-invariants.
- The computational infeasibility of finding these quotients is a necessary security condition for isogeny-based cryptosystems.
- The paper presents a subexponential quantum algorithm for evaluating quotients in Ellq,n(O∆).
- Cryptosystem operations can use random smooth ideals, but the paper’s attack requires evaluating the isogeny star operator on arbitrary inputs.
4 Computing the isogeny star operator
The paper constructs a subexponential algorithm for evaluating the isogeny star operator by finding short factor-base relations and converting them into isogeny sequences. Under GRH, the resulting algorithm succeeds with high probability and has subexponential running time, while the quantum implementation can avoid superpolynomial space.
- Computing a relation: The relation algorithm finds a factor-base representation [b] = F^z with |z|1 bounded by O(ln |∆|).The bounded L1 norm keeps the resulting isogeny sequence manageable.
- Computing the isogeny star operator: The classical algorithm takes an ideal class [b] and j(E), then outputs j(E′) satisfying [b] ∗ j(E) = j(E′).
- Computing the isogeny star operator: The main evaluation algorithm computes a relation, constructs isogenies whose composed kernel corresponds to the factor-base powers, and returns the resulting j-invariant.
- Quantum implementation: The quantum implementation can avoid superpolynomial space because quantum factoring permits direct smoothness testing without storing the set S.
- Runtime analysis: Under GRH, Algorithm 2 succeeds with probability at least 1 − 1/e.
- Runtime analysis: Under GRH, Algorithm 2 has worst-case running time at most Lq(1/2).
5 A quantum algorithm for constructing isogenies
The paper reduces isogeny construction to an injective abelian hidden shift problem and combines quantum hidden-shift algorithms with subexponential evaluation of the group action. Under GRH, this yields subexponential isogeny construction, with a polynomial-space variant available at a slower rate.
- Reduction to hidden shift: The reduction encodes horizontally isogenous curves as hiding functions on Cl(O∆), with the unknown shift representing the ideal class mapping one curve to the other.The functions are f_c([b]) = [b] ∗ j(E_c), and injectivity follows from the free and transitive group action.
- Reduction to hidden shift: Injectivity is crucial because it enables Kuperberg-style hidden-shift algorithms, whereas non-injective functions can require exponentially many queries.The paper identifies this injective reduction as its first nontrivial application of Kuperberg’s algorithm outside the black-box setting.
- Evaluation and assumptions: The group action can be evaluated in subexponential time using the paper’s classical algorithm for the isogeny star operator, making the reduction algorithmically effective.Prior work lacked a known subexponential evaluation algorithm under only GRH, while this work supplies one.
- Evaluation and assumptions: Assuming GRH and a known discriminant, Algorithm 3 decomposes Cl(O∆), solves the hidden shift, and outputs the ideal class defining the isogeny.The discriminant assumption is aligned with existing isogeny-based cryptosystem proposals.
- Complexity and space: The resulting running time is subexponential under GRH, with faster Kuperberg and slower polynomial-space Regev variants.The Kuperberg approach requires superpolynomial space, while Regev’s generalization uses polynomial space.
- Complexity and space: Improving only hidden-shift solving or isogeny-star evaluation would not suffice to make the overall algorithm polynomial-time.The runtime is jointly constrained by both subroutines.
A Subexponential-time and polynomial-space quantum algorithm for the general abelian hidden shift problem
The appendix generalizes Kuperberg- and Regev-style sieving to arbitrary finite abelian hidden shifts. Its sieve combines labeled quantum states through progressively smaller label sets, achieving subexponential time with polynomial space.
- Generalization: The appendix extends Regev’s polynomial-space hidden-shift approach from cyclic groups to arbitrary finite abelian groups.This generalization is needed because the group relevant to isogeny construction is not always cyclic.
- State preparation and sieving: Fourier sampling produces states with random labels, and the sieve combines them to create states whose labels become progressively smaller.The target states include |ψ_2^j⟩, which support recovery of the hidden shift.
- State preparation and sieving: Given states |ψ_1⟩, |ψ_2⟩, |ψ_4⟩, …, |ψ_2^(k−1)⟩ with 2^k = Ω(N), the hidden shift can be reconstructed in polynomial time with probability Ω(1).The sieve supplies these structured states from initially sampled states.
- State preparation and sieving: The combination procedure maps k known labels below B into one known label below B′, succeeding with probability Ω(1) under a bounded ratio between B and B′.Its running time is 2^k poly(log N).
- Complexity analysis: The generalized sieve succeeds with probability 1−o(1), using k(1+o(1))^m state preparations and combination operations and space O(mk).The space bound follows because the algorithm stores only O(mk) states at a time.
- Odd-order cyclic groups: For odd cyclic groups, division by 2 is an automorphism, allowing the sieve to prepare the required powers and solve the hidden shift in L_N(1/2) time.This result complements the arbitrary-group polynomial-space construction.