Lattice-based cryptography shield protecting a key after a quantum attack breaks an elliptic curve

Lattice-Based Cryptography for Smart Contracts: Post-Quantum Signature Costs on Bitcoin and Ethereum

Ethereum, post-quantum, secp256k1

Lattice-based cryptography replaces the elliptic curve mathematics behind secp256k1 signatures with problems Shor’s algorithm cannot solve in polynomial time, and post-quantum smart contracts depend on it before a cryptographically relevant quantum computer exists. Bitcoin signs transactions with ECDSA and Schnorr over secp256k1, and Ethereum accounts use ECDSA over the same curve. Shor’s algorithm derives a private key from a public key, which lets an attacker move every coin the key controls.

Migration to post-quantum signatures carries a cost in bytes and gas: a 65-byte ECDSA signature verifies for 3,000 gas through the ecrecover precompile, while lattice-based cryptography needs signatures of 666 to 2,420 bytes and verification routines costing millions of gas in Solidity.

How Shor’s Algorithm Targets secp256k1 Signatures

Shor’s algorithm solves the elliptic curve discrete logarithm problem (ECDLP) in polynomial time, while the best classical attacks need exponential time. A secp256k1 public key equals the private key times a generator point, and a quantum computer reverses the multiplication.

Hash functions like SHA-256 face only Grover’s quadratic speedup, which leaves 128 bits of quantum security. The signature layer carries the structural weakness, and lattice-based cryptography removes it by replacing the curve with a lattice problem.

Exposure depends on when a public key becomes visible. Bitcoin outputs paying to a hashed key (P2PKH, P2WPKH) hide the key until the owner spends, and the spending transaction reveals it in the mempool. Pay-to-public-key (P2PK) and Taproot outputs publish the key inside the output script. Ethereum derives addresses from a Keccak-256 hash of the public key; every account with a sent transaction has revealed its key on-chain, while receive-only accounts keep it hidden.

Quantum Resource Estimates for Breaking 256-Bit Curves

In 2017, Microsoft Research calculated a requirement of 2,330 logical qubits for Shor’s algorithm against a 256-bit prime-field elliptic curve. In March 2026, Google Quantum AI published secp256k1 circuits needing at most 1,200 logical qubits and 90 million Toffoli gates, or at most 1,450 logical qubits and 70 million Toffoli gates. On superconducting hardware with a 0.1% physical error rate, the circuits fit in fewer than 500,000 physical qubits.

Runtime determines the practical risk, since with a 10-microsecond reaction time the 70-million and 90-million gate circuits finish in 18 and 23 minutes. A machine precomputing the key-independent part of the circuit completes an on-spend attack in roughly 9 to 12 minutes after a public key appears.

Bitcoin’s average block interval is 10 minutes, so a transaction waiting in the mempool becomes a viable target until post-quantum signatures based on lattice-based cryptography replace ECDSA.

Bar chart of logical qubits for Shor's algorithm against secp256k1: 2,330 in 2017, 1,200 to 1,450 in 2026
Figure 1. Logical qubits required to run Shor’s algorithm against secp25k1-class curves

Which Bitcoin and Ethereum Keys Are Exposed

Google Quantum AI counts more than 1.7 million BTC locked in P2PK scripts, up to 2.3 million BTC of dormant coins vulnerable across all script types, and roughly 6.7 to 6.9 million BTC with exposed public keys across all protocols. Owners of dormant coins cannot move them voluntarily, so migration deadlines protect them only if governance adds a rule.

BIP-360 proposes Pay-to-Merkle-Root (P2MR), a SegWit version 2 output type with bc1z addresses, removing the Taproot key-path spend so the output commits to a Merkle root of scripts and publishes no public key. The BIP entered the repository as a draft in February 2026 and specifies no signature algorithm; SLH-DSA, ML-DSA, and Falcon are the candidates. Bitcoin’s migration depends on choosing between lattice-based cryptography and hash-based schemes for the P2MR script leaves.

Bar chart of bitcoin exposed to quantum attack: 1.7M BTC in P2PK, up to 2.3M dormant, 6.7M to 6.9M exposed keys
Figure 2. Bitcoin supply exposed to an ECDLP attack

In Ethereum, exposure sits in externally owned accounts, and the Ethereum Foundation’s post-quantum team targets 2029 for core layer-1 upgrades, including hash-based leanXMSS signatures for validators in place of BLS, with execution-layer migration extending past 2029 through opt-in account abstraction.

Lattice-Based Signatures: ML-DSA and Falcon

NIST published FIPS 204 (ML-DSA) on August 13, 2024, as its primary digital signature standard, derived from CRYSTALS-Dilithium. FN-DSA, based on Falcon, carries the designation FIPS 206. Both schemes rest on lattice problems, including short integer solution (SIS), which no known quantum algorithm solves in polynomial time, so lattice-based cryptography supplies the main post-quantum signature candidates for blockchains.

Size is the cost of lattice-based cryptography: an ECDSA signature takes 65 bytes, Falcon-512 uses a 666-byte signature and an 897-byte public key, ML-DSA-44 uses a 2,420-byte signature and a 1,312-byte public key, and hash-based SLH-DSA-128s uses 7,856 bytes. At the standard rate of 16 gas per non-zero calldata byte, an ML-DSA-44 signature costs about 38,720 gas in calldata, against about 1,040 gas for ECDSA.

