How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
We use Shor's algorithm for the computation of elliptic curve private keys as a case study for resource estimates in the silicon-photonics-inspired active-volume architecture. Here, a fault-tolerant surface-code quantum computer consists of modules with a logarithmic number of non-local inter-module connections, modifying the algorithmic cost function compared to 2D-local architectures. We find that the non-local connections reduce the cost per key by a factor of 300-700 depending on the operating regime. At 10% threshold, assuming a 10-$μ$s code cycle and non-local connections, one key can be generated every 10 minutes using 6000 modules with 1152 physical qubits each. By contrast, a device with strict 2D-local connectivity requires more qubits and produces one key every 38 hours. We also find simple architecture-independent algorithmic modifications that reduce the Toffoli count per key by up to a factor of 5. These modifications involve reusing the stored state for multiple keys and spreading the cost of the modular division operation over multiple parallel instances of the algorithm.
Claim as recorded
Resource estimate for Shor ECC-256 private-key recovery. The v1 baseline record ecc256-litinski-2023 takes the paper 2D-local surface-code configuration, not the headline active-volume one. Verified against the paper body, not the abstract: "we perform a resource estimate for a baseline architecture with 2D-local connections ... In total, we need 6000 logical qubits and 109 million Toffoli gates per key", and "with a 1 us code cycle, superconducting qubits generate one key every 484*28 seconds, or 3.8 hours". That settles the ambiguity the abstract creates, where the same figure 6000 counts active-volume MODULES of 1152 physical qubits each. Stored: 6000 logical qubits, 109e6 Toffoli, 484e6 logical cycles at d=28, 3.8 h. Two stored figures are derived rather than stated -- spacetime volume 7.28e13 logical qubit-rounds and success probability 0.978 -- and the record own uncertainty_notes say so. This is the only usable resource estimate at the headline runtime scenario, so it alone decides which cryptographic targets the model can evaluate.
Canonical citation
Daniel Litinski
arXiv (Cornell University / arXiv) — tier A
arXiv: 2306.08585v1
Related model versions
This record has not been used in a published model version yet. Being listed here is not the same as feeding a forecast.
Related evidence
- Quantum error correction below the surface code threshold — Logical error rate , 2024-08-24
This is a probabilistic model of CRQC capability based on public evidence. Its primary result is a forecast interval built from the percentiles the evidence can resolve. A percentile that does not cross within the model’s horizon is reported as undefined, never estimated, together with the share of scenarios that do not cross. The model is recalculated weekly and does not claim day-level or second-level certainty.