Is blockchain fit for the post-quantum future?

Cryptography is one of the cornerstones of all blockchain infrastructures. Hashes link blocks together and public-private key cryptography helps secure data and verify transactions. A major advantage of blockchain is that its cryptography man es it virtually untamperable, with changes in the crypto being virtually impossible.
 

This isn’t necessarily due to some magical component of the cryptography though. The reason why this cryptography is so secure is because in most blockchain implementations every node has a copy of all the blocks and a massive amount of computing power would be needed to hack it, computing power no one currently has. If the tech industry is known for anything though, it’s rapid innovation. Every year we see improvements and there is a threat on the horizon to not only the cryptography securing blockchain, but also all cryptographically secure digital information: quantum computing. Blockchain’s future is presently uncertain, and for businesses interested in integrating this technology it is crucial to be aware of whether or not it is future proof - and how long that future needs to last. In this article we’ll be discussing how quantum computers threaten blockchain, as well as looking at potential solutions that could improve blockchain’s resilience.

Threats to blockchain’s future: quantum computing

Two fundamental features of blockchain are public-private key pair encryption (asymmetric cryptography) and black box hash algorithms. There are differences in the ways these two are vulnerable to quantum computing though. Let’s take a look at how and why for each.

Asymmetric 

Asymmetric cryptography or public-private key cryptography is used in blockchain’s public-private key address pairing. Simply put this is where two different keys are used to encrypt and decrypt data. On a blockchain a private key is used to encrypt, the public key is used to decrypt and verify identity. This works in reverse as well.

The way that these key pairings are created is that a public key is generated when a private key has Elliptic Curve Cryptography applied to it. Currently it would take an impossible amount of computing power to determine the input to the an elliptic curve algorithm, as it generates keys by producing the product of two large prime numbers. This is relatively simple to do, but attempting to find the factors of two large prime numbers is futile with present technology.

Shor’s algorithm though, is a quantum integer factorization algorithm. Given an integer input it finds the prime factors of that number. If quantum computers continue to advance, it will only be a matter of time before they can make quick work of the asymmetric cryptography used on blockchain, and also elsewhere. This is of course a major security risk to a core component of blockchain infrastructure.

Black box algorithms

Black box algorithms are used in blockchain to hide information and link blocks together. They are algorithms where information can be sent in, but there’s no way to to decrypt the output. The current zeitgeist is that hashing algorithms such as SHA256 are uncrackable. This type of cryptography is also not vulnerable to Shor’s algorithm. 

There is however a quantum algorithm that can find, with high probability, the unique input of a black box function (such as SHA256) given a certain output. It’s called Grover’s algorithm, and the reason current hashing is safe from this is because, as with Shor’s algorithm, today’s computers do not have the power to run it.

Potential solutions

Asymmetric and symmetric cryptography are not equally vulnerable to quantum computing. Black box functions can be made secure by simply doubling the hash length, making it too computationally expensive for even projected quantum computers. However asymmetric cryptography security is at risk, and work is already being done by the cyber security community to develop quantum-resistant methods. The National Institute of Standards and Technology (NIST) is already searching for post-quantum algorithms and published the first round of proposals in early 2018. They will continue to analyze and begin drafting standards over the next couple of years. The National Security Agency (NSA) is also aware of the threat quantum computers pose, and has announced plans to move their standards to quantum-resistant cryptography. While this is still experimental, the threat is not being entirely neglected.

In universities lots of research is being conducted around this subject. Kitkenko et al. for instance propose a possible solution and report an experimental realization of a quantum-safe blockchain platform that utilizes quantum key distribution across an urban fiber network for information-theoretically secure authentication. These results were able to address questions about realizability and scalability of quantum-safe blockchains.

If solid post-quantum cryptography options become more developed, it will be possible to integrate them into blockchain. That is the good news. The bad news remains, that past blocks are immutable. So if blocks generated in the past are signed using algorithms that have been broken, that distributed content will remain unalterable too. No backward compatibility, no backward patching with quantum stage algorithms.

For the time being there are other ways to reduce the risk, such as using blockchain address only once (a practice already recommended on Bitcoin). Ideally though the strength of the cryptography will rise with the strength of the computers that threaten it.

Conclusion

There is much excitement and optimism around the future of blockchain at the moment. Experimentation and creative destruction are at their peak. Other technology is growing too however, and one of these is a definite threat to not only blockchain, but to cryptography as a whole.

Quantum computers are not nearly as powerful as they have the potential to be though. Presently we are limited and struggle to turn this theory into practice. For the time being blockchain is safe from this threat, but it is good to keep an eye on the future and understand that even this revolutionary tool is not entirely safe in the ever changing world of tech.