Bitcoin in the Age of Quantum Computing

Deemed as one of the biggest potential technological revolutions of recent history, quantum computing also poses security risks for the cryptocurrency space. Quantum-computing is able to harness quantum mechanics to reach data processing levels otherwise impossible with traditional computing.

In 2015, Google announced that its quantum prototype was 100 million times faster than any other computer in their laboratory, and this was nearly five years ago. In that short time span, we’ve seen a massive explosion in popularity and quantity of cryptocurrencies.

It’s been estimated that in order to hack a single a 64-digit hexadecimal private key, it would take most modern computers anywhere between 10,000 years to a few billion billion years to crack. Google’s quantum supercomputer could potentially shave that time down to 200 seconds. 

Bitcoin’s security relies on the computational difficulty of the public-private key cryptography function (ECDSA), which becomes computationally feasible to solve with quantum computing capabilities.

More specifically, it is vulnerable to a modified Schor’s algorithm (which normally makes integer factorization much easier) for solving discrete logarithm problems. 

Unlike a “quantum-resistant cryptocurrency” (which is something bitcoin can evolve towards by updating the signature algorithm), “quantum money” uses quantum mechanics — photons and their state — in order to mint, sign, and verify transactions.

More specifically, instead of leveraging the existing cryptocurrency binary digital world (where a bit is either a 1 or a 0), quantum money uses quantum bits, or “qubits,” which can exist in more than one state at the same time. 

What is Quantum Money?

Quantum cryptography’s security is based on the No Cloning Theorem, which gives mathematical assurances that it is impossible to exactly copy an arbitrary quantum state. More intuitively, the quantum state is always different than what can be measured/observed from the outside, and every measurement alters the quantum state.

Quantum money is one of the main concepts in the Quantum Cryptography field, which focuses on the creation of quantum-resistant primitives, such as randomness and signatures. The goal of quantum money is to create money that is physically impossible to counterfeit. 

This is in sharp contrast to the existing cash banknotes system, which is still capable of being counterfeited. According to the United States Department of Treasury, there are roughly $70 million counterfeit bills in circulation in the US, not counting the hundreds of millions that have been seized. 

Full quantum money would use quantum mechanics in each of the steps involving the minting, signing of transactions, and verifying transactions. 

For example, minting would entail having a quantum algorithm run by the bank, which would send the quantum state (photons and their state) to the user, through a quantum channel. Similarly, quantum verification would require sending of the quantum state to the bank to be verified. 

Semi-Quantum Money as a Hybrid Approach

An intermediary step to full quantum money could be Semi-Quantum Money, which uses classical minting and classical verification for the bank side. This means that while the user would still need a quantum computer, the bank would only use a classical computer and a classical communication channel.

This lowers the barrier significantly, creating a more feasible goal for the evolution of money. 

Interestingly, in semi-quantum money, the user creates the banknotes, but the creation process is originated in the minting that involves the bank, which can identify if a state would be copied subsequently, attempting double spends.

One area that still needs more research would be that of a public semi-quantum money, which wouldn’t require a bank to verify it. This would generally require a memory-dependent system (unlike private semi-quantum money), which makes it a lot more challenging due to how challenging it is to store information in quantum memory. 

What Would Happen to Bitcoin in a Quantum Computing World?

Bitcoin uses SHA 256 for the hashing algorithm and ECDSA for signatures. While SHA-256’s security wouldn’t be impacted by quantum computing (since it uses symmetric encryption), breaking ECDSA would become much easier, since it is based on the classical computational infeasibility of breaking the private key. 

However, breaking the private key assumes knowing the corresponding public key, which is only being revealed when trying to spend bitcoins (through UTXO).

This means that if only one Bitcoin address is being utilized at a time, the risk only exists for the amount of time between transaction broadcasting and addition to a block. 

Therefore, the amount of time available for computing the private key (generally less than 1 hour) would still pose significant computational challenges, even in a quantum computing world, which is estimated at the earliest to in the 2030s-2040s (ECRYPT II). 

Final Thoughts

Quantum computing likely won’t cause the level of problems we are envisioning today. As the threat of quantum computing materializes, Bitcoin would be able to adjust gradually by evolving to adopt more quantum-resistant cryptography such as  Merkle Schemes, Lamport’s Signature, and Secret Sharing. 

In the meantime, new versions of Quantum Money are being created, such as public and private quantum money, or semi-quantum money. Long term, the mathematical assurances provided by the No Cloning Theorem would be able to increase the security of the money, but the path will be created with intermediary building blocks that bridge the current fiat and crypto worlds with the more distant quantum money world. 

Sources:

https://bitcoinist.com/heres-exactly-how-long-it-would-take-to-crack-your-bitcoin-wallet/

https://bitcoin.stackexchange.com/questions/2847/how-long-would-it-take-a-large-computer-to-crack-a-private-key

https://thenextweb.com/contributors/2018/04/14/quantum-computing-wreak-havoc-cryptocurrency/

https://en.wikipedia.org/wiki/Counterfeit_United_States_currency

https://cointelegraph.com/news/quantum-computing-vs-blockchain-impact-on-cryptography

https://www.inc.com/eric-mack/no-google-its-quantum-computer-arent-killing-bitcoin-anytime-soon.html

https://www.forbes.com/sites/amycastor/2017/08/25/why-quantum-computings-threat-to-bitcoin-and-blockchain-is-a-long-way-off/#359dad642882

https://orsattath.wordpress.com/2013/08/01/bitcoin-vs-quantum-money-the-problem-of-accountability/

http://webee.technion.ac.il/people/ittay/aft19/aft19-final25.pdf

(This article was originally published in albaronventures.com)