The Quantum Threat to Bitcoin: How Your Cryptocurrency Could be Stolen in Under 10 Minutes

The first part of this series explored the fundamental principles of quantum computing. However, understanding how quantum computers work is only half the story; the other half involves grasping what they can attack and how they can be used maliciously, such as stealing bitcoin. This piece focuses on the target of such attacks: the encryption that secures bitcoin transactions. It explains why a quantum algorithm can break this encryption and discusses the implications of Google's recent paper on quantum computing, which has significant ramifications for the timeline of potential attacks. Bitcoin relies on elliptic curve cryptography, a system that uses a pair of keys: a private key, which is a secret number, and a public key, derived from the private key through a mathematical operation on a specific curve. This process is akin to a one-way map, where it's easy to go forward but virtually impossible to reverse the process using classical computers. The security of bitcoin transactions hinges on this one-way function, where the private key proves ownership, and the public key can be shared without compromising security. However, the discovery of Shor's algorithm by mathematician Peter Shor in 1994 introduced a quantum algorithm that can efficiently break this encryption. Shor's algorithm solves the discrete logarithm problem, which classical computers find nearly impossible, in polynomial time. The algorithm works by converting the problem of finding a private key into finding the period of a function, which quantum computers can solve efficiently by applying the function to all possible inputs simultaneously and then using the Fourier transform to find the correct period. This process exploits the quantum properties of superposition, entanglement, and interference. Despite Shor's algorithm being known for over 30 years, its application has been limited by the requirement for a large number of stable qubits to maintain coherence throughout the calculation. Recent estimates by Google have significantly reduced the number of qubits needed, from millions to fewer than 500,000, making the threat more tangible. Google's paper not only reduced the qubit count but also introduced a practical attack scenario, where parts of the calculation can be precomputed, leaving the quantum computer in a primed state, ready to finish the calculation once a target public key appears. This scenario introduces a 'nine-minute window' where an attacker has roughly nine minutes to derive a private key and submit a competing transaction after a user broadcasts a transaction. While this 'mempool attack' is alarming, it requires a quantum computer that does not yet exist. A more pressing concern is the approximately 6.9 million bitcoin already vulnerable to an 'at-rest' attack because their public keys have been exposed on the blockchain. These coins can be targeted without any time constraint, posing a significant risk once a capable quantum computer is built.