Quantum resistant blockchains explained.
The fact that whatever is registered on a blockchain can’t be tampered with is one of the great reasons for the success of blockchain. But what if the rules change and there is a possibility to break one of the defense lines of blockchain? Eventually, quantum computers will be able to break some of the mathematics that secure blockchain. Looking ahead, awareness is growing in the blockchain ecosystem that quantum computers might cause the need for some changes in the cryptography that is used by blockchains to prevent hackers from forging transactions.
How would quantum computers pose a threat to blockchain? First, let’s get a misconception out of the way. When talking about the risk quantum computers could pose for blockchain, some people think about the risk of quantum computers out-hashing classical computers. This, however, is not expected to pose a real threat when the time comes.
This paper explains why: https://arxiv.org/pdf/1710.10377.pdf “In this section, we investigate the advantage a quantum computer would have in performing the hashcash PoW used by Bitcoin. Our findings can be summarized as follows: Using Grover search, a quantum computer can perform the hashcash PoW by performing quadratically fewer hashes than is needed by a classical computer. However, the extreme speed of current specialized ASIC hardware for performing the hashcash PoW, coupled with much slower projected gate speeds for current quantum architectures, essentially negates this quadratic speedup, at the current difficulty level, giving quantum computers no advantage. Future improvements to quantum technology allowing gate speeds up to 100GHz could allow quantum computers to solve the PoW about 100 times faster than current technology.
However, such a development is unlikely in the next decade, at which point classical hardware may be much faster, and quantum technology might be so widespread that no single quantum enabled agent could dominate the PoW problem.”
The real point of vulnerability is this: attacks on signatures wherein the private key is derived from the public key. That means that if someone has your public key, they can also calculate your private key, which is unthinkable using even today’s most powerful classical computers. But in the days of quantum computers, the public-private keypair will be the weak link. Quantum computers have the potential to perform specific kinds of calculations significantly faster than any normal computer. Besides that, quantum computers can run algorithms that take fewer steps to get to an outcome, taking advantage of quantum phenomena like quantum entanglement and quantum superposition. So quantum computers can run these certain algorithms that could be used to make calculations that can crack cryptography used today. See for reference here and here.
Most blockchains use Elliptic Curve Digital Signature Algorithm (ECDSA) cryptography. Using a quantum computer, Shor’s algorithm can be used to break ECDSA. (See for reference: here and for the pdf version here.) In short: one could derive the private key from the public key. So again: if someone has your public key (and a quantum computer), then he has your private key and can create a transaction and empty your wallet.
RSA has the same vulnerability while RSA will need a stronger quantum computer to be broken than ECDSA.
At this point in time, it is already possible to run Shor’s algorithm on a quantum computer. However, the amount of qubits available right now makes its application limited. Some would even argue that the quantum computers that have been developed so far do not deserve to be named actual quantum computers due to the infant state of it’s development. It might not surprise you, but IBM doesn’t share that opinion and has launched it’s first commercial quantum computer. Promotional video here and article here. Anyway, however you would label the device, Shor’s has been proven to work on a quantum device and we have exited the era of pure theory and entered the era of practical applications:
- 2001: First execution of Shor’s algorithm at IBM’s Almaden Research Center and Stanford University. The paper here: (Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance Lieven M. K. Vandersypen)
- 2009: Researchers at University of Bristol demonstrate Shor’s algorithm on a silicon photonic chip. And the paper here.
- IBM on Shor’s here
So far Shor’s algorithm has the most potential, but new algorithms might appear which are more efficient. Algorithms are another area of development that makes progress and pushes quantum computer progress forward. To give an example: a new algorithm called Variational Quantum Factoring is being developed and looks quite promising. “ The advantage of this new approach is that it is much less sensitive to error, does not require massive error correction, and consumes far fewer resources than would be needed with Shor’s algorithm. As such, it may be more amenable for use with the current NISQ (Noisy Intermediate Scale Quantum) computers that will be available in the near and medium term.” See for more information here. It is however still in development, and only works for 18 binary bits at the time of this writing, but it shows new developments that could mean that, rather than a speedup in quantum computing development to be posing the most imminent threat to RSA and ECDSA, instead a speedup in the mathematical developments could be even more consequential. For a paper on VQF, see here.
It all comes down to this: when your public key is made public, which is always necessary to make transactions, you are at some point in the future vulnerable to quantum attacks. (This also goes for BTC and other blockchains, that use the hash of the public key as an address instead of the full original public key, but more on that in the following parts of the series.) However, if you would have keypairs based on post-quantum cryptography, you would not have to worry about this issue since in that case not even a quantum computer could derive your private key from your public key.
The conclusion is that future blockchains should be quantum resistant, using post-quantum cryptography. It’s very important to realize that post quantum cryptography is not just adding some extra characters to standard signature schemes. It’s the mathematical concept that makes a signature scheme quantum resistant. To become quantum resistant, the algorithm needs to be changed. “The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be solved on a sufficiently powerful quantum computer running Shor’s algorithm. Even though current, publicly known, experimental quantum computers lack power to break any real cryptographic algorithm, many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat.” For more about post-quantum cryptography, also known as quantum resistant cryptography, here.
You can continue reading here: part 3B expectations in the field of development.