Brace for impact: ECDLP challenges for quantum cryptanalysis

1. Problem Statement

The paper addresses the lack of precise, standardized benchmarks to track the progress of early fault-tolerant quantum computers (FTQC) toward economically impactful applications, specifically the cryptanalysis of Elliptic Curve Cryptography (ECC).

• The Gap: While factoring challenges (e.g., RSA) exist, existing Elliptic Curve Discrete Logarithm Problem (ECDLP) benchmarks are either too sparse (e.g., Certicom challenges) or inadequate for standard Shor's algorithm applications (e.g., "Bitcoin puzzles" that restrict the key to an interval, solvable by Pollard's Kangaroo rather than Shor's period finding).
• The Risk: Bitcoin and many other financial systems rely on the secp256k1 curve. If sufficiently large FTQCs are built, Shor's algorithm could derive private keys from public keys exposed on the blockchain, threatening the security of digital assets.
• The Need: A "transparent ruler" is required to measure the gap between current hardware capabilities and the threshold needed to break 256-bit ECC, allowing for proactive migration to post-quantum signatures.

2. Methodology

The authors propose a difficulty-graded suite of ECDLP challenges and a comprehensive resource estimation framework.

A. The Challenge Suite (secpkk1)

• Curve Structure: The challenges retain the exact curve equation of Bitcoin's secp256k1: $y^2 = x^3 + 7 \pmod p$.
• Variable Field: Instead of changing the curve parameters, the authors systematically shrink the prime field $p$ from 256 bits down to 6 bits.
• Deterministic Construction:
  • For each bit-length $k$, a prime $p$ is selected such that the curve order $n$ is prime.
  • Two points, $P_p$ and $Q_p$, are generated deterministically using the labels "Quantum" and "Challenge" via SHA-256 hashing and a "nothing-up-my-sleeve" (NUMS) procedure to find valid curve points.
  • This eliminates hidden private keys; the challenge is to find $\kappa$ such that $P_p = [\kappa]Q_p$.
• Scope: The suite covers bit-lengths $k \in \{6, \dots, 256\}$, providing a fine-grained ladder for testing.

B. Classical Calibration

• The authors benchmark the difficulty of these challenges against the best-known classical attacks using Pollard's rho algorithm.
• They analyze historical records (e.g., solving 112-bit curves on PlayStation 3s, 129-bit interval attacks on GPUs) to establish that classical complexity scales as $\Theta(2^{b/2})$.
• This establishes that generic 256-bit ECDLP is currently intractable for classical computers, while smaller instances (e.g., 6-bit) serve as milestones for FTQC demonstrations.

C. Quantum Resource Estimation

The paper translates Shor's algorithm for ECDLP into physical resource requirements using three distinct error-correction architectures:

1. Surface Code (2D): The standard baseline using lattice surgery.
2. Repetition Cat Code: A bosonic architecture (Alice & Bob) leveraging biased noise to reduce overhead.
3. LDPC Cat Code: A newer architecture combining cat qubits with Low-Density Parity-Check codes for higher encoding rates.

The estimation process involves:

• Logical Level: Compiling Shor's ECDLP circuit (based on HJNRS reversible arithmetic) to count logical qubits ($N_{log}$) and Toffoli gates ($T_{count}$).
• Physical Level: Mapping logical counts to physical qubits ($N_{phys}$) and runtime ($t$) based on specific hardware assumptions (physical error rates, cycle times, magic-state factory throughput).

3. Key Contributions

1. Deterministic Challenge Ladder: A reproducible set of ECDLP instances from 6 to 256 bits using the secp256k1 curve shape, providing a standardized "ruler" for the community.
2. Calibrated Baselines: A clear separation between generic ECDLP (Shor's algorithm) and interval-restricted puzzles, anchoring claims to published classical records.
3. Multi-Architecture Costing: A unified comparison of Shor's ECDLP costs across Surface, Repetition Cat, and LDPC Cat codes, highlighting the trade-offs between qubit count and runtime.
4. Sensitivity Analysis: Identification of the critical "levers" (magic-state supply, code distance, physical error rates) that determine when a 256-bit break becomes feasible.
5. Migration Roadmap: Concrete proposals for Bitcoin migration (e.g., BIP 360, commit-then-upgrade strategies) based on the projected timeline of quantum threats.

4. Key Results

• Resource Scaling: The paper provides detailed tables (Appendix B) showing the exponential growth in resources required as bit-length increases.
  • 6-bit instance: Solvable with a few hundred logical qubits and seconds of runtime on current FTQC projections. This is the target for the first end-to-end FTQC demonstration.
  • 256-bit instance (secp256k1):
    • Surface Code (Conservative): Requires ~4.8 million physical qubits and ~670 hours (28 days).
    • Surface Code (Aggressive): Requires ~0.8 million physical qubits and ~22 hours.
    • Repetition Cat Code: Requires ~126,000 cat qubits and ~9 hours.
    • LDPC Cat Code: Requires ~38,000 cat qubits and ~17 hours (under aggressive assumptions).
• Timeline Projection: Overlaying these resource requirements with current hardware roadmaps (IBM, Google, Quantinuum, Alice & Bob), the authors estimate a first plausible window for cryptanalytically relevant quantum computers (CRQCs) between 2027 and 2033.
  • This window depends heavily on the scaling of non-Clifford resource supply (magic states) and the reduction of physical error rates.
• Classical vs. Quantum: The classical "wall" at ~120 bits is confirmed; moving from 120 to 256 bits requires an exponential increase in classical effort ($2^{64}$ more operations), whereas quantum effort scales polynomially with the bit-length.

5. Significance and Implications

• Early Warning System: The challenge ladder acts as a "canary in the coal mine." Solving the 6-bit or 160-bit instances with active error correction would signal that the technology is rapidly approaching the 256-bit threshold.
• Policy and Migration: The paper argues that waiting for a confirmed 256-bit break is too late. The "commit-then-upgrade" strategy is recommended:
  • Users should move funds to scripts that commit to a post-quantum public key (via a hash) while keeping the classical spend path open.
  • This allows for a soft-fork migration to post-quantum signatures (e.g., BIP 360) before the quantum threat materializes, avoiding a hard fork or network downtime.
• Community Alignment: By providing a common, transparent metric, the paper enables algorithm designers, hardware engineers, and cryptographers to speak the same language regarding progress, moving beyond theoretical asymptotics to concrete engineering milestones.

In conclusion, the paper provides a rigorous, data-driven framework to monitor the "countdown" to quantum vulnerability for ECC, urging the cryptocurrency community to begin migration preparations immediately based on the projected 2027–2033 threat window.