Introduction

Recently, there has been a surge of news about revolutionary breakthroughs in quantum computing that could significantly impact our understanding of the resilience of cryptographic algorithms. This imposes certain limitations on the development of distributed database technologies based on blockchains—chains of blocks linked by hash sums. But do these advances pose a real threat to the blockchain of the future? Should you rush to cash out your bitcoins and hide them under your grandma’s mattress at the first sign of a working quantum computer? Most likely not, and here’s why.

Table of Contents

• Introduction
• Part 1. The Present
  • Why the Post-Quantum Era May Not Arrive (At Least in the Near Future)
  • Security of Existing Cryptographic Algorithms
• Part 2. The Future
  • Requirements for a Post-Quantum Blockchain
  • Algorithms to Counter Post-Quantum Attacks
  • Post-Quantum Encryption Algorithms
  • Post-Quantum Signature Algorithms
• Conclusion

Part 1. The Present

Why the Post-Quantum Era May Not Arrive (At Least in the Near Future)

As appealing as the idea of inventing computing technology that far surpasses current capabilities may be, there are many obstacles to building a quantum computer. Quantum operations involve several logical steps: initializing qubits (the quantum analogs of “zeros and ones”), entangling them, isolating these systems from external interference, and reading the results. Each step presents its own challenges, making it difficult to achieve the required precision.

One major issue is the difficulty of producing uniform and stable qubits. Quantum computers operate on probabilistic principles, and their results are probability distributions of possible answers. To avoid random data loss, it’s crucial to eliminate any external noise or observation (that’s how quantum mechanics works). Stable qubit operation requires maintaining an environment temperature of about 20 mK, which is hard to achieve even in labs. Scientists use superfluid liquids for such cooling. Recently, researchers at Duke University in the U.S. announced they had created more noise-resistant quantum systems, successfully initializing qubits 99.4% of the time, compared to the expected 98.9%.

Despite progress, unresolved issues remain, such as high production costs, the need for highly qualified personnel, and the unsuitability of quantum computers for everyday tasks.

Security of Existing Cryptographic Algorithms

Let’s examine how resistant current blockchain security algorithms are to cryptanalytic attacks, as understanding the present is key to discussing the future of cryptosystems.

The resilience of public-key cryptosystems to classical computer attacks is traditionally measured by the “bits-of-security level”—the effort required for a brute-force attack. For example, a 1024-bit asymmetric cryptosystem is as hard to break as brute-forcing a 1024-bit key. For reference, the cost of breaking modern 80-bit cryptosystems on classical computers ranges from tens of thousands to hundreds of millions of dollars. 112-bit systems are considered secure against classical attacks for the next 30-40 years. However, researchers have found that 160-bit elliptic curves can be broken by a 1,000-qubit quantum computer, and 1024-bit RSA by about 2,000 qubits. This threatens systems based on integer factorization (RSA), elliptic curves (ECDSA, ECDH), and discrete logarithms, all of which can be efficiently solved by Shor’s quantum algorithm.

As for hash functions, unlike public-key cryptosystems, traditional hash functions are considered resistant to quantum attacks, since finding a hash preimage is an NP-hard problem. However, quantum attacks using Shor’s algorithm can still affect them: if a blockchain’s hash function is compromised, someone with a powerful enough quantum computer could forge digital signatures, track blockchain users, and steal digital assets. Grover’s algorithm can also be used to find hash collisions, replace groups of blocks, or speed up mining, undermining the integrity of the blockchain.

Part 2. The Future

Requirements for a Post-Quantum Blockchain

At first glance, simply increasing key and hash sizes might seem like enough to restore security, but this would drastically reduce performance. To maintain speed and make blockchains resistant to new types of attacks, post-quantum cryptosystems should meet the following requirements:

• Small key sizes: Devices interacting with the blockchain should ideally use small public and private keys to minimize storage needs and simplify computations. This is especially important for IoT devices with limited resources.
• Small signature and hash lengths: Since blockchains store transaction data, including user signatures and hashes, increasing their size also increases the blockchain’s size.
• Fast execution: Post-quantum schemes should be as fast as possible to allow high transaction throughput. Fast execution is also linked to low computational complexity, which is crucial for resource-constrained devices.
• Low computational complexity: While related to fast execution, low complexity ensures that even limited hardware can participate in blockchain transactions.
• Low energy consumption: Some blockchains, like Bitcoin, are energy-intensive mainly due to their consensus protocols. Other factors include hardware used, number of transactions, and security schemes.

