How Quantum Computers Break ECDSA and What Has to Replace It

By Nika, NodeTimes newsroom.

Shor's algorithm solves the elliptic-curve discrete logarithm problem on a sufficiently large fault-tolerant quantum computer, so a public key is enough to recover the private key that authorizes spending. ECDSA stops being a lock. The useful questions are narrower than the headlines: which keys are already exposed, how long an attacker gets, and whether a post-quantum signature fits in a block.

What Shor's algorithm breaks, and what it does not

Shor's algorithm breaks signatures and key establishment built on integer factoring or the discrete logarithm problem; it does not break hash functions or symmetric ciphers. Mining is not the problem; transaction authorization is.

Shor's algorithm: a quantum algorithm that solves the discrete logarithm and factoring problems in polynomial time. ECDSA (Elliptic Curve Digital Signature Algorithm) proves that a transaction was authorized by the key holder; Bitcoin and Ethereum accounts use it over secp256k1 (a 256-bit elliptic curve over a prime field, standardized in FIPS 186). Ethereum's consensus layer signs with BLS over BLS12-381 (a pairing-friendly curve), which falls to the same algorithm. Published estimates for a 256-bit curve key are quoted in quantum gates and disagree by orders of magnitude: one circuit needs roughly 70 to 90 million Toffoli gates, a leaner model about 65,536 logical gates, a gap that comes from the circuit model rather than from the hardware.

What survives is a longer list than most coverage admits:

• Hash functions and symmetric ciphers (SHA-2, SHA-3, AES-256): Shor does not touch them, and Grover's speedup is absorbed by longer keys.
• Proof-of-work mining: protected by that same quadratic bound plus difficulty adjustment, so "quantum computers will mine all the Bitcoin" is a wrong claim, not an open one.

If the vocabulary here is new, the post-quantum glossary keeps the definitions; this section carries only what the argument needs.

Which keys are exposed right now

Only visible public keys can be attacked, and for UTXO chains that visibility is created by the act of spending. Exposure depends on transaction history, not on balance.

Taproot is the counterintuitive case: a Pay-to-Taproot output publishes a tweaked public key at creation, so it faces a long-exposure attack before it is ever spent. BIP-360 proposes Pay-to-Merkle-Root (P2MR), a soft fork that keeps the script-tree construction and removes the key-path spend. Its authors are explicit that this covers long exposure only.

Bitcoin exposure estimates are model output, not measurement: one published model puts about six million BTC in quantum-exposed outputs, of which some 2.3 million are judged irreducibly at risk. Most of that exposure is P2PK-era: a Pay-to-Public-Key output carries the public key in its script from the moment it is created, so it is readable years before anyone tries to spend it.

The two attack windows, and why only one is urgent

The BIP-360 discussion frames the problem as two windows: a long-exposure attack has years of public key to work with, a short-exposure attack must break a key inside one block interval. That difference decides which defence pays off first.

• Long exposure: any key that has signed once stays on-chain forever, including every spent-from address that still holds funds and every P2TR output.
• Short exposure: the leaner 65,536-gate circuit maps to roughly 66 seconds on a machine with a 1 kHz effective logical clock, which beats Bitcoin's 10-minute target and loses to Ethereum's 12-second slot.

A shorter block time is therefore not automatically safer: the attacker's execution window scales down with it.

What replaces ECDSA

NIST has settled on three post-quantum signature standards: two are final and one, FN-DSA, is still a draft; they differ in size and speed more than in security level. Migration is a bandwidth and storage decision before it is a cryptographic one.

Two properties drive every real migration plan: post-quantum signatures are one to two orders of magnitude larger than ECDSA, and no standardized scheme supports public-key recovery, which Ethereum relies on today through ecrecover. Both push cost onto block space, propagation and storage rather than CPU.

Why a blockchain cannot simply swap the signature

Swapping the scheme changes block economics before it changes security. An Ethereum transaction runs about 110 bytes including a roughly 65-byte ECDSA signature; a 2,420-byte lattice signature makes it more than twenty times larger.

• Bitcoin: BIP-360 for long-exposure defence, deliberately scheme-neutral.
• Ethereum, user level: keep the protocol signature-agnostic and route migration through account abstraction; EIP-8141, the frame-transaction draft, is the mechanism that decouples an account from its ECDSA key, while EIP-7702 stays a delegation mechanism whose authorization list relies on ECDSA and does not close the post-quantum gap.
• Ethereum, block level: EIP-8288, an extension of the frame-transaction draft, lets transactions declare (scheme, data_hash, verification_key_hash) dependencies that builders aggregate off-chain into one recursive STARK.

The consequence for builders is that post-quantum readiness is a block-space and aggregation problem, not a drop-in library swap.

The deadline is the migration, not the machine

The regulatory clock runs independently of hardware progress: NIST's transition plan deprecates quantum-vulnerable public-key algorithms after 2030 and disallows them after 2035.

A chain that wants post-quantum signatures live before 2035 has to settle a scheme, a migration path and an aggregation story years earlier. Nothing in the research says the migration is impossible: the binding constraint is coordination.

Preparing ahead of that deadline is the subject of Q-day and blockchain: how to prepare for the quantum threat.

Frequently asked questions

Can a quantum computer steal coins from a wallet that has never sent a transaction?

Not when the address is hash-based: it holds only a hash of the public key, and Shor's algorithm cannot invert a hash.

So "move your coins" is not a complete answer either: an unspent wallet is exposed the moment it signs.

Is Grover's algorithm a threat to mining or to hashing?

No, not in practice: Grover halves the effective key length instead of breaking the primitive, and proof-of-work difficulty adjusts to available hashrate.

The threat model worth watching is confined to signatures and key establishment.

Is Ethereum's validator set more exposed than user accounts?

Yes, structurally: every validator signature is stored permanently, and BLS aggregation is what makes thousands of attestations affordable to verify, a property no NIST post-quantum signature standard reproduces.

That is why Ethereum's published direction pairs hash-based validator signatures with proof-based aggregation.

Does "harvest now, decrypt later" apply to signatures?

Partly: the phrase comes from key establishment, where captured traffic is decrypted later, but the same asymmetry holds for signatures, because a public key recorded today can be attacked later with no further access to the victim.

The constraint differs: signature exposure is limited to what is on-chain, traffic exposure to what was captured. The attack has a page of its own: harvest now, decrypt later.

Does any major chain run post-quantum transaction signatures on mainnet?

Algorand does: native Falcon-1024 accounts have been live on its mainnet since August 2026, with Falcon-backed LogicSig accounts since November 2025.

What that shows is a post-quantum account on a major L1, not a chain that has migrated as a whole. Algorand's Falcon accounts sit beside its Ed25519 ones, its consensus keys still run on a classical curve, and the scheme it uses is the deterministic variant of Falcon rather than the draft FN-DSA standard, so the honest split is between an account that can be post-quantum and a network whose base model has moved.