Why Quantum Computers Will Eventually Break Bitcoin and Ethereum Signatures

Digital signatures, not encryption, are blockchain''s real quantum exposure. "Harvest now, decrypt later" attacks a major modern threat to data confidentiality, but digital signature algorithms are also vulnerable to quantum computing.

Web3 is heavily reliant on digital signatures to create trust on a decentralized digital ledger. The looming quantum threat means that blockchains will need to make the transition to post-quantum digital signature schemes.

Why ECDSA is Vulnerable

The Elliptic-Curve Digital Signature Algorithm (ECDSA) is one of the most widely used digital signature algorithms for blockchain. This algorithm is used to provide authentication and integrity protection for blockchain transactions and blocks.

Quantum computing threatens ECDSA due to the existence of Shor''s algorithm, which provides a polynomial-time solution to the elliptic-curve discrete logarithm problem. Algorithms like ECDSA take advantage of the fact that the (elliptic-curve) discrete logarithm problem is mathematically "hard", meaning that determining the exponent from a discrete logarithm or performing division on an elliptic curve has exponential complexity.

The complexity mismatch between elliptic curve multiplication (polynomial) and division (exponential) makes it possible to create cryptographic algorithms that are both usable and secure. Shor''s algorithm breaks this, reducing the complexity of elliptic curve division to polynomial.

What''s Actually Exposed

Shor''s algorithm enables an attacker to derive ECDSA private keys from the associated public keys. This means that any account whose public key has been published to the blockchain''s distributed ledger is potentially vulnerable.

Any blockchain account that has made an on-chain transaction has published its public key. This is essential to verify digital signatures, which use the public key to extract the content hash from the signature and compare this to an independently computed hash of the content.

In contrast, accounts that have never transacted on-chain are not exposed, since their public keys are never recorded on the distributed ledger. This makes single-use addresses a viable way to protect against the quantum threat since attackers can''t reverse-engineer a private key from a public key that they don''t have.

Managing the Quantum Risk

Current guidance from NIST and other organizations points to 2031 as a target for migration to digital signature algorithms. By this point, it is possible that cryptographically relevant quantum computers (CRQCs) capable of breaking ECDSA will exist.

Unlike encryption algorithms and other uses of digital signatures, blockchain isn''t vulnerable to "sign now, forge later" attacks. Once a blockchain migrates to a post-quantum signature algorithm, the ability to forge ECDSA signatures for past transactions won''t matter since the current, trusted state of the blockchain will be secured by a quantum-resistant signature scheme.

Blockchains like Bitcoin and Ethereum should plan to execute a hard fork to implement hybrid signatures, combining ECDSA and a post-quantum algorithm before the deadline. This approach reduces the risks of quantum computing or a broken post-quantum algorithm. In the meantime, users should consider adopting single-use addresses to manage their personal exposure to quantum risk.