I'm writing a series about blockchain tech and possible future security risks. This is the third part of the series introducing Quantum resistant blockchains.

Part 1 and part 2 will give you usefull basic blockchain knowledge that is not explained in this part.

Part 1 here

Part 2 here

Quantum resistant blockchains explained.

- How would quantum computers pose a threat to blockchain?

- Expectations in the field of quantum computer development.

- Quantum resistant blockchains

- Why is it easier to change cryptography for centralized systems such as banks and websites than for blockchain?

- Conclusion

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. 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. So 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. https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#Quantum_computing_attacks and https://eprint.iacr.org/2017/598.pdf

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: https://arxiv.org/abs/quant-ph/0301141 and pdf: https://arxiv.org/pdf/quant-ph/0301141.pdf ) Meaning: they can derive the private key from the public key. So if they got your public key (and a quantum computer), then they got your private key and they 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. But it has been proven to work, 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, https://arxiv.org/abs/quant-ph/0112176 )
• 2009: Researchers at University of Bristol demonstrate Shor's algorithm on a silicon photonic chip: http://science.sciencemag.org/content/325/5945/1221also the paper here: https://arxiv.org/abs/0911.1242
• IBM on Shor’s: https://quantumexperience.ng.bluemix.net/proxy/tutorial/full-user-guide/004-Quantum_Algorithms/110-Shor's_algorithm.html?highlight=shor

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. A new algorithm called Variational Quantum Factoring is being developed and it 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." https://quantumcomputingreport.com/news/zapata-develops-potential-alternative-to-shors-factoring-algorithm-for-nisq-quantum-computers/

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 posing the most imminent threat to RSA and ECDSA, a speedup in the mathematical developments could be even more consequential. More info on VQF here: https://arxiv.org/abs/1808.08927

It all comes down to this: when your public key is visible, which is always necessary to make transactions, you are at some point in the future vulnerable for quantum attacks. (This also goes for BTC, which uses the hash of the public key as an address, but more on that in the following articles.) If you would have keypairs based on post quantum cryptography, you would not have to worry about that 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 it quantum resistant. “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 easily solved on a sufficiently powerful quantum computer running Shor's algorithm. Even though current, publicly known, experimental quantum computers lack processing power to break any real cryptographic algorithm, many cryptographers are designing new algorithms to prepare for a time when quantum computing becomes a threat.” https://en.wikipedia.org/wiki/Post-quantum_cryptography

Expectations in the field of quantum computer development.

To give you an idea what the expectations of quantum computer development are in the field:

• https://www.nextbigfuture.com/2018/06/intel-superconducting-quantum-technology-could-push-to-1000-qubits-by-2023-and-silicon-spin-qubits-to-1-million-qubits-by-2028.html "It should be about 5 years to 1000 qubit chips with superconducting technology. It should be about 10 years to million qubit chips."
• https://www.technologyreview.com/s/603495/10-breakthrough-technologies-2017-practical-quantum-computers/ "And a million-physical-qubit system, whose general computing applications are still difficult to even fathom? It’s conceivable, says Neven, “on the inside of 10 years.” " (That is Harmut Neven of Google’s quantum computing effort)
• https://www.research.ibm.com/5-in-5/quantum-computing/ IBM believes quantum computers will be mainstream in 5 years. (Meaning outside of research labs, but not necessarily in livingrooms of the average Joe. And no amount of qubits mentioned though)
• https://www.barrons.com/articles/microsoft-we-have-the-qubits-you-want-1519434417 “Five years from now, we will have a commercial quantum computer,” says Holmdahl.
• And those are just the commercial companies. The pentagon sees quantum computing as the next arms race. China is about to pump $10 Billion in a research centre. They won't be open about their developments as Google etc. https://www.nextgov.com/emerging-tech/2018/07/pentagon-seeks-edge-quantum-computing/149718/ It’s not a bad idea to start looking for solutions and new opportunities in blockchain.
  • This paper estimates ECDSA being at risk as soon as 2027. https://arxiv.org/pdf/1710.10377.pdf

When will ECDSA be at risk? Estimates are only estimates, there are several to be found so it's hard to really tell.

The report on this subject from the National Academy of Sciences doesn't make an estimate on when the risk would occur. They acknowledge this is quite impossible due to the fact there are a lot of unknowns and due to the fact that you have to base any findings only on publicly available information, obviously excluding any non available advancements from private companies and national efforts. The report does have an advice though:

