How DLTs Could Withstand The Advent Of Quantum Computers?
Quantum computers are being developed at a fast pace as several resources are committed to it.
There have been some warnings to the blockchain community about how quantum computers will be able to break public-key cryptography and leave blockchain-based systems obsolete. But let’s not forget that this is not a blockchain’s exclusive problem, as today, practically all digital systems rely on the security of current cryptography systems.
How Current Systems Are Vulnerable To Quantum Computers?
Today, most digital systems use cryptographic systems with security that rely on the difficulty to solve the integer factorization problem, the discrete logarithm problem, and the elliptic-curve discrete logarithm problem. These problems can be solved by sufficiently powerful Quantum Computers through the use of Shor’s algorithm. It’s not expected that quantum computers could have the power to break classical cryptography with these algorithms in less than 5 years, but there is no assurance when we talk about the speed of technological evolution. For example, there was leaked recently news that Google’s quantum computer would have obtained what is called Quantum supremacy, which means the ability of a quantum computer to solve problems that a classical could not. This capability, however, is constrained for now to the sampling of pseudo-random circuits and is still far from being able to implement the Shor’s algorithm, for which, progress in the Quantum error correction (QEC) technique would be required. This technique reduces known issues as quantum decoherence and quantum noise that become more relevant as the quantum computer capacity increase.
To prevent this quantum black swan to all our digital infrastructure, two alternatives have been devised.
The first one is the direct use of Quantum devices with symmetric key cryptography (Both parties share a common secret). This scheme is called Quantum Key Distribution (QKD) and is a longer-term solution since it requires a complete update of the existing infrastructure and the maturation of quantum technology with the added costs that this represents, so at the moment it is not considered viable for decentralized public networks.
For the second one, the cryptographic community has been working in a new family of algorithms that could withstand quantum computers. This branch of algorithms belongs to what is called Post-Quantum cryptography, which is the focus of this article.
How Post-Quantum Cryptography Can Overcome This?
Post-Quantum cryptography relies on different mathematical problems of which no practical solutions are known even with the use of Quantum computers. Depending on the problems and mechanisms on which they are based, they have been classified in several families: Lattice-based cryptography, Multivariate cryptography, Hash-based cryptography, Code-based cryptography, Supersingular elliptic curve isogeny, and symmetric key quantum resistance.
What Is The Status Of Post-Quantum Cryptography? Can It Be Used Today?
To achieve standardization and acceptance of the cryptography community a cryptographic system must go a long way. There are institutions dedicated to vetting these technologies and creating standards. For instance, The National Institute of Standards and Technology (NIST), a US-based agency, is in the process of selecting one or more of post-quantum algorithms through a public competition-like process to create cryptographic standards which can withstand the advent of quantum computers. Currently, 26 candidate algorithms have been accepted in the second round of the competition (1).
It is estimated that this process still has a long time to finish and could be extended even after 2024. So, right now, it’s still not safe to implement cryptography that uses a single post-quantum algorithm because is not proved that they are at least as secure as the standards ones we currently use. The practical alternative to begin implementing long-term quantum-safe algorithms is in the use of Hybrid cryptography.
Hybrid cryptography consists of the combination of several cryptographic mechanisms that grant the security of the safest of them. This is a new field of research and only a few proposals for post-quantum hybrid cryptography protocols are public.
How Can I Access Post-Quantum Algorithms?
Most post-quantum mechanisms have their own implementations. There are also some libraries that contain several implementations like libpqcrypto and OQS(Open Quantum Safe) project. Currently, OQS has consolidated and implemented most of the latest version of post-quantum cryptographic systems in C and has created wrappers for them in python, C# and probably soon java (external go implementations also exists).
How Can DLTs Incorporate Post-Quantum Cryptography?
Due to the different DLT’s architectures, designs and ideologies there isn’t a one size fits all solution. For example, it is expected that in Ethereum 2.0 account abstraction will be implemented and this will allow delegating the signature verification to a smart contract, which would allow different types of signature algorithms implementations. Other blockchains have been designed to use post-quantum signatures as XMSS.
Most blockchains have targeted the family of the hash-based signatures as an alternative to classical cryptography. The main reasons behind this election are key and signature size. Old hash-based signatures have had the problem of losing security every time the signature is used, for this reason, they were called one-time signatures. For example, IOTA uses Winternitz one-time signature (WOTS) (2) and has mitigated this vulnerability by restricting the address reuse at the wallet level but not at the protocol level.
New stateless hash-based signatures such as SPHINCS+ have been proposed as suitable post-quantum replacements for classical signatures. Also, a hash-based signature scheme XNYSS (eXtended Naor-Yung Signature Scheme) has been proposed as a replacement in existing blockchains such as Bitcoin (3). There are new blockchains/DLTs such as Quantum Resistant Ledger(QRL) based on XMSS which is already working and proposals such as Blockchained Post-Quantum Signatures (BPQS) mechanism by R3, which also relies on hash-based signatures but could extend them to an unlimited number of operations.
A Path To The Post-Quantum Era
In preparation for the advent of Quantum computers, we at everis Blockchain Digital Lab are continuously researching the best approaches to implement post-quantum algorithm solutions in our products. Soon, we will publish an example showing the use and testing of these algorithms.
Author: Rodny Palomino — Researcher at Digital Lab Blockchain/DLT Perú in everis
Editor: Juan José Miranda — Director at Digital Lab Blockchain/DLT Perú in everis
Bibliography
1. “Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process”, Csrc.nist.gov. January 2017.
2. https://docs.iota.org/docs/dev-essentials/0.1/concepts/addresses-and-signatures
3. Post-quantum blockchain using one-time signature chains, Wouter van der Linde, August 27, 2018
4. Blockchained Post-quantum Signatures, Konstantinos Chalkias, James Brown, Mike Hearn, Tommy Lillehagen, Igor Nitto, and Thomas Schroeter, R3