Bitcoin in the Age of Quantum Computing by@jacob-ramirez

February 6th 2020 672 reads

Jacob is part of aims to provide insights about crypto.

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.

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.

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.

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.

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).

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**)