Quantum Computing and Blockchain
--
At the “A Coffee with Ren III” event held by Huawei on November 6, Huawei founder Ren Zhengfei and Detlef Zuehlke, spiritual father of the smart factory Industry 4.0, Professor for Production Automation and former President of the UN Security Council, Founding Dean of the LKY School of National University of Singapore (NUS) conducted a panel discussion and dialogue on the topic: Digital sovereignty — From Discussion To Action. “A lot of people say how great the blockchain is, but it becomes worthless when facing quantum computing.” Regarding data security, Ren Zhengfei thinks he can resort to the law.
In response to Ren’s view, Research Director of Conflux Dr. Yang Guang believes that the threat quantum computers could pose on the security of blockchain technology is minimal from a technical point of view. Saying that the emergence of quantum computing will solve many computational bottlenecks is just a rumor. This rumor may have effects on cryptocurrency prices from the psychological aspect, rather than resulting in any technically serious issues.
Throughout the whole history of quantum computing, at its all-time high there were two and a half quantum algorithms widely considered as “useful”, i.e. potentially having “realistic applications”.
The first and most famous “useful” quantum algorithm is the Shor algorithm. Shor algorithm can be used to decompose large integers or find periods in groups. This algorithm has an exponential advantage over classical algorithms and hence can be used to attack RSA algorithms as well as elliptic curve encryption/signatures;
The second algorithm is the Grover search algorithm. This algorithm provides a quadratic speedup over classical brute-force algorithms. For example, the Grover search algorithm is able to find a specific element from a database of size N with time O(√N), whereas a classical search algorithm would require time linear in N in expectation.
The remaining “half” algorithm is the HHL algorithm for solving linear equations. This algorithm was believed to provide an exponential advantage in solving linear equations if several prerequisites are satisfied and hence could potentially speed up machine learning in a certain step. However, the HHL algorithm is only counted as “half” a useful algorithm because when using this approach, other steps of machine learning would dominate the running time and it is not clear whether the speed up provided by HHL is crucial. Furthermore, recent research works show that the same speed up is achievable with deliberately designed classical algorithms. Therefore, even this half cannot be counted, meaning now there are only two “useful” quantum computing algorithms.
Except for the above-mentioned algorithms, quantum computing has not yet been proved to have substantial advantages over classical computers on any meaningful and natural (not artificially constructed) problems. This has been a major concern in this area for decades.
Therefore, even if high-performance quantum computers were available, the biggest impact would be that RSA encryption and ECDSA signature schemes are no longer secure and need to be replaced with other quantum-resistant schemes.
Actually, there are already plenty of off-the-shelf cryptography schemes that are quantum-resistant. They are not widely used in practice only because there are no quantum computers as of now and no one feels the necessity to make such an update. It is sufficient to switch to those quantum-resistant schemes before quantum computers become an actual threat.
For general computing problems, including finding collisions of cryptographic hash functions, quantum computers are not known to have a substantial advantage over classical computers. In other words, it is impossible to find a collision of hash functions at once with a quantum computer, except for the quadratic speed up by Grover search.
Even though mining with Grover search algorithm may temporarily induce some performance improvement, this improvement is not much different than upgrading from a CPU to an ASIC miner. By the time everyone is mining with a quantum miner, the new balance will be established.
In addition, Satoshi Nakamoto is really admirable for his far-sightedness. Bitcoin addresses are hash values of public keys rather than the original public keys. And it is also recommended not to reuse an old address. Thus, as long as the public keys behind publicly-observable addresses are not exposed, even quantum computers cannot break the signature scheme. When transactions are broadcasted and the public key is exposed, it is very likely that the transaction will be confirmed before the attacker manages to crack the public key, and therefore it remains safe against a quantum adversary. With the hash-of-public-key design it is also convenient to upgrade to any other signature schemes, including those resistant to quantum attacks.
In summary, quantum computing has merely marginal impacts on the security of blockchains, and the impacts are easy to tackle and hence not a real threat from a technical perspective.
In September 2019, Google published a paper on Nature, claiming that their quantum computer “Sycamore” had achieved “quantum supremacy” and completed a complex task in just 3 minutes and 20 seconds whereas a summit supercomputer was estimated to spend over 10,000 years to finish the same task. This news got people concerned, as the general public starts to worry about that quantum computing may bring complete disruption to the blockchain’s proud encryption system.
So what impact does quantum supremacy have on a blockchain?
Not to mention that Google’s statement of 3m20s versus 10,000 years has been questioned by IBM and many other scientists from both industry and academia. Google actually picked a problem that is especially friendly to quantum computing and at the same time unfriendly to classic computers — simulating the behavior of a random quantum circuit — and concluded that quantum chips are better than universal purpose supercomputers on this particular problem.
This result can be a milestone in science, but it is meaningless to solving realistic problems. In addition, it does not mean that Google’s quantum computing chip can complete all calculations, a classical supercomputer would need a lot of time for, in a couple of minutes.
As an example, we cannot claim “donkeys are better than humans” or “Donkey Supremacy” if no person can mimic a donkey’s sound better than a real donkey.
Back to the question of the progress of quantum computers, according to Google’s current level of quantum chips, how long will it take for quantum computers to develop into cracking currently applied RSA encryption algorithms?
For example, to attack an RSA algorithm with 2048-bit key length (the lowest security standard in use nowadays), at least around 3000 to 4000 logical qubits are necessary. Google’s chip presently has 60 qubits, so according to quantum Moore’s law, it seems that it will take roughly 10 years to reach the necessary qubits.
However, Google’s quantum chip only implements physical qubits, but not logical qubits. Physical qubits are easily affected by external interference and cannot be directly used for complex calculations. So before being used in a quantum computer, multiple physical qubits must be organized with quantum error correction codes to implement a logical qubit. According to the current error level of quantum chips, it would take tens to hundreds of thousands of physical qubits to realize a single logical qubit. In an analogy to the hardware of classical computers, cracking 2048-bit RSA encryption requires a 4000-bit quantum CPU, but the current state-of-art quantum chip is roughly at the level of a “quantum triode”, even from realizing a quantum logic gate there is still a long long way to go. Therefore, cracking currently used RSA encryption should be impossible for at least twenty years.
Note that engineering approaches such as quantum computers must spend a long time to evolve to the level capable of cracking cryptographic algorithms, which incurs only a very limited threat to security. This is because such kind of threat is predictable, and hence people would have enough time to upgrade to more powerful quantum-resistant schemes. Eventually, when the quantum computer comes true, RSA should already have been abandoned for a long time.
Comparing to the engineering progress of quantum computers, mathematicians, including cryptologists and theoretical computer scientists, could be more dangerous to the entire blockchain industry. Because there is a chance that a theoretical result suddenly breaks the in-use cryptographic schemes.
Conflux is a State-of-the-Art public blockchain system that can achieve high TPS without sacrificing decentralization or safety. By delicately combining its unique and advanced algorithm with a novel structure — — Tree Graph (TG), Conflux makes consensus no longer a performance bottleneck, thereupon solves a series of problems in the industrialization of public chains. Currently, in its first stage, Conflux adopts PoW (Proof of Work) mechanism as the basis of its consensus.
Join the Revolution here:
Youtube: Conflux Chain
Twitter: https://twitter.com/ConfluxChain
Telegram: http://t.me/Conflux_English