Algorithms to Counter Post-Quantum Attacks

Let’s look at current solutions for future-proofing cryptosystems. Spoiler: there’s no perfect algorithm that meets all the above criteria yet, but research is ongoing! We’ll analyze how to secure encryption/decryption and digital signature mechanisms using various algorithm types. Improvements to hash functions are not covered here, as quantum computing’s impact on their security is less significant. Only some existing algorithms are listed; a full review would require a separate article.

Post-Quantum Encryption Algorithms

1. Code-Based Cryptosystems: These use error-correcting codes to generate private keys. For example, the McEliece system’s security is based on the NP-hardness of decoding general linear codes. It offers fast encryption and relatively fast decryption, but requires large matrices (public and private keys), often from 100 KB to several MB. Compression methods and LDPC codes help mitigate this.
2. Multivariate-Based Cryptosystems: These rely on the difficulty of solving systems of quadratic multivariate polynomials (NP-hard or NP-complete). Promising schemes include those based on the Matsumoto-Imai algorithm and Hidden Field Equations (HFE).
3. Lattice-Based Cryptosystems: These are based on the hardness of problems like the Shortest Vector Problem (SVP) in N-dimensional lattices. Lattice-based schemes are computationally simple and can speed up blockchain transactions, but require large keys (often several thousand bits), as seen in NTRU or NewHope.
4. Supersingular Elliptic Curve Isogeny Cryptosystems: These use protocols based on supersingular isogenies of elliptic curves. SIKE is a leading example, using pseudorandom walks in supersingular isogeny graphs. For 128-bit classical security, SIKEp434 uses a 2,640-bit public key and a 2,992-bit private key.
5. Hybrid Cryptosystems: These combine pre-quantum and post-quantum systems to protect data from both quantum and classical attacks. For example, CECPQ2 strengthens TLS connections. While promising, hybrids require significant computational resources and energy, so trade-offs are necessary.

Post-Quantum Signature Algorithms

1. Code-Based Cryptosystems: Enhanced algorithms based on McEliece, such as Niederreiter and CFS, are used for post-quantum signatures. These produce short signatures that can be verified quickly, but large key sizes can make signature generation inefficient.
2. Multivariate-Based Cryptosystems: Schemes based on Matsumoto-Imai or HFE can generate signatures comparable in size to RSA, but require tens of thousands of bytes per key and need further improvement.
3. Lattice-Based Cryptosystems: Lattice-based signature schemes require smaller keys than multivariate schemes, but produce slightly larger signatures. BLISS-B is a notable example, offering performance on par with RSA and ECDSA, but is vulnerable to cache attacks that can recover the secret key after about 6,000 signatures.
4. Supersingular Elliptic Curve Isogeny Cryptosystems: In theory, these can be used for post-quantum digital signatures, but current implementations are too slow for practical use.
5. Hash-Based Schemes: These rely on the security of the underlying hash function rather than mathematical problem hardness. The eXtended Merkle Signature Scheme (XMSS) is a promising example, but is impractical for blockchain due to slow key generation. Improvements include using one-time authentication and limited-use keys to preserve anonymity and minimize tracking.

Conclusion

This article aimed to answer the question of blockchain’s future by analyzing the latest developments on both sides of quantum technology. We looked at the challenges of building quantum computers and the main algorithms that can (with some caveats) resist future blockchain attacks.

For now, we can only talk about candidates for the role of “savior,” which may one day become as familiar as RSA is today. Personally, I believe that regardless of how quickly quantum computers are adopted, research in this area will support many achievements and discoveries. Cryptographers may also choose to play it safe and secure blockchains against even just the looming threat—just in case. The technology is promising, after all. So you can safely leave your crypto savings and grandma’s mattress alone (at least for the next 10 years).

Thank you for reading this longread—I hope you found it useful!

References

• T. M. Fernández-Caramès and P. Fraga-Lamas, “Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks”
• D. Aggarwal, G. K. Brennen, T. Lee, M. Santha and M. Tomamichel, “Quantum attacks on Bitcoin, and how to protect against them”
• J. Proos and C. Zalka, “Shor’s discrete logarithm quantum algorithm for elliptic curves,” Quantum Inf. Comput., vol. 3, no. 4, pp. 317-344, 2003
• National Institute of Standards and Technology Interagency or Internal Report 8309, 39 pages (July 2020)

Author: El1za