Two recent studies indicate quantum computers could crack elliptic curve cryptography—securing banks, internet traffic, and cryptocurrencies like Bitcoin—with far fewer qubits than previously estimated: around 10,000-30,000 for one approach or 500,000 for another. Researchers highlight rapid hardware progress, urging a shift to post-quantum standards.
Researchers led by Dolev Bluvstein at Oratomic analyzed Shor's algorithm using neutral atoms trapped in optical tweezers as reconfigurable qubits, enabling all-to-all interactions and efficient error correction superior to fixed superconducting architectures. Their paper, 'Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits,' estimates fewer than 30,000 physical qubits could break 256-bit ECC—the basis for many secure systems—in 10 days, a 100-fold reduction from prior estimates. Arrays exceeding 6,000 qubits have already been demonstrated. Bluvstein noted that creating such an array may be feasible within a year, though reliable qubit control remains challenging, with no shortcuts like linking existing machines possible as qubits must interact directly. A full machine might be buildable by the end of the decade, potentially taking years to complete a decryption run. The team wrote, “Appropriately designed neutral-atom architectures could support cryptographically relevant implementations of Shor’s algorithm,” and called for adopting post-quantum cryptography.
Separately, Google researchers optimized Shor's algorithm for the elliptic curve discrete logarithm problem over secp256k1, Bitcoin's curve. Their methods require one circuit with under 1,200 logical qubits and 90 million Toffoli gates, or another with under 1,450 logical qubits and 70 million gates—translating to roughly 500,000 physical qubits for a solution in under 10 minutes, 20 times fewer resources than 2003 estimates. Citing misuse risks, Google withheld full details, releasing a zero-knowledge proof after US government consultation, and argued for limiting future quantum cryptanalysis disclosures.
Cryptography expert Brian LaMacchia, formerly at Microsoft, described the papers as showing steady qubit and algorithmic advances toward practical quantum cryptanalysis, though Matt Green of Johns Hopkins called Google's caution alarmist hype. The findings underscore vulnerabilities in current public-key systems, prompting urgency for cryptographic migration.