An overview of post-quantum threats to proof-of-work cryptocurrencies

8UNx...RQtg

4 Mar 2024

Proof-of-work (PoW), or Nakamoto consensus, is a decentralized consensus mechanism that secures a blockchain by requiring nodes to expend energy and compete against each other to solve complex mathematical challenges to add blocks to the chain and receive rewards.
PoW also requires the network nodes to come to a consensus on whether network elements, such as account balances and the order of transactions, are correct. Bitcoin
BTC
$65,177
is the largest PoW-powered blockchain by market cap in existence.The mathematical problems Bitcoin network nodes solve require a significant number of computations, and miners often have to deploy application-specific integrated circuit (ASIC) hardware to keep up with the other nodes in a PoW network. Even with ASICs, acquiring majority control of the network and executing a 51% attack to validate invalid transactions would require a substantial amount of computational power.
However, with the introduction of quantum computing technologies, there is a growing concern that the cryptographic underpinnings of blockchain technology, including Bitcoin, could be disrupted. Quantum computers may be able to attack conventional cryptographic methods, such as the ones employed in Bitcoin’s transaction validation procedure.
In particular, compared to classical computers, quantum computers can tackle complicated mathematical problems like discrete logarithms and integer factorization at an exponentially faster rate. The emergence of quantum computing poses a post-quantum threat to Bitcoin’s security.
Should a sufficiently potent quantum computer be developed, it might jeopardize the cryptographic integrity of the algorithms that underpin Bitcoin. This could allow malevolent actors to carry out attacks that were previously deemed impossible, such as the capacity to carry out a 51% attack with less computational work than is currently required.

What is post-quantum computing?

Post-quantum computing refers to the era that would follow the development and deployment of quantum computers that have the potential to solve computational challenges that are presently thought to be beyond the capabilities of classical computers. This covers activities like simulating quantum systems, factoring big numbers and resolving specific optimization issues.
Quantum computing differs fundamentally from classical computing, which relies on bits that can represent either 0 or 1. Instead, quantum bits, or qubits, are used in quantum computing. Due to principles of superposition and entanglement, qubits can represent 0, 1, or both simultaneously.
The implications of quantum computing on PoW are considered one of the greatest incoming threats to the efficacy and effectiveness of blockchains and blockchain cryptography.
In the post-quantum computing era, quantum-resistant cryptographic algorithms will be developed to withstand attacks from quantum computers and ensure the security of sensitive information in a post-quantum world.

How quantum computers can attack Bitcoin

Cryptography is a discipline within mathematics focusing on securing communication and data and is fundamental to PoW cryptocurrencies like BTC. The Bitcoin blockchain uses powerful cryptography to ensure its decentralized money transfer model remains trustless, private and secure during peer-to-peer transactions. However, quantum computers may attack it by deploying machines and algorithms powerful enough to break its cryptographic shields.
Bitcoin uses asymmetric encryption (also known as public-key cryptography), which employs two different keys: public and private. The public key is used to encrypt data or, in the case of Bitcoin, to generate a Bitcoin address where funds can be received. However, the private key is used for decryption or signing transactions. The private key proves ownership of the funds and authorizes transactions, allowing them to be securely added to the blockchain.

BlockShow by Cointelegraph is back with a crypto festival in Hong Kong, May 8-9 - Secure Your Spot!

Ad

The most important ways Bitcoin uses cryptography are through digital signatures and hash functions. Both of these, however, are potentially crackable through quantum computing.

Digital signatures

The Elliptic Curve Digital Signature Algorithm (ECDSA) for digital signatures allows users to verify who owns a Bitcoin address and approve transactions. If quantum computers become powerful enough, they might be able to defeat ECDSA using techniques such as Shor’s algorithm, which might theoretically solve the discrete logarithm problem — the foundation of ECDSA security — in polynomial time.
The powerful superpositioned Schor’s algorithm could run on a quantum machine and, using a brute force method, determine the private key associated with a public key, hidden with the elliptic curve cryptography (ECC) scheme, invalidating the digital signature.

Hash functions

Cryptographic hash functions, namely SHA-256, are used by Bitcoin in several ways, including the mining process (PoW) and the creation of addresses using public keys. Hash functions are considered more immune to quantum attacks than the public-key cryptography systems today.
However, a sufficiently powerful quantum computer might still present a threat, albeit less immediately concerning than for digital signatures. For instance, Grover’s algorithm may theoretically be able to accelerate the search for a pre-image of a hash function. But it only offers a quadratic speed, implying that the threat may be lessened if the hash length is doubled, for example, from 256 to 512 bits.

