The Quantum Threat to Bitcoin: How a Powerful Computer Can Crack Encryption in Under 10 Minutes

The first part of this series provided an overview of quantum computing, focusing on its underlying physics. However, understanding how quantum computers work is only half the story; the other half involves comprehending what they can attack and how. This piece explores the target of a quantum attack: the encryption mechanism used by bitcoin. It discusses why a quantum algorithm can break this encryption and the recent developments, such as Google's paper, that have altered the timeline of this threat. Bitcoin utilizes elliptic curve cryptography to verify ownership, a system that relies on a one-way mathematical function. This function, based on the 'secp256k1' curve, takes a private key (a 256-digit binary number) and generates a public key. The process is akin to a one-way map, where starting from a known point (the generator point G), a series of steps defined by the curve's mathematics leads to a public key. Anyone can confirm the public key, but reversing the process to find the private key is virtually impossible for classical computers. This is due to the elliptic curve discrete logarithm problem, which is estimated to take longer than the age of the universe to solve using the best-known classical algorithms. The security of bitcoin hinges on this one-way function. However, in 1994, mathematician Peter Shor discovered a quantum algorithm that can efficiently solve the discrete logarithm problem. Shor's algorithm exploits the principles of quantum mechanics, including superposition, entanglement, and interference, to find the period of a function related to the elliptic curve. This period is crucial because, once known, it allows for the quick derivation of the private key. The algorithm operates by putting its input into a superposition, allowing it to evaluate the function for all possible inputs simultaneously. It then applies a quantum operation called the Fourier transform, which cancels out incorrect answers and reinforces the correct ones. The result is the period of the function, from which the private key can be easily calculated. Despite Shor's algorithm being known for over 30 years, implementing it has been beyond reach due to the requirement for a large number of stable qubits. Recent estimates suggest that fewer than 500,000 qubits might be sufficient, a significant reduction from previous estimates. Google's Quantum AI division, along with contributions from other researchers, designed quantum circuits that implement Shor's algorithm against bitcoin's elliptic curve, using approximately 1,200 to 1,450 logical qubits. The practical attack scenario introduced by Google involves precomputing parts of the algorithm that depend on the elliptic curve's fixed parameters, allowing the quantum computer to sit in a primed state. When a target public key appears, the machine only needs to finish the second half of the calculation, which Google estimates takes about nine minutes. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction. For bitcoin, this means that if a user broadcasts a transaction and their public key is visible, an attacker has roughly nine minutes to redirect funds, with a 41% chance of succeeding before the original transaction confirms. Moreover, approximately 6.9 million bitcoin are vulnerable to an 'at-rest' attack because their public keys have already been exposed on the blockchain. These coins can be targeted without any time constraint, as the attacker can take as long as needed to derive the private key. The implications of this quantum threat and the ongoing developments in quantum computing and bitcoin security will be explored in the next part of this series.