How Quantum Computing Can Compromise Bitcoin Security in Under 10 Minutes

The first part of this series delved into the fundamentals of quantum computing, explaining how it differs from classical computing. However, understanding the inner workings of a quantum computer is not enough to comprehend how it can be used to steal bitcoin. To grasp this, it's essential to know what a quantum computer is attacking and how bitcoin's security measures work. This piece begins by examining bitcoin's encryption and the recent developments that have led to a significant reduction in the time it takes to break it, as identified by Google's quantum computing paper. Bitcoin's security relies on a system called elliptic curve cryptography, which involves a pair of keys: a private key and a public key. The public key is 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 move forward but virtually impossible to reverse. The security model is based on this one-way trapdoor, where the private key proves ownership, and the public key is safe to share because classical computers cannot reverse the math. However, a quantum algorithm known as Shor's algorithm can break this trapdoor. Discovered in 1994, Shor's algorithm efficiently solves the discrete logarithm problem, which is the backbone of bitcoin's security. The algorithm works by converting the problem into finding the period of a function, which is a task that quantum computers are well-suited for. By using quantum properties such as superposition, entanglement, and interference, the algorithm can find the period and ultimately the private key. The reason bitcoin remains secure today is that running Shor's algorithm requires a quantum computer with a large number of stable qubits. Recent estimates have reduced the number of qubits required, making the threat more plausible. Google's paper introduced a practical attack scenario, where parts of the algorithm can be precomputed, leaving only the second half to be completed once a target public key appears. This has led to the estimation that the second half of the calculation can be completed in approximately nine minutes, which is less than the average block confirmation time in bitcoin. This creates a window of opportunity for a quantum attacker to derive a private key and submit a competing transaction. The larger concern is the significant number of bitcoin that are already vulnerable to an 'at-rest' attack, where the public key has been exposed on the blockchain. These coins can be compromised without a race against time, as the attacker can take as long as needed to derive the private key.