Quantum Money and Bitcoin
This article is initially published in Albaron Ventures.
Quantum Money and Bitcoin Deemed one of the biggest potential technological revolutions of recent history, quantum computing poses security risks for cryptocurrency. This is because quantum computing can harness quantum mechanics to reach data processing levels otherwise impossible with traditional computing.
Quantum Money and Bitcoin In 2015, Google announced that its quantum prototype was 100 million times faster than any other computer in their laboratory nearly five years ago. In that short period, we’ve seen a massive explosion in the popularity and quantity of cryptocurrencies. It’s been estimated that to hack a single 64-digit hexadecimal private key; it would take most modern computers anywhere between 10,000 years to a few 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 essential 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 generally makes integer factorization much more accessible) for solving discrete logarithm problems.
Quantum Money and Bitcoin 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 — to mint, sign, and verify transactions. More specifically, instead of leveraging the existing cryptocurrency binary digital world (where a bit is either a one or a 0), quantum money uses quantum bits, or “qubits,” which can exist simultaneously in more than one state.
Enter “Quantum Money”
Quantum cryptography’s security is based on the No Cloning Theorem, which gives mathematical assurances that it is impossible to copy an arbitrary quantum state exactly. 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 creating quantum-resistant primitives, such as randomness and signatures. Quantum money aims to generate cash that is physically impossible to counterfeit.
This sharply contrasts the existing cash banknotes system, which can still be counterfeited. According to the United States Department of Treasury, roughly $70 million in counterfeit bills are circulated in the US, not counting the hundreds of millions seized.
Full quantum money would use quantum mechanics in each step involving the minting, signing, and verifying transactions.
For example, minting would entail running a quantum algorithm by the bank, sending the quantum state (photons and their condition) to the user through a quantum channel. Similarly, quantum verification would require sending the quantum form 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 still needs a quantum computer, the bank only uses 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. Still, the creation process originated in the minting that involves the bank, which can identify if a state would be copied subsequently, attempting double-spending. One area that still needs more research is public semi-quantum money, which wouldn’t require a bank to verify it. However, this would generally require a memory-dependent system (unlike private semi-quantum cash), which makes it a lot more challenging due to how hard 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.
Quantum Money and Bitcoin However, breaking the private key assumes knowing the corresponding public key, which is only 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 time available for computing the private key (generally less than 1 hour) would still pose significant computational challenges, even in a quantum computing world, estimated at the earliest to be in the 2030s-2040s (ECRYPT II).
Final Thoughts
Quantum Money and Bitcoin computing likely won’t cause the problems we envision today. Instead, 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.
Quantum Money and Bitcoin 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 funds. Still, 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