Google says one of its quantum computers has been able to solve a problem that would be practically impossible to do on a conventional computer, becoming the first to achieve so-called “quantum supremacy”.
Google’s quantum computer was reportedly able to solve a calculation — proving the randomness of numbers produced by a random number generator — in 3 minutes and 20 seconds that would take the world’s fastest traditional supercomputer, Summit, around 10,000 years.
If true, it is big news. A paper containing details of the work was posted to a NASA server last week. However, it was quickly taken down. Several media outlets reported on the rumors.
The crypto world watched this event unfold closely, as they should. After all, since the advent of bitcoin, the threat of quantum computing has motivated researchers, technologists and, now, governments, to build software able to resist attack by even the most powerful quantum computers.
What exactly is “quantum supremacy”? Why is it a threat to the crypto community? Will Bitcoin and Ethereum collapse in the face of “quantum supremacy”?
What exactly is “quantum supremacy”?
Shortly after the news of Google’s alleged achievement of quantum supremacy broke, the paper was taken down from NASA website for unknown reasons. Google has not made any comments on it yet but there is a reasonable belief as Google and NASA have been on the verge of achieving quantum supremacy for the last year when Google collaborated with NASA in 2018 to help them prove quantum supremacy.
While powerful sounding, quantum supremacy is a term that describes the ability of quantum computing devices to solve some specific problems that classical computers practically cannot.
Google’s competitor, IBM, released a prototype quantum computer with 7 “quantum bits” (qubits) — a measure of the computer’s quantum power — in 2001. In the past two years, Intel, IMB, and Google have released similar prototypes with 49, 50, and 72 qubits respectively. The Chinese Academy of Science also achieved a quantum computer prototype with 11 qubits.
Why is it a threat to the crypto community?
In theory Google’s alleged 53-qubits quantum computer could break 53-bit cryptography in seconds.
But what you need to know about Bitcoin to understand the potential threat of quantum computing is that its architecture relies on two algorithms: Elliptical Curve Digital Signature Algorithm (ECDSA) for digital signatures and SHA-256 as a hash function. Theoretically, a quantum computer can use Shor’s algorithm to break ECDSA.
A bitcoin wallet contains a collection of key pairs, each consisting of a private key and a public key. ECDSA is the cryptography behind private and public keys used in Bitcoin. It consists of combining the math behind finite fields and elliptic curves to create one-way equations. A private key is a number, usually picked at random. From the private key, bitcoin use elliptic curve multiplication, a one-way cryptographic function, to generate a public key. From the public key, bitcoin uses a one-way cryptographic hash function to generate a bitcoin address.
A private key can be applied to the digital fingerprint of a transaction to produce a numerical signature. This signature can only be produced by someone with knowledge of the private key., Meanwhile, anyone with access to the public key and the transaction fingerprint can use them to verify the signature. If a computer gets the public key and uses the public key to calculate the private key, it can manipulate assets on the blockchain.
Bitcoin use secp256k1, as the parameters of the elliptic curve in its public-key cryptography. This means that it is easy to calculate public key based on a private but the reverse is very difficult, making the whole process safe.
SHA-256 is a member of the SHA-2 cryptographic hash functions designed by the NSA. SHA stands for Secure Hash Algorithm. Cryptographic hash functions are mathematical operations run on digital data; by comparing the computed “hash” (the output from execution of the algorithm) to a known and expected hash value, a person can determine the data’s integrity. A one-way hash can be generated from any piece of data, but the data cannot be generated from the hash.
Shor’s algorithm can be used to break the elliptic curve cryptography by computing discrete logarithms on a hypothetical quantum computer. Theoretically, a quantum computer could use Shor’s algorithm to get your private from your public key, as Jack Matier of the Quantum Resistant Ledger recently explained in a Medium post. A paper predicts that quantum computers can break bitcoin’s signature scheme in less than 10 minutes (600 seconds) as early as 2027.
Will Bitcoin and Ethereum collapse in the face of “quantum supremacy”?
It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20–30 years. So does this mean that bitcoin is not safe anymore? Not quite.
Considering that Google’s machine is only 53 qubits, it is still no match for the kind of cryptography used in bitcoin. Additionally, Shor’s algorithm does not pose a threat to bitcoin yet.
Bitcoin wallet address is based on the public key and private key system of ECDSA. However, the wallet address does not use the public key directly. Rather, it uses the hash value of the public key. If you have not exposed your public key, Shor’s algorithm is useless. Hence, even if a quantum computer breaks the crypto algorithms, it cannot threaten the addresses that have never made any transactions.
While the native encryption algorithms used by Bitcoin and other proof-of-work coins are safe for now, the fact is that the rate of advancements in quantum technology is increasing, and that could, in time, pose a threat. But just like how quantum technology is advancing, so is crypto projects.
There are already efforts to develop new cryptography algorithms for a post-quantum era.
Justin Drake, an Ethereum developer working on sharding, has stated that the Ethereum team is working, although at a very early research stage, on Ethereum 3.0. That is planned to have super quadratic scaling, he said.
In an interview where he was asked about this vision for ETH 3.0, Vitalik Buterin, programmer and writer primarily known as a co-founder of Ethereum, said, “STARKs, STARKs and lots of STARKs. Hopefully some nice way to achieve 2 second average block times. Extremely effective cross-shard communication, either at base layer or through a variety of easy-to-use layer 2 systems.” ETH 3.0 will focus on quantum resistance and quantum security.
Similarly, Bitcoin can upgrade its algorithm and fork to tackle the threats that quantum computers pose potentially. Bitcoin has made incredible advancements in the past decade. It has seen the rapid development of computers. None of the advanced technology — be it single-core CPU, multi-core CPU, supercomputers, or artificial intelligence — has managed to challenge Bitcoin’s cryptocurrency system so far. It is safe to say that Bitcoin and Ethereum will not be threatened by the threats of quantum supremacy. Rather, it will perfect itself facing those challenges.
Reasons Why Quantum Supremacy Won’t Threaten Bitcoin was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.