Lattice-based cryptography signature and key sizes: Falcon-512 and ML-DSA-44 versus ECDSA and SLH-DSA
Figure 3. Signature and public key size by scheme

Gas Cost of Post-Quantum Verification on the EVM

Verification dominates cost when contracts run the mathematics in Solidity. The ZKNox implementations report 8.1 million gas for NIST-compliant ML-DSA verification and 4.9 million gas for ETHDilithium, a variant replacing the SHAKE256 expansion with a Keccak-based one. For Falcon-512, the NIST-compliant verifier costs 3.9 million gas and the EVM-tuned ETHFALCON costs 1.5 million gas. Against the 3,000 gas of ecrecover, lattice-based cryptography costs 500 to 2,700 times more in contract code.

Draft Ethereum proposals target the gap with precompiled contracts: EIP-7885 adds number-theoretic transform (NTT) precompiles, cutting ETHFALCON verification from 1.8 million to 479,341 gas, a 73.4% reduction measured on a modified Ethereum client. EIP-8051 prices ML-DSA-44 verification at 4,500 gas, and EIP-8355 prices ML-DSA-44, ML-DSA-65, and ML-DSA-87 verification at 6,500, 9,000, and 13,500 gas.

With a precompile, calldata becomes the larger line item: an ML-DSA-44 call carrying the 1,312-byte public key, the 2,420-byte signature, and a 32-byte message costs about 60,000 gas in calldata at 16 gas per byte, plus about 6,500 gas for the precompile, against roughly 4,500 gas for an ECDSA check.

Data-heavy transactions face floor pricing of 40 gas per non-zero byte under EIP-7623, which lifts the calldata charge to about 150,000 gas, so lattice-based cryptography costs a contract wallet more in bandwidth than in compute.

Lattice-based cryptography verification gas on the EVM: Solidity versus precompile proposals and ecrecover
Figure 4. Gas to verify signature on the Ethereum Virtual Machine

Migration Paths for Bitcoin and Ethereum Accounts

Ethereum accounts can migrate without a protocol-wide flag day through account abstraction. ERC-4337 smart accounts accept custom verification logic, so a wallet can verify Falcon or ML-DSA signatures in a contract at the Solidity gas figures above.

EIP-8141 introduces frame transactions with a VERIFY frame and a 100,000-gas validation budget for the public mempool; pure Solidity lattice verification exceeds the budget by 15 to 81 times, so precompiles become a prerequisite for mempool propagation.

EIP-7932 adds a signature-algorithm registry and a sigrecover precompile with a 3,000-gas base cost. Teams deploying wallets before the precompiles ship can isolate the signature check in a modular verifier contract, so a later switch to a precompile changes one address instead of wallet logic.

Smart contract teams can plan around three ranges: 666 to 2,420 bytes of signature data, 1.5 to 8.1 million gas in Solidity, and 4,500 to 13,500 gas under proposed precompiles. Bitcoin depends on BIP-360 activation and an algorithm choice, while Ethereum depends on precompile pricing and account abstraction adoption.

The lowest published estimate sets the break threshold near 1,200 logical qubits, and lattice-based cryptography migration must finish before hardware reaches it.

FAQ

What is lattice-based cryptography, and why is it important for Bitcoin and Ethereum?

Lattice-based cryptography is a family of cryptographic algorithms that relies on mathematical problems considered resistant to quantum computing attacks. Its implementation could replace ECDSA and Schnorr signatures based on secp256k1 with post-quantum alternatives, helping protect digital assets and blockchain transactions against future quantum threats.

How can Shor’s algorithm break Bitcoin and Ethereum cryptographic signatures?

Shor’s algorithm can solve the elliptic curve discrete logarithm problem in polynomial time. This could allow an attacker to derive a private key from an exposed public key and authorize transactions without the owner’s consent. In Bitcoin, certain public keys become visible when funds are spent. In Ethereum, accounts that have already sent transactions have exposed their public keys on-chain.

Which post-quantum signature algorithms could replace ECDSA and Schnorr?

The main candidates include ML-DSA, derived from CRYSTALS-Dilithium, and Falcon, both based on lattice-related mathematical problems. NIST standardized ML-DSA through FIPS 204 in 2024, while Falcon is undergoing standardization as FN-DSA. Bitcoin is also considering hash-based alternatives such as SLH-DSA.

How much does implementing post-quantum signatures cost on Ethereum smart contracts?

The Solidity implementations require between 1.5 million and 8.1 million gas, compared with 3,000 gas for ECDSA verification through ecrecover. However, the proposed EIP-8051 and EIP-8355 precompiles aim to reduce ML-DSA verification costs to between 4,500 and 13,500 gas, depending on the variant.

How can Bitcoin and Ethereum migrate to post-quantum cryptography?

Bitcoin could adopt BIP-360, a proposal that introduces the Pay-to-Merkle-Root (P2MR) output format. However, the network still needs to select its signature algorithms and complete the adoption process. Ethereum can facilitate migration through account abstraction and smart accounts that support post-quantum verification. Precompiled contracts could also reduce verification costs and make algorithms such as ML-DSA and Falcon more practical to deploy.