Source-linked AI summary
Quantum resource estimates for computing elliptic curve discrete logarithms
Martin Roetteler, Michael Naehrig, Krysta M. Svore, Kristin Lauter
TL;DR
The paper addresses the concrete quantum resources needed to solve elliptic-curve discrete logarithms, where implementation constants matter despite polynomial asymptotic runtime. It uses LIQUi|⟩-based reversible-circuit simulation to estimate Shor’s algorithm and finds ECC attacks require fewer resources than RSA factoring at comparable classical security levels.
Problem
Concrete quantum resource requirements for solving the elliptic-curve discrete logarithm problem remain important because implementation constants affect practical feasibility despite polynomial asymptotic runtime.
Method
The authors implement and classically simulate reversible modular arithmetic and controlled elliptic-curve point-addition circuits within the LIQUi|⟩ software architecture.
Results
At comparable classical security, elliptic-curve discrete logarithms require fewer quantum resources than RSA factoring; for P-256, the estimate is 2330 logical qubits and about 1.26 · 10^11 Toffoli gates.
Takeaways & Limitations
The estimates provide concrete data for assessing the quantum security horizon of elliptic-curve cryptography and offer reversible arithmetic and group-law circuits as potential building blocks for other quantum algorithms.
Takeaways & Limitations
The approach’s fidelity could be improved with complete addition formulas, but not all elliptic curves admit a twisted Edwards model supporting more efficient complete formulas.
Abstract
from arXiv · showhide
We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.
1 Introduction
The paper develops precise, gate-level quantum resource estimates for solving the elliptic curve discrete logarithm problem with Shor’s algorithm. It combines reversible arithmetic circuits, elliptic curve point addition, and classical simulation to compare ECC attacks with RSA factoring.
- Motivation: Elliptic curve cryptography is widely deployed, and its security relies on the hardness of the elliptic curve discrete logarithm problem.Elliptic curves support public-key mechanisms including key exchange and digital signatures, with relatively small parameters at comparable classical security levels.
- Approach: LIQUi|⟩ provides the programming, compilation, and simulation framework, while reversible circuits are implemented primarily as Toffoli, CNOT, and NOT networks.The authors exploit efficient classical simulation of reversible circuits on classical input states, allowing simulations beyond the tool’s roughly 32-qubit general simulation limit.
- Approach: The paper builds on earlier theoretical estimates by fully programming and simulating the underlying arithmetic, measuring logical qubits, Toffoli gates, and circuit depth.The implementation targets Shor’s algorithm for ECDLP and enables gate-level comparison with resource estimates for Shor’s factoring algorithm.
- Contributions: The reversible arithmetic toolkit includes modular addition, subtraction, negation, doubling, multiplication, squaring, inversion, and affine elliptic curve point addition.Montgomery multiplication is compared with double-and-add multiplication, and the inversion circuit uses a reversible binary extended Euclidean algorithm.
- Results: 9n + 2⌈log2(n)⌉ + 10 qubits and about 448n^3 log2(n) + 4090n^3 Toffoli gates suffice for Shor’s ECDLP circuit over an n-bit prime field.For P-256, the point-addition circuit uses 2330 logical qubits and the full algorithm requires about 1.26 · 10^11 Toffoli gates.
- Results: For comparable classical security, the estimates indicate that attacking ECC requires fewer resources than factoring RSA, while providing concrete data for assessing future quantum-security timelines.The authors also present their reversible arithmetic and elliptic curve circuits as potential building blocks for other quantum algorithms.
2 Elliptic curves and Shor’s algorithm
The section introduces elliptic curves and the ECDLP, then describes Shor’s quantum procedure for recovering a discrete logarithm through controlled point operations and Fourier sampling.
- Elliptic curves: Elliptic curves over F_p are represented by the affine equation y^2 = x^3 + ax + b together with a point at infinity, forming an abelian group.The group operation is defined through rational functions in point coordinates, with the point at infinity as the neutral element.
- Elliptic-curve group law: For P_1 + P_2, the group law handles the point at infinity and inverse cases separately before computing affine coordinates using the slope λ.The slope uses a difference quotient when P_1 ≠ P_2 and a tangent expression when P_1 = P_2.
- The ECDLP: Scalar multiplication [m]P is repeated group addition and is central to discrete-logarithm protocols and Shor’s ECDLP algorithm.The order ord(P) is the smallest positive integer r satisfying [r]P = Ø.
- The ECDLP: The ECDLP asks for the unique m such that Q = [m]P in a cyclic subgroup generated by a known point P of order r.The cryptographic setting uses a large prime field and a cyclic subgroup of large prime order.
- Shor’s algorithm: Shor’s algorithm prepares two superposed registers, conditionally adds multiples of P and Q, discards the point register, and applies QFTs before classical post-processing.The controlled additions implement the double scalar multiplication at the circuit’s core.
- Shor’s algorithm: A semiclassical Fourier-transform variant uses only one additional qubit beyond those needed to represent and add elliptic-curve points.Its phase shifts depend on previous measurement outcomes, unlike the circuit in Figure 1.
3 Reversible modular arithmetic
The paper develops reversible modular arithmetic circuits needed for elliptic-curve point addition, including addition, doubling, multiplication, Montgomery multiplication, and inversion. These constructions emphasize reversible operation, ancilla management, and circuit-depth trade-offs.
- Motivation: Full modular arithmetic is required because elliptic-curve point additions operate on quantum-register coordinates using additions and multiplications modulo p.The arithmetic supports scalar multiplications in the elliptic-curve discrete-logarithm algorithm.
- Circuit primitives: The reversible arithmetic toolkit includes integer addition, subtraction, constant addition, controlled variants, modular addition, doubling, multiplication, squaring, and inversion.The circuits operate on n-bit integers held in quantum registers and preserve reversibility through uncomputation and returned ancillas.
- Modular addition and doubling: Modular addition maps |x⟩|y⟩ to |x⟩|(x + y) mod p⟩ using integer addition, constant-modulus addition and subtraction, comparison, and auxiliary qubits.Its controlled form is obtained by controlling all operations in the modular-addition circuit.
- Modular addition and doubling: For odd p, modular doubling maps |x⟩ to |2x mod p⟩ in place using a cyclic shift and modular reduction, requiring n + 2 qubits.The reduction ancilla is uncomputed by checking the least significant bit of the result.
- Multiplication and squaring: Modular multiplication uses binary decomposition of one multiplicand, combining modular doublings with controlled modular additions in a 3n + 2-qubit circuit.Modular squaring removes the second multiplicand register and instead uses an additional ancilla to conditionally add x.
- Montgomery multiplication: Montgomery multiplication uses one integer addition per round instead of at least two for each modular reduction, reducing depth but requiring extra qubits and a reverse pass for uncomputation.The algorithm stores whether p was added in each round so division by 2 can be implemented by a cyclic shift.
- Modular inversion: The reversible extended binary GCD implementation uses a fixed 2n-step schedule and a counter register so its operations are independent of the input.A four-branch reversible round handles parity tests and conditional subtraction based on the comparison of the two working values.
4 Reversible elliptic curve operations
The paper builds reversible controlled elliptic-curve point addition from modular arithmetic and analyzes exceptional cases under the generic affine group law. It also discusses resource-relevant trade-offs and alternatives, including projective coordinates and complete addition formulas.
- Controlled point addition: The reversible point-addition algorithm replaces P1 with P3 = P1 + P2 when controlled, using a classically precomputed constant point P2.It operates on affine coordinates and assumes nonzero inputs with P1 ≠ ±P2.
- Controlled point addition: The algorithm composes controlled and uncontrolled modular additions, subtractions, negation, multiplication, squaring, and inversion on point coordinates and auxiliary registers.The modular multiplication, squaring, and inversion operations are out of place and use separate output registers.
- Circuit registers: The circuit uses n-qubit coordinate and auxiliary-value registers, one control qubit, and a 5n-qubit temporary register determined by modular inversion.The registers |x1⟩, |y1⟩, |t0⟩, and |λ⟩ each contain n logical qubits; temporary qubits are returned to their original state.
- Resource bottleneck: Four inversion calls make modular inversion the main cost of affine point addition because the slope λ must be computed and uncomputed.The in-place algorithm relies on recomputing λ from the output point P3 via P3 + (−P2), independently of P1.
- Exceptional cases: The generic-group-law analysis bounds the overall fraction of invalid scalars from exceptional additions by approximately n/2^n.For a fixed random offset, the validity probability for a scalar pair is approximately 1 − n/2^(n−1), consistent with the stated fidelity-loss estimate.
- Alternative coordinate systems: Complete addition formulas could avoid exceptional cases, but projective-coordinate implementations introduce equivalence-class representations and more temporary values to uncompute.The paper leaves complete group laws and alternative coordinate systems as open problems, and notes that twisted Edwards forms do not support all curves such as prime-order NIST curves.
5 Cost and resource estimates for Shor’s algorithm
The authors simulate reversible modular arithmetic and controlled elliptic-curve point addition to estimate qubit, Toffoli-count, and depth requirements for Shor’s ECDLP algorithm. Their estimates include 9n + 2⌈log2(n)⌉ + 10 logical qubits and (448 log2(n) + 4090)n^3 Toffoli gates, with comparisons to RSA factoring.
- Simulation framework: LIQUi|⟩ simulations provide qubit counts, Toffoli-gate counts, and Toffoli-depth measurements for reversible elliptic-curve point addition and its components.The implementation covers modular addition, multiplication, inversion, and elliptic-curve point addition over n-bit prime fields.
- Reversible arithmetic: Montgomery multiplication is used because it substantially reduces Toffoli gates without increasing qubit registers beyond those supplied by modular inversion.Although modular doubling and additions use fewer qubits, inversion determines the overall qubit lower bound.
- Qubit resources: 9n + 2⌈log2(n)⌉ + 10 logical qubits are required for controlled elliptic-curve point addition.The count includes the inversion workspace, one control qubit, and two additional n-qubit registers for intermediate inversion results.
- Gate-count scaling: 224n^2 log2(n) + 2045n^2 Toffoli gates describe the estimated scaling of a single elliptic-curve point addition.The leading coefficient combines four inverters, two squarers, and four multipliers.
- Gate-count scaling: (448 log2(n) + 4090)n^3 Toffoli gates estimate the full Shor ECDLP circuit.The estimate is obtained from the point-addition cost and the overall algorithmic repetition factor.
- Depth and comparison: Toffoli depth is slightly smaller than total Toffoli count, indicating exploitable parallelism, while RSA factoring has a distinct scaling estimate of (64(log2(n) − 2) + 29.46)n^3.The RSA comparison uses modular constant multiplication and aligns practical ECC and RSA parameters by classical security level.
6 Discussion
The discussion compares the simulation-based estimates with prior theoretical analyses and identifies reversible modular inversion as the main source of extra qubits. The authors conclude that ECC appears easier to attack than RSA at comparable classical security levels, while leaving lower-qubit inversion as future work.
- Comparison with prior estimates: The estimates provide additional evidence that ECDLP is easier to compute quantumly than factoring an RSA modulus at comparable classical security levels.The paper also reports that its Toffoli counts exceed theoretical time estimates and its qubit counts exceed Proos and Zalka’s conjectures.
- Modular inversion: The larger qubit count relative to Proos and Zalka’s estimate arises from the chosen extended binary GCD implementation for modular inversion.This algorithm uses additions, subtractions, and binary shifts rather than divisions with remainder.
- Modular inversion: Register sharing could reduce inversion space, but changing variable boundaries complicates its reversible implementation and simulation.The authors leave a reversible modular inversion circuit using register sharing for future work.
- Modular inversion: The implementation requires about 2n more qubits than the compared Euclidean approach because binary GCD produces garbage and needs an additional n-qubit cleanup register.The authors could not determine how to avoid these costs while achieving step-wise reversibility.
- Overall conclusion: The study presents and classically tests Toffoli-dominated circuits for Shor’s ECDLP algorithm, supporting the conclusion that ECC is easier to attack than RSA even for relatively small keys.The tested circuits implement controlled addition of a point known at circuit-generation time.