On 31 March, Google Quantum AI announced it has published a whitepaper showing that future quantum computers may break the Elliptic Curve Cryptography, which protects blockchain technologies and cryptocurrencies, with fewer qubits and gates than previously realized.
The updated estimates reflect a 20-fold reduction in the number of qubits and gates necessary to break the 256-bit elliptic curve discrete logarithm problem (ECDLP-256), on which elliptic curve cryptography is based. Specifically, Google has compiled two quantum circuits that implement Shor’s algorithm for ECDLP-256: one that uses less than 1,200 logical qubits and 90 million Toffoli gates, and one that uses less than 1,450 logical qubits and 70 million Toffoli gates. Google estimates that these circuits can be executed on a superconducting qubit Cryptographically Relevant Quantum Computer (CRQC) with fewer than 500,000 physical qubits in a few minutes, given standard assumptions about hardware capabilities that are consistent with some of Google’s flagship quantum processors. This is an approximately 20-fold reduction in the number of physical qubits required to solve ECDLP-256 and a continuation of a long history of gradual optimization in compiling quantum algorithms to fault-tolerant circuits.
To share this research responsibly, Google engaged with the U.S. government and developed a new method to describe these vulnerabilities via a zero-knowledge proof, so they can be verified without providing a roadmap for bad actors.
Read the announcement here, and the whitepaper here.
