Post-Quantum Cryptography

A blockchain perspective

Quantum computing will have a big impact on our lives: drug development, traffic optimization, artificial intelligence or weather forecasting will benefit from the power increase that a quantum computer will bring with it; but with great power comes great responsibility, and the impact of quantum computing in cybersecurity may be disastrous unless current cryptographic techniques are pushed forward. This article will cover some of these aspects from a very informal point of view: the impact on blockchain technology, and some of the new techniques developed and current proposals for a prospective quantum-resistant blockchain. Enjoy!

Asymmetric cryptography

Most of the current communications between Alice and Bob go through encryption processes that aim to make them incomprehensible to third parties. Bob and Alice can choose between two philosophies when encrypting their communications, either using a shared secret key (symmetric cryptography) or using a pair of keys, where one of them is secret and the other public (asymmetric cryptography).

Asymmetric cryptography embraces mechanisms such as the Diffie-Hellman key exchange, or the ElGamal, RSA and the Paillier cryptosystems, to name a few. The security of these techniques rely on the computational complexity of the two mathematical problems below:

1. The prime factorization problem where, given an integer a, the task is to find two prime numbers b and c such that a = b · c.
2. The discrete logarithm problem where, given a pair of elements, a and b, in a cyclic group G, the task is finding an element c in G such that a = b^c.

These two problems, when implemented correctly, are practically infeasible for current computers, and this is the fact that allows us to assure that the associated cryptosystem is secure, at least against brute force attacks.

The role played by asymmetric cryptography in blockchain technology is central as it’s the main ingredient in digital signatures, where the hash of a transaction from Alice to Bob is encrypted using Alices’ private key together with the plain transaction. After receiving it, Bob will verify the transaction received using Alice’s public key and comparing hashes.

Quantum computing

Quantum computing has been an active research field since its first appearance in the ’80s when physicists like Richard Feynman or mathematicians like Yuri Manin proposed using quantum-mechanical properties in computer science.

By that time, people were happy and enthusiastic with asymmetric cryptography… at least until the release of the Kraken. In January 1996, Peter Shor published Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, where a concrete proposal for a quantum algorithm able to solve, in super-polynomial time (i.e., feasible time), the two main problems providing security in most of the current communications. The impact of Shor’s algorithm is particularly important in blockchain technology, as it might be used to break the ECDSA algorithm, which is used by Bitcoin, Ethereum or Zcash, among others.

If Shor’s algorithm wasn’t enough, Lov Grover published in 1998 A framework for fast quantum mechanical algorithms. The main consequence of Grover’s algorithm is the possibility to create quantum algorithms able to find preimages of hash functions, another problem computationally complex for a classic computer. Grover’s algorithm represents a threat as it might be used against hash functions such as SHA256, Keccak or RIPEMD160, and this turns into major vulnerabilities in Bitcoin, Ethereum, Litecoin, or Zcash. Furthermore, the algorithm might be used to find hash collisions, which allows replacing blocks in a blockchain. The good news with Grover’s algorithm is that doubling the length of involved keys or message digests should be enough for current hash functions to become quantum-resistant.

The key factor that makes a classical computer bite the dust in some situations when compared to a quantum computer is superposition, which essentially is the ability of a quantum system to be in multiple states (up and down, inside and outside, etc) at the same time. For example, for a given function f, a quantum computer allows us to compute f(x) for a superposition of all values of x at the same time.

Potential quantum attacks to the blockchain may affect either the PoW stage or the digital signatures:

1. In the first case, Grover’s algorithm could be used to perform the hashcash PoW, the one used in Bitcoin for instance, with quadratically fewer hashes than required by a classic computer. This fact implies that an attacker with a quantum computer could modify a block and recreate the blockchain much faster departing from the “new block”. This has several implications: on one hand, malicious miners would obtain more rewards than honest miners, and on the other malicious miners could take control of the blockchain much faster, as the ability to create new blocks increases.
2. In the second case, Shor’s algorithm may be used against the ECDSA digital signature algorithm. A quantum attacker would be able to obtain the private key of a user given its public key. Whilst this attack doesn’t affect blockchain’s structure in terms of linked hashes, it opens the door to forge the contents in a block, indeed: the inclusion of an unprocessed transaction in a block once it’s broadcasted is not immediate; if a quantum computer can obtain the secret key, the attacker may use it to create a new transaction redirecting the payment to its address. Without the intention of being pessimistic, observe that an attack against a processed transaction may be performed using Grover’s algorithm, and thus falls into (1) above.

Post-quantum cryptography

To overcome the attacks described above and to be prepared for forthcoming quantum attacks, it’s important to find new mathematical tools leading to stronger cryptographic algorithms. The basic idea is that, in this new framework, number theory is no longer enough, and a more complex mathematical structure is required. This point of view leads to exploring mathematical fields such as geometric number theory or algebraic geometry and a new research area: post-quantum cryptography.

