John Smith Dec 22, 2018
Quantum computing will profoundly disrupt Bitcoin and the entire cryptocurrency ecosystem. Bitcoin’s developers have a plan for transitioning to quantum-resistant cryptography, but their best efforts may not be enough to avert existential risk to the network.
[...]
The security of these digital signatures relies on the existence of mathematical problems that are much harder to solve than their solutions are to check. To crack the so-called Elliptic Curve Digital Signature Algorithm (ECDSA) used by Bitcoin would take today’s fastest supercomputer far over a trillion years. However, in 1999, Peter Shor published an algorithm could do it in ‘polynomial time’, easily on the timescale of hours or minutes [1]. The catch is, this algorithm requires a different kind of computer altogether — a quantum computer.
[...]
The alarm has begun to be raised about the approaching downfall of modern cryptographic standards. Digital signature algorithms such as ECDSA and the closely related RSA secure not only Bitcoin and cryptocurrencies but the entire internet, banking system, and more. The issue has been covered by the Economist [4], Fortune [5], and the New York Times [6]. While large-scale quantum computers appear to still be at least five years out, major governmental institutions such as the NSA are already beginning their transition to post-quantum standards [7]. The United States’ National Institute of Standards and Technology, or NIST, has stated that “regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing”. Several scientific articles have gone further into detail on the nature of the threat specifically to Bitcoin and blockchains [8, 9], including a recent Nature commentary [11].
The response in the cryptocurrency community, however, has so far been muted.
[...]
The essential problem is this. If Bitcoin changes nothing, then eventually, addresses with known public keys will have their private keys derived from those public keys by a quantum computer running Shor’s algorithm. This includes very old addresses (including Satoshi’s) as well as addresses that have sent a transaction, publishing their public keys to the blockchain. The owner of that quantum computer could then simply use the found private keys to send bitcoin from those addresses to themselves.
A transition to a post-quantum digital signature algorithm does not solve this problem; an attacker could simply use the vulnerability to claim balances on the new chain using the old-format private keys. An alternative method of attack would be to short bitcoin and then make this vulnerability public, crashing the value of bitcoin and enriching themselves in the process.
The commit-delay-reveal scheme is meant to help Bitcoin address these challenges. [...]
That is the most rigorous solution available. Unfortunately, it has several crucial flaws. [...]
Bitcoin’s developers have also considered stopgap measures. [...]
Like the commit-delay-reveal scheme, these mechanisms also rely on individual users opting in to using the more secure signatures, leaving millions of bitcoins behind in vulnerable addresses.
HOW LONG DO WE HAVE?
The number of logical qubits required to crack secp256k1, the specific elliptic curve on which Bitcoin’s public-key cryptography is based, is approximately 2330 [17]. The noisiness associated with qubits, however, means that the number of qubits in a quantum computer is larger than the number of logical qubits that it functionally possesses. A scientific paper by Aggarwal et al. (2017) modeled the development of quantum computing given optimistic and conservative assumptions, respectively; this model estimates that 2330 logical qubits will be available between approximately 2024 and 2030. If higher-bit elliptic curves are used as a stopgap, it will shift Bitcoin’s security window by a year or two. Eventually, though, the blockchain’s ability to support more complex curves will be outstripped by the exponentially-growing computational abilities of quantum computers.
Quantum computing will profoundly disrupt Bitcoin and the entire cryptocurrency ecosystem. Bitcoin’s developers have a plan for transitioning to quantum-resistant cryptography, but their best efforts may not be enough to avert existential risk to the network.
[...]
The security of these digital signatures relies on the existence of mathematical problems that are much harder to solve than their solutions are to check. To crack the so-called Elliptic Curve Digital Signature Algorithm (ECDSA) used by Bitcoin would take today’s fastest supercomputer far over a trillion years. However, in 1999, Peter Shor published an algorithm could do it in ‘polynomial time’, easily on the timescale of hours or minutes [1]. The catch is, this algorithm requires a different kind of computer altogether — a quantum computer.
[...]
The alarm has begun to be raised about the approaching downfall of modern cryptographic standards. Digital signature algorithms such as ECDSA and the closely related RSA secure not only Bitcoin and cryptocurrencies but the entire internet, banking system, and more. The issue has been covered by the Economist [4], Fortune [5], and the New York Times [6]. While large-scale quantum computers appear to still be at least five years out, major governmental institutions such as the NSA are already beginning their transition to post-quantum standards [7]. The United States’ National Institute of Standards and Technology, or NIST, has stated that “regardless of whether we can estimate the exact time of the arrival of the quantum computing era, we must begin now to prepare our information security systems to be able to resist quantum computing”. Several scientific articles have gone further into detail on the nature of the threat specifically to Bitcoin and blockchains [8, 9], including a recent Nature commentary [11].
The response in the cryptocurrency community, however, has so far been muted.
[...]
The essential problem is this. If Bitcoin changes nothing, then eventually, addresses with known public keys will have their private keys derived from those public keys by a quantum computer running Shor’s algorithm. This includes very old addresses (including Satoshi’s) as well as addresses that have sent a transaction, publishing their public keys to the blockchain. The owner of that quantum computer could then simply use the found private keys to send bitcoin from those addresses to themselves.
A transition to a post-quantum digital signature algorithm does not solve this problem; an attacker could simply use the vulnerability to claim balances on the new chain using the old-format private keys. An alternative method of attack would be to short bitcoin and then make this vulnerability public, crashing the value of bitcoin and enriching themselves in the process.
The commit-delay-reveal scheme is meant to help Bitcoin address these challenges. [...]
That is the most rigorous solution available. Unfortunately, it has several crucial flaws. [...]
Bitcoin’s developers have also considered stopgap measures. [...]
Like the commit-delay-reveal scheme, these mechanisms also rely on individual users opting in to using the more secure signatures, leaving millions of bitcoins behind in vulnerable addresses.
HOW LONG DO WE HAVE?
The number of logical qubits required to crack secp256k1, the specific elliptic curve on which Bitcoin’s public-key cryptography is based, is approximately 2330 [17]. The noisiness associated with qubits, however, means that the number of qubits in a quantum computer is larger than the number of logical qubits that it functionally possesses. A scientific paper by Aggarwal et al. (2017) modeled the development of quantum computing given optimistic and conservative assumptions, respectively; this model estimates that 2330 logical qubits will be available between approximately 2024 and 2030. If higher-bit elliptic curves are used as a stopgap, it will shift Bitcoin’s security window by a year or two. Eventually, though, the blockchain’s ability to support more complex curves will be outstripped by the exponentially-growing computational abilities of quantum computers.
