What is a Quantum Computer?
The New Scientist answers the question What is a Quantum Computer?
Classical computers, which include smartphones and laptops, encode information in binary “bits” that can either be 0s or 1s. In a quantum computer, the basic unit of memory is a quantum bit or qubit.
For instance, eight bits is enough for a classical computer to represent any number between 0 and 255. But eight qubits is enough for a quantum computer to represent every number between 0 and 255 at the same time. A few hundred entangled qubits would be enough to represent more numbers than there are atoms in the universe.
In situations where there are a large number of possible combinations, quantum computers can consider them simultaneously. Examples include trying to find the prime factors of a very large number or the best route between two places.
That last paragraph above exposes the problem for not just Bitcoin security but virtually all public-private key password encryption.
How Can 7 Bits Represent So Much?
Technology review describes superposition.
Qubits can represent numerous possible combinations of 1 and 0 at the same time. This ability to simultaneously be in multiple states is called superposition. To put qubits into superposition, researchers manipulate them using precision lasers or microwave beams.
Researchers can generate pairs of qubits that are “entangled,” which means the two members of a pair exist in a single quantum state. Changing the state of one of the qubits will instantaneously change the state of the other one in a predictable way. This happens even if they are separated by very long distances.
Nobody really knows quite how or why entanglement works. It even baffled Einstein, who famously described it as “spooky action at a distance.” But it’s key to the power of quantum computers.
It takes supercooled computers and vacuum chambers to keep qubits stable long enough to perform a complex calculation.
The potential is immense.
Airbus, for instance, is using them to help calculate the most fuel-efficient ascent and descent paths for aircraft. And Volkswagen has unveiled a service that calculates the optimal routes for buses and taxis in cities in order to minimize congestion.
Google’s Aim
The Wall Street Journal reports Google Aims for Commercial-Grade Quantum Computer by 2029
Alphabet Inc.’s Google plans to spend several billion dollars to build a quantum computer by 2029 that can perform large-scale business and scientific calculations without errors, said Hartmut Neven, a distinguished scientist at Google who oversees the company’s Quantum AI program. The company recently opened an expanded California-based campus focused on the effort, he said.
“We are at this inflection point,” said Dr. Neven, who has been researching quantum computing at Google since 2006. “We now have the important components in hand that make us confident. We know how to execute the road map.”
Google is interested in many potential uses for the technology, such as building more energy-efficient batteries, creating a new process of making fertilizer that emits less carbon dioxide and speeding up training for machine-learning, a branch of artificial intelligence, Dr. Neven said.
For those and other use cases, Google says it will need to build a 1-million-qubit machine capable of performing reliable calculations without errors. Its current systems have less than 100 qubits.
What About Bitcoin?
Deloitte discusses Quantum Computers and the Bitcoin Blockchain.
Since Google announced that it achieved quantum supremacy there has been an increasing number of articles on the web predicting the demise of currently used cryptography in general, and Bitcoin in particular. The goal of this article is to present a balanced view regarding the risks that quantum computers pose to Bitcoin.
All known (classical) algorithms to derive the private key from the public key require an astronomical amount of time to perform such a computation and are therefore not practical. However, in 1994, the mathematician Peter Shor published a quantum algorithm that can break the security assumption of the most common algorithms of asymmetric cryptography. This means that anyone with a sufficiently large quantum computer could use this algorithm to derive a private key from its corresponding public key, and thus, falsify any digital signature.
The prerequisite of being “quantum safe” is that the public key associated with this address is not public. But as we explained above, the moment you want to transfer coins from such a “safe” address, you also reveal the public key, making the address vulnerable. From that moment until your transaction is “mined”, an attacker who possesses a quantum computer gets a window of opportunity to steal your coins.
In such an attack, the adversary will first derive your private key from the public key and then initiate a competing transaction to their own address. They will try to get priority over the original transaction by offering a higher mining fee.
In the Bitcoin blockchain it currently takes about 10 minutes for transactions to be mined (unless the network is congested which has happened frequently in the past). As long as it takes a quantum computer longer to derive the private key of a specific public key then the network should be safe against a quantum attack. Current scientific estimations predict that a quantum computer will take about 8 hours to break an RSA key, and some specific calculations predict that a Bitcoin signature could be hacked within 30 minutes.
There’s much more to the article including some advice for Bitcoin holders about public keys that needs to be addressed now.
But if quantum computers ever become fast enough, the security of the entire blockchain will melt down.
Deloitte notes the only solution is ‘post-quantum cryptography’ to build robust and future-proof blockchain applications.
That caution applies not only to Bitcoin but to any existing application that uses public-private keys.
How Does This Work?
Thanks!
I am fascinated by the idea that a bit can be both 0 and 1 at the same time.
I knew that but I was unaware that Einstein did not now how entangled qubits works and nobody still does.
We have something and no one knows how it even works! https://t.co/SI9C6Oks7z
— Mike “Mish” Shedlock (@MishGEA) May 23, 2021
Post Quantum Cryptography
Wikipedia has an excellent discussion of Post-quantum cryptography
One of the simple proposed solutions is to double the key size but there are practical considerations.
A practical consideration on a choice among post-quantum cryptographic algorithms is the effort required to send public keys over the internet.
The Open Quantum Safe project was started in late 2016 and has the goal of developing and prototyping quantum-resistant cryptography. It aims to integrate current post-quantum schemes in one library.
The Open Quantum Safe project currently supports 6 algorithms.
Beyond that, Forward Secrecy allows the use of one-time keys, generated at random.
Forward secrecy protects data on the transport layer of a network that uses common SSL/TLS protocols, including OpenSSL, when its long-term secret keys are compromised, as with the Heartbleed security bug. If forward secrecy is used, encrypted communications and sessions recorded in the past cannot be retrieved and decrypted should long-term secret keys or passwords be compromised in the future, even if the adversary actively interfered, for example via a man-in-the-middle attack.
The value of forward secrecy is that it protects past communication. This reduces the motivation for attackers to compromise keys. For instance, if an attacker learns a long-term key, but the compromise is detected and the long-term key is revoked and updated, relatively little information is leaked in a forward secure system.
Things may not be quite as simple as simply saying double the key size.
Mish