During the last few years, a lot of research effort has been poured into exploring new mathematical techniques for the definition of quantum-resistant cryptographic algorithms. In this direction, it is important to highlight projects such as NIST’s competition to find new post-quantum standards or European projects such as PQCRYPTO and PROMETHEUS.

The main techniques explored for the definition of new quantum-resistant cryptographic algorithms are lattices, isogenies of supersingular elliptic curves, codes, multivariate polynomials, and hash functions.

Although each one of the latter is interesting and rich in concepts and ideas, on this occasion we are focusing on lattices and hashes.

Very roughly speaking, a lattice is a repeating arrangement of points in the space (although we do not assume any restraint on the dimension). Their applications in cryptography embrace all the primitives: encryption/decryption (such as NTRUEncrypt), digital signatures (Falcon or Dilithium for instance) and key exchanges (Frodo or NewHope).

The security of these methods relies on several problems. Let Zq denote the integers modulo a prime q:

1. The closest vector problem: in this problem, given a vector, one is required to find the closest non-trivial vector in the lattice.
2. The shortest vector problem: here one is required to find the shortest non-trivial vector in the lattice.
3. The short integer solution problem: in this problem given m vectors (of dimension n) with elements in Zq, arranged as the columns of a matrix A, one must find a small enough solution for A · z = 0 (mod q).
4. The learning with errors: let us consider a secret, n-dimensional, vector S with elements in Zq, a public (m,n)-matrix A with elements in Zq, and a noise, m-dimensional, vector E with elements in Zq. Given B = A · S + E, the task is to find S.

Although lattice-based algorithms need to improve in terms of key sizes, they represent a very promising solution in post-quantum cryptography. Recent research papers show that some proposals are fast and even comparable to current asymmetric algorithms such as RSA when tested on classic computers. This shows that lattice-based algorithms could be suitable for blockchain technology. Concerning digital signatures proposals like Dilithium and qTesla are among the fastest algorithms, even when compared with the current solutions. For key exchange, we point out NewHope, which has been integrated into Google’s fork of OpenSSL and is being considered for integration in the Tor network.

It’s time for hashing. A hash function outputs a digest of fixed length, no matter the length of the input. It must satisfy two properties:

1. To be collision-resistant, which means that given two different inputs, it must be computationally infeasible to find a common output.
2. To be preimage resistant, which means that given the output of the hash function, it must be computationally infeasible to find a valid input.

The security of hash-based schemes relies on the security of the underlying hash function, rather than on the complexity of the underlying mathematical problem (as happens with lattice-based algorithms). It is important to keep in mind that most of the hash functions involved in blockchain technology, such as SHA256 in the cases of Bitcoin and Ethereum, are assumed to be quantum-resistant, as Grover’s algorithm just reduces the number of searches from 2^256 to 2^128.

Hash-based digital signature solutions need to improve in terms of general performance to be suitable for the blockchain. In this direction, some researchers suggest new faster algorithms which are inspired by extended Merkle trees that seem to be practical for blockchain.

Post-quantum cryptography in blockchain

One can find several initiatives exploring quantum resistance in the blockchain.

Some proposals aim at approaches requiring memory-intensive PoW like Equihash, which is being used by Zcash, or cuckoo cycles, based on finding constant sized subgraphs in random graphs.

Bitcoin Post-Quantum, a hard fork of Bitcoin that uses the Extended Merkle Signature Scheme (XMSS) combined with Winternitz One-Time Signatures. In future updates, this proposal is planning to implement zero-knowledge proof primitives like ZK-starks to achieve privacy.

Another proposal exploring the use of hash-based algorithms is Corda, which is experimenting with SPHINCS.

There are other proposals, such as Abel, which are using algorithms based on lattices to provide recipient, origin and value hiding. Some researchers are exploring replacing Bitcoin’s digital signature with algorithms such as TESLA#, which relies upon a polynomial flavoured version of the learning with errors problem.

To be fully applicable in the blockchain environment, post-quantum resistant cryptography needs to tackle the following aspects:

1. Small key sizes: a blockchain needs to make use of small key pairs to reduce the required storage space. Furthermore, small keys involve less complex computational operations when managing them.
2. Fast execution and low computational complexity: regarding computational complexity, post-quantum schemes need to be as fast, and less computationally demanding, as possible to allow a blockchain to process a large number of transactions per second.
3. Small signature and hash length: a blockchain essentially stores data transactions, including user signatures and hashes. Therefore, if the signature or hash lengths increase, the size of the blockchain will increase as well.

Several techniques could be explored for their application in a blockchain setting: aggregate signatures allow generating a combined signature obtained from several of them; group signatures give a member of a group permission to anonymously sign on behalf of its group; ring signatures allow for specifying a set of possible signers without revealing who of them produced a signature. Furthermore, lattices, besides providing interesting potential solutions for the blockchain, also open the door to include homomorphic encryption in the blockchain, which would allow third parties to process encrypted transactions without revealing any secret data.

As a final remark it is important to point out the fact that, despite the big initiatives, such as the NIST project, no major projects are focusing exclusively on providing the blockchain with quantum resistance.