"Even if a quantum computer that can decrypt current cryptographic ciphers is more than a decade off, the hazard of such a machine is high enough—and the time frame for transitioning to a new security protocol is sufficiently long and uncertain—that prioritization of the development, standardization, and deployment of post-quantum cryptography is critical for minimizing the chance of a potential security and privacy disaster."

Quantum resistant blockchains

“Quantum resistant” is only used to describe networks and cryptography that are secure against any attack by a quantum computer of any size in the sense that there is no algorithm known that makes it possible for a quantum computer to break the applied cryptography and thus that system.

Also, to determine if a project is fully quantum resistant, you would need to take in account not only how a separate element that is implemented in that blockchain is quantum resistant, but also the way it is implemented. As with any type of security check, there should be no backdoors, in which case your blockchain would be just a cardboard box with bulletproof glass windows. Sounds obvious, but since this is kind of new territory, there are still some misconceptions. What is considered safe now, might not be safe in the age of quantum computers. I will address some of these in the following chapters, but first I will elaborate a bit about the special vulnerability of blockchain compared to centralized systems.

Why is it easier to change cryptography for centralized systems such as banks and websites than for blockchain?

Developers of a centralized system can decide from one day to the other that they make changes and update the system without the need for consensus from the nodes. They are in charge, and they can dictate the future of the system. But a decentralized blockchain will need to reach consensus amongst the nodes to update. Meaning that the majority of the nodes will need to upgrade and thus force the blockchain to only have the new signatures to be valid. We can’t have the old signature scheme to be valid besides the new quantum resistant signature scheme. Because that would mean that the blockchain would still allow the use of vulnerable, old public- and private keys and thus the old vulnerable signatures for transactions. So at least the majority of the nodes need to upgrade to make sure that blocks which are constructed using the old rules and thus the old vulnerable signature scheme, are rejected by the network. This will eventually result in a fully upgraded network which only accepts the new post quantum signature scheme in transactions. So, consensus is needed. The most well-known example of how that can be a slow process is Bitcoin’s need to scale. Even though everybody agrees on the need for a certain result, reaching consensus amongst the community on how to get to that result is a slow and political process. Going quantum resistant will be no different, and since it will cause lesser performance due to bigger signatures and it will need hardware upgrades quite likely it will be postponed rather than be done fast and smooth due to lack of consensus. And because there are several quantum resistant signature schemes to choose from, agreement an automatic given. The discussion will be which one to use, and how and when to implement it. The need for consensus is exclusively a problem decentralized systems like blockchain will face.

Another issue for decentralized systems that change their signature scheme, is that users of decentralized blockchains will have to manually transfer/ migrate their coins/ tokens to a quantum safe address and that way decouple their old private key and activate a new quantum resistant private key that is part of an upgraded quantum resistant network. Users of centralized networks, on the other hand, do not need to do much, since it would be taken care of by their centralized managed system. As you know, for example, if you forget your password of your online bank account, or some website, they can always send you a link, or secret question, or in the worst case they can send you mail by post to your house address and you would be back in business. With the decentralized systems, there is no centralized entity who has your data. It is you who has this data, and only you. So in the centralized system there is a central entity who has access to all the data including all the private accessing data, and therefore this entity can pull all the strings. It can all be done behind your user interface, and you probably wouldn’t notice a thing.

And a third issue will be the lost addresses. Since no one but you has access to your funds, your funds will become inaccessible once you lose your private key. From that point, an address is lost, and the funds on that address can never be moved. So after an upgrade, those funds will never be moved to a quantum resistant address, and thus will always be vulnerable to a quantum hack.

To summarize: banks and websites are centralized systems, they will face challenges, but decentralized systems like blockchain will face some extra challenges that won't apply for centralized systems.

• Updating the signature scheme will need consensus in the sense that all nodes need to update after implementation of a quantum resistant signature scheme.
• Users of blockchain will personally need to move their funds from old addresses to new quantum resistant addresses. You won't need to move your bank funds.
• Lost addresses where people lost access to their funds will never be moved and stay vulnerable to quantum hacks. Blockchain doesn't know their users, can't communicate with them and won't be able to distinguish coins on lost addresses from coins from users who still have access but somehow have not migrated their coins after a quantum resistant update. So burning lost coins will be legally a big issue.

All issues specific for blockchain and not for banks or websites or any other centralized system.

Conclusion

Bitcoin and all currently running traditional cryptocurrencies are not excluded from this problem. In fact, it will be central to ensuring their continued existence over the coming decades. All cryptocurrencies will need to change their signature schemes in the future. This won’t be an easy transfer. There are some huge challenges to overcome. I will get to this in the next few chapters.