Potential mitigation strategies for addressing post-quantum threats in proof-of-work cryptocurrencies

Securing PoW against quantum threats and developing post-quantum blockchain security have become essential. The blockchain’s quantum computing challenge is to develop solutions that can protect it from a quantum computer powerful enough to break all of its current cryptographic security measures.
Quantum-proof cryptocurrency and quantum resistance in blockchains may be possible with techniques like lattices, isogenies and codes.

Lattices

A lattice-based cryptography is based on the mathematical concept of a lattice. A lattice is a grid of evenly spaced points that extend infinitely in every direction. This type of cryptography uses the complexity of lattices as the basis for encrypting or decrypting messages.
Lattice-based cryptography uses operations on lattice points to carry out encryption, decryption and other cryptographic functions. An attacker would find it challenging to decipher the original message or decryption key without knowing the precise structure of the lattice utilized in the encryption process due to the complexity and intractability of problems on lattices, which serve as the foundation for security.

Isogenies

Isogeny-based cryptography is an evolution of ECC and focuses on securely passing secret messages using the mathematical properties of elliptic curves. However, it introduces a new layer of complexity by using isogenies rather than the points on the curves directly, as in traditional ECC.
Isogeny-based cryptography is similar to two parties coming up with a secret handshake in public, with every move being observed, but no one can replicate it. Like lattice-based cryptography, its complexity offers possible defense against quantum computer attacks, making isogeny-based cryptography a viable option for post-quantum cryptography.

Code-based cryptography

Code-based cryptography is based on challenging-to-decode general linear code. It is based on creating puzzles with error-correcting code, which is a set of mathematical tools used to detect and correct errors in data transmission. For example, if a message sent over the internet gets corrupted before it reaches its target, an error-correcting code would be used to recover it accurately.
In code-based cryptography, it should be straightforward for anyone with the right key to decode a message — but challenging for anyone else. Code-based cryptography is considered to have quantum resistance potential because decoding random linear code — the basis of code-based cryptography — is not known to be efficiently solvable by quantum computers based on current algorithms, including Shor’s and Grover’s.

Ongoing research and development efforts in post-quantum cryptography

In 2022, the United States Department of Commerce’s National Institute of Standards and Technology (NIST) announced it had chosen the first set of encryption tools designed to withstand attacks by quantum machines. The four selected algorithms will become a part of NIST’s post-quantum cryptographic standard, which is set to be finalized in 2024. They are:

Cryptographic Suite for Algebraic Lattices, or CRYSTALS-Kyber: It is built for general encryption purposes, such as securing connections between web browsers and servers
Cryptographic Suite for Algebraic Lattices, or CRYSTALS-Dilithium: It is designed to replace current digital signature schemes like ECDSA.
SPHINCS+: A stateless hash-based signature scheme that provides an alternative to traditional signature methods and offers security based on different mathematical problems.
Fast-Fourier Lattice-based Compact Signatures, or FALCON: It was also designed for digital signatures (based on lattice cryptography), which is known for its compact signatures and fast verification times.

The future of PoW in the quantum era

The future of PoW cryptocurrencies in the quantum era is a topic of significant interest and concern within the cryptographic and blockchain communities. Scientists from the University of Sussex estimate that a quantum system capable of utilizing 13 million qubits could break the cryptographic algorithms (that secure the Bitcoin blockchain) within 24 hours.
The mining component of PoW may be impacted by quantum computing. Although quantum techniques, like Grover’s algorithm, can accelerate mining through a quadratic speedup in the search for a nonce that meets the PoW criterion, the potential disruption to cryptographic security outweighs this benefit. Nonetheless, the processing capacity required to significantly influence PoW mining is not yet available.
To protect PoW blockchains from future quantum attacks, the blockchain community is actively investigating and creating cryptographic algorithms resistant to quantum attacks. For instance, QuEra, a startup founded by former researchers from Harvard University and Massachusetts Institute of Technology, has released an incredibly ambitious roadmap for a Quantum machine set to be released soon.
The company plans on releasing a quantum computer with 100 logical qubits and 10,000 physical Qubits by 2026. It has been claimed that the machine will demonstrate a “practical quantum advantage,” meaning this computer will be able to perform tasks that today’s bit-based computers cannot.
Quantum computers are still unable to crack cryptographic algorithms like those used in Bitcoin due to their small size or lack of fidelity. The field is progressing, though many technical obstacles, such as qubit coherenc