Brace for impact: ECDLP challenges for quantum cryptanalysis
quant-ph
Submitted: 2025-08-19
Updated: 2026-10-29
Comments: 40 pages, 6 figures
Code: https://github.com/JeanLucPons/Kangaroo
License: http://creativecommons.org/licenses/by/4.0/
The gist: Precise suites of benchmarks are required to assess the progress of early fault-tolerant quantum computers at economically impactful applications such as cryptanalysis.
Terminology
Abstract
Precise suites of benchmarks are required to assess the progress of early fault-tolerant quantum computers at economically impactful applications such as cryptanalysis. Appropriate challenges exist for factoring but those for elliptic curve cryptography are either too sparse or inadequate for standard applications of Shor's algorithm. We introduce a difficulty-graded suite of elliptic curve discrete logarithm (ECDLP) challenges that use Bitcoin's curve y 2=x 3+7 mod p while incrementally lowering the prime field from 256 down to 6 bits. For each bit-length, we provide the prime, the prime group order, and two deterministic nothing-up-my-sleeve (NUMS) points in compressed SEC1 form. All challenges are generated by a deterministic, reproducible procedure, and no private challenge scalar is chosen in advance. We calibrate classical cost against Pollard's rho records and quantum cost against resource estimation results for Shor's algorithm. We compile Shor's ECDLP circuit to logical counts and map them to physical resources for various parameters of the surface code, the repetition cat code and the LDPC cat codes. Under explicit and testable assumptions on physical error rates, code distances, and non-Clifford supply, our scenarios place the full 256-bit instance within a 2027--2033 window. The challenge ladder thus offers a transparent ruler to track fault-tolerant progress on a cryptanalytic target of immediate relevance, and it motivates proactive migration of digital assets to post-quantum signatures.
Sources
- Beyond NISQ: The Megaquop Machine
- Quantum attacks on Bitcoin, and how to protect against them
- A Threshold for Quantum Advantage in Derivative Pricing
- Towards Quantum Advantage in Financial Market Risk using Quantum Gradient Algorithms
- Derivative Pricing using Quantum Signal Processing
- Analyzing Prospects for Quantum Advantage in Topological Data Analysis
- Reliably assessing the electronic structure of cytochrome P450 on today's classical computers and tomorrow's quantum computers
- Assessing requirements to scale to practical quantum advantage
- Applications and resource estimates for open system simulation on a quantum computer
- Quantifying fault tolerant simulation of strongly correlated systems using the Fermi-Hubbard model
- Prospects for NMR Spectral Prediction on Fault-Tolerant Quantum Computers
- QREChem: Quantum Resource Estimation Software for Chemistry Applications
- Faster quantum chemistry simulations on a quantum computer with improved tensor factorization and active volume compilation
- Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization
- Fast quantum simulation of electronic structure by spectrum amplification
- Improved quantum circuits for elliptic curve discrete logarithms
- How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Shor's discrete logarithm quantum algorithm for elliptic curves
- Quantum resource estimates for computing elliptic curve discrete logarithms
Related papers
- Computational regimes in matrix-product-state-based quantum trajectory simulations
- Toward chemically accurate quantum simulations on quantum hardware: A quantum-HPC hybrid approach
- Transversal surface-code game with reconfigurable qubits
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements