How Quantum Computers Pose a Threat to Bitcoin Security in Under 10 Minutes

The first part of this series delved into the fundamental principles of quantum computing, distinguishing it from classical computing. However, understanding the inner workings of a quantum computer is just the beginning; the real question is how it can be utilized to compromise bitcoin's security. This involves grasping the cryptographic mechanisms that underpin bitcoin, identifying the vulnerabilities, and comprehending the role of quantum algorithms in exploiting these weaknesses. This piece begins by examining bitcoin's encryption methodology, known as elliptic curve cryptography, and progresses to discuss the recent findings by Google that significantly reduce the estimated time required to break this encryption using a quantum computer. The core of bitcoin's security lies in a mathematical concept known as the elliptic curve discrete logarithm problem. Essentially, each bitcoin wallet has a pair of keys: a private key, which is a secret number, and a public key, which is derived from the private key through a complex mathematical operation. The relationship between these keys is based on a one-way function, meaning it's straightforward to generate a public key from a private key but virtually impossible to reverse the process using conventional computers. This one-way function is the backbone of bitcoin's security model, ensuring that only the owner of a private key can spend the associated bitcoins. However, the advent of quantum computing, particularly through the application of Shor's algorithm, threatens to upend this security paradigm. Shor's algorithm is a quantum algorithm that can efficiently solve the discrete logarithm problem, thereby breaking the encryption that protects bitcoin transactions. The algorithm leverages 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 knowing it allows for the easy calculation of the private key, given the public key and the parameters of the elliptic curve. The process involves putting the input register of the quantum computer into a superposition state, representing all possible inputs simultaneously, and then applying a quantum operation known as the Fourier transform to reinforce the correct answers while canceling out the incorrect ones. Google's recent paper has significant implications for the timeline of a potential quantum attack on bitcoin. By designing quantum circuits that implement Shor's algorithm against bitcoin's specific elliptic curve, the researchers have shown that the number of qubits required for such an attack can be significantly lower than previously estimated, potentially fewer than 500,000. Moreover, they introduced a practical attack scenario where parts of the computation can be precomputed, leaving only the final step to be completed once a target public key is identified. This final step, according to Google's estimates, could take approximately nine minutes, which is alarmingly close to the average time it takes for a bitcoin transaction to be confirmed. The implications are profound, especially for the approximately 6.9 million bitcoins whose public keys have already been exposed on the blockchain, making them vulnerable to an 'at-rest' attack that does not require racing against the clock. As quantum computing technology advances, the gap between the potential for a quantum attack and the security measures in place to protect bitcoin is narrowing. Understanding these dynamics is crucial for assessing the future security of bitcoin and other cryptocurrencies that rely on similar cryptographic principles.