ECDLP challenges for Quantum Cryptanalysis

The security of modern digital communication relies heavily on encryption, and assessing the ability of future quantum computers to break these codes is now a critical task, particularly for elliptic curve cryptography. Pierre-Luc Dallaire-Demers, William Doyle, and Timothy Foo, all from the Pauli Group, introduce a new set of challenges designed to rigorously test the progress of emerging quantum computers in solving the elliptic curve discrete logarithm problem (ECDLP). This research addresses a significant gap in benchmark availability, providing a carefully graded ladder of problems based on the same curve used in Bitcoin, but with progressively smaller problem sizes. By calibrating the difficulty for both classical and quantum computers, and mapping the computational requirements to realistic quantum hardware parameters, the team demonstrates that a full 256-bit instance of the ECDLP could be within reach of a fault-tolerant quantum computer between 2027 and 2033, motivating a timely transition to quantum-resistant cryptographic methods.

Researchers present a comprehensive suite of elliptic curve discrete logarithm problem (ECDLP) challenges, utilising Bitcoin’s curve. These challenges systematically reduce the prime field size from 256 bits down to 6 bits, providing a graded difficulty scale for testing cryptographic algorithms. For each bit-length, the team supplies the prime number, the base point, and a corresponding example public key, ensuring a standardised testing environment. All challenges originate from a deterministic and reproducible procedure, allowing for consistent and verifiable results. The work calibrates the cost of classical attacks against established records and estimates the quantum cost using resource estimations for Shor’s algorithm. Researchers compile Shor’s ECDLP circuit to logical qubit counts and subsequently map these requirements to physical resources, considering various parameters of the surface code, the repetition cat code, and the LDPC cat codes.

Shor’s Algorithm Resource Scaling with Parameters

This research explores how the computational demands of Shor’s algorithm change with different configurations. The team investigated how varying parameters such as logical qubit count, code distance, and the number of factories affect the number of physical qubits and the overall computation time. The analysis reveals a trade-off between resource usage and execution time, with lower qubit counts generally requiring longer computation times and vice versa. Different scenarios were explored, including variations in the surface code, a method for protecting quantum information from errors. These scenarios allow for a detailed comparison of optimization strategies and their impact on performance.

Tracking Quantum Progress Against Bitcoin Encryption

Researchers have developed a series of increasingly complex mathematical challenges designed to track the progress of quantum computers towards breaking modern encryption. These challenges center around the elliptic curve discrete logarithm problem (ECDLP), a core component of the cryptographic system used to secure Bitcoin and other cryptocurrencies. The team constructed a “ladder” of problems, starting with a simplified 6-bit version and scaling up to the full 256-bit size used in Bitcoin’s secp256k1 curve. This allows for precise measurement of improvements in both classical and quantum computing capabilities.

The work addresses a critical need for standardized benchmarks in the field of fault-tolerant quantum computing, where assessing progress is currently difficult. Existing benchmarks lack the granularity needed to track year-over-year advancements, and many focus on restricted problem sizes that don’t accurately reflect the difficulty of breaking real-world encryption. This new suite of challenges provides a transparent and reproducible ruler for measuring progress towards the point where quantum computers could pose a threat to Bitcoin’s security. The researchers meticulously calibrated the classical computational cost of solving these problems, establishing a baseline for comparison with quantum algorithms.

They then modeled the quantum resources required to run Shor’s algorithm on these challenges, mapping the algorithm’s requirements to different quantum error correction codes, including surface codes, repetition cat codes, and LDPC cat codes, to estimate the number of physical qubits needed. Their analysis suggests that a quantum computer capable of solving the full 256-bit ECDLP, the size used in Bitcoin, could emerge within the 2027-2033 timeframe. This prediction is based on current trends in quantum hardware development and assumptions about error rates and architectural improvements. The team’s work highlights the importance of proactively migrating digital assets to post-quantum cryptographic signatures to protect against future threats.

By providing a clear and quantifiable roadmap, this research serves as a crucial early warning system for the cryptocurrency community and the broader field of cybersecurity. The researchers emphasize that this challenge ladder is not a perfect predictor, as breakthroughs in quantum computing can occur unexpectedly, but it offers the best available public and auditable method for tracking progress and comparing different approaches to quantum cryptanalysis. The detailed modeling and sensitivity analysis allow the community to identify the key physical and architectural levers that will determine when quantum computers can realistically break Bitcoin’s encryption.

Graded Challenges Track Quantum Cryptographic Progress

This research introduces a carefully constructed series of challenges designed to track progress in the development of fault-tolerant quantum computers, specifically their ability to break modern encryption. The team created a graded suite of elliptic curve discrete logarithm problems (ECDLP), using the same mathematical structure as Bitcoin’s encryption, but systematically reducing the size of the problem from 256 bits down to 6 bits. This allows researchers to assess quantum computer performance on increasingly difficult tasks, providing a clear benchmark for advancement. The work establishes both classical and quantum baselines for solving these problems, calibrating performance against existing classical algorithms and estimating the resources required for a quantum solution using different quantum error correction codes.

Resource estimations suggest that a quantum computer capable of breaking the full 256-bit encryption, relevant to Bitcoin security, could emerge between 2027 and 2033, dependent on improvements in physical qubit performance and architectural choices. The authors acknowledge that the timeline is sensitive to these factors and that the availability of results depends on what research teams publish. This research provides a transparent and auditable “ruler” for tracking progress and highlights the need to proactively transition to post-quantum cryptographic signatures to protect digital assets.