Quantum Computing and Shor’s Algorithm: The Fundamental Threat of ECDSA in the Bitcoin Blockchain and Ways to Build Post-Quantum Security

20.10.2026

Quantum computing poses a fundamental threat to the security of the Bitcoin blockchain and other cryptocurrencies based on ECDSA and elliptic curve cryptography. Shor’s algorithm provides a polynomial-time solution to the discrete logarithm problem on a set of elliptic curve points, making it possible to recover a private key from a public key. Current resource estimates indicate that an attack on the secp256k1 curve requires approximately 1200–1450 logical qubits and tens of millions of Toffoli gates. This is significantly lower than previously estimated, reducing the threat timeframe to the end of this decade.

Around 7 million BTC are stored in addresses whose public keys have already been compromised or could be compromised upon the first spend. This creates a huge incentive for attackers with a quantum computer to carry out an attack. Even for addresses with undisclosed public keys, there is a window of vulnerability during the transaction broadcast.

Post-quantum cryptography, standardized by NIST, provides ready-made security tools: ML-KEM, ML-DSA, and SLH-DSA. However, migrating the blockchain ecosystem to these standards requires significant time and coordination. A dual signature mechanism (ECDSA + PQC) is seen as a pragmatic transition path. The key takeaway: preparation for the post-quantum era must begin immediately, as delays could lead to irreversible financial losses.

Content

  1. Introduction
  2. Theoretical Foundations of ECDSA and the Discrete Logarithm Problem
  3. Shor’s Algorithm: The Mathematical Basis of an Attack on ECDLP
  4. Relationship with the Hidden Number Problem (HNP) and Lattice Attacks
  5. Practical resource estimates for secp256k1
  6. Specifics of Bitcoin transaction attacks
  7. Timeframe: When is Q-Day?
  8. Post-Quantum Cryptography: NIST Standards and Migration
  9. Conclusion
  10. Directions for further research

1. Introduction

The security of the vast majority of modern blockchain systems, including Bitcoin and Ethereum, relies on the computational difficulty of the elliptic curve discrete logarithm problem (ECDLP). The ECDSA (Elliptic Curve Digital Signature Algorithm) algorithm is used to authorize transactions: the owner of a private key  sk  generates a signature that any network participant can verify using the corresponding public key  pk = sk · G , where  G  is the generator point of the secp256k1[reference:0] curve. The security of the scheme is based on the assumption that recovering  sk  from  pk  requires exponential time on a classical computer.

However, in 1994, Peter Shor proposed a quantum algorithm that solves both the integer factorization problem and the discrete logarithm problem in polynomial time [reference:1]. This means that ECDSA and related schemes (Schnorr, ECDH)  are not post-quantum secure . A sufficiently powerful, fault-tolerant quantum computer can recover a private key from a public key, allowing an attacker to sign transactions on behalf of the legitimate owner, effectively gaining complete control over the funds.

Key Threat:  A fault-tolerant quantum adversary (FTQA), possessing a large-scale quantum computer with error correction, can recover private keys protected by RSA, ECDSA, BLS, and related schemes, forge digital signatures, and compromise validator authentication.[reference:2] For a blockchain, this means the potential for theft of funds from any address whose public key has been exposed on the network.

2. Theoretical Foundations of ECDSA and the Discrete Logarithm Problem

2.1. Secp256k1 Curve Parameters

Bitcoin uses an elliptic curve  secp256k1defined over a prime field  𝔽 p  by the Weierstrass equation:

y² ≡ x³ + 7 (mod p)

where  p = 2 256  − 2 32  − 977 . The order of the group of points  n  is also close to  2 256 . The private key  sk  is a random integer from the range  [1, n−1] , and the public key is calculated as the scalar product:

pk = sk · G

where  G  is a fixed generator point. The scalar multiplication operation is efficiently computed using classical methods (double-and-add, windowed NAF), but the inverse operation—finding  sk  from known  pk  and  G  —is ECDLP[reference:3].

2.2. ECDSA signature scheme

To sign a message with a hash  h  (usually SHA-256), the following steps are performed:

  1. A one-time secret nonce  k ∈ [1, n−1] is generated .
  2. The point R = k · G is calculated  , then  r = R x  mod n .
  3. Calculate  s = k −1 (h + r · sk) mod n .
  4. Signature is a pair  (r, s) .

Signature verification uses the public key  pk  and does not require knowledge  of sk  or  k . However, if the nonce  k  is ever repeated or biased, the private key can be recovered even using classical methods—via lattice attacks on the hidden number problem (HNP) [reference:4].

2.3. Discrete Logarithm Problem (ECDLP)

Formally, ECDLP is formulated as follows: given points  G  and  Q = sk · G  on an elliptic curve over a finite field, the task is to find an integer  sk . The best classical algorithms (Pollard rho, kangaroo) solve this problem in  O(√n) ≈ 2,128  operations, which is computationally infeasible with current technologies. It is precisely this gap that underlies Bitcoin’s security.

Shor’s algorithm breaks this asymmetry by reducing ECDLP to the problem of finding the period of some function, which is efficiently solved using the quantum Fourier transform (QFT) in a polynomial number of operations.

3. Shor’s Algorithm: The Mathematical Essence of an Attack on ECDLP

3.1 Classical convolution to the period finding problem

Let  G  be the generator of a cyclic group of order  n , and  Q = sk · G . We define a function  f: ℤ n  × ℤ n  → E(𝔽 p ) :

f(a, b) = a · G + b · Q

This function has the periodicity property:  f(a + sk, b − 1) = (a + sk) G + (b − 1) Q = a G + sk G + b Q − Q = a G + b Q = f(a, b). Thus, the vector (sk, −1) is the period of f in the group ℤ n  × ℤ n .

3.2. Quantum solution to the problem of finding the period

The quantum computer prepares a uniform superposition of  a and b , computes  f(a, b)  in the quantum oracle, and applies the inverse QFT to the registers  a  and  b . The measurement yields pairs  (u, v) satisfying the condition  u · sk + v ≡ 0 (mod n) . Having collected enough such pairs (usually  O(log n) ), one can solve the linear system and find  sk  using classical postprocessing (e.g., continued fractions or lattice algorithms).

Why it works:  Quantum parallelism allows  f to be calculated  on all inputs simultaneously, and QFT extracts period information from the global phase of the quantum state. This is an exponential speedup compared to any classical algorithm that must iterate over the values.

3.3 Resource Requirements: Logical Qubits and Toffoli Gates

A practical attack on secp256k1 requires estimating the number of logical qubits and quantum gates. According to recent research (2026), Shor’s scheme for 256-bit ECDLP can be implemented in two ways:

  • Qubit-minimized variant:  ≤ 1200 logical qubits and ≤ 90 million Toffoli gates.
  • Gate minimization variant:  ≤ 1450 logical qubits and ≤ 70 million Toffoli gates[reference:5][reference:6].

These estimates assume the presence of full error correction (surface code) and a sufficient number of physical qubits to implement one logical qubit (typically thousands of physical qubits per logical qubit). Thus, an attack would require hundreds of thousands to millions of physical qubits.

ParameterQubit minimizationMinimizing gates
Logical qubits≤ 1200≤ 1450
Toffoli Gates≤ 90 million≤ 70 million
Physical qubits (estimate)~10 6 –10 7~10 6 –10 7

4. Relationship with the Hidden Number Problem (HNP) and Lattice Attacks

While Shor’s algorithm is a direct quantum attack on ECDLP, there is also a classical attack vector that can be strengthened by quantum methods:  the Hidden Number Problem (HNP) . This arises when the nonces  k  in ECDSA are not uniformly random.

4.1 ECDSA Signature Equation and Information Leakage

Each signature  (r i , s i )  for a hash  h i  satisfies the linear comparison:

ki − si−1 · ri · d − si−1 · hi ≡ 0 (mod n)

where  d = sk  is the long-term private key[reference:7]. If the values  ​​k i  are small ( |k i | < B ) or have a common prefix/suffix, the problem of recovering  d  reduces to HNP, which is efficiently solved using lattice algorithms (LLL, BKZ).

4.2 Practical implications for cryptocurrencies

Breitner and Heninger (2019) demonstrated that lattice attacks on HNP can be used to compute hundreds of Bitcoin private keys and dozens of Ethereum, Ripple, SSH, and HTTPS keys. In total, approximately 300 Bitcoin keys were recovered. The attacks took approximately 40 CPU years in total and were significantly faster than naive brute-force attacks or Pollard rho [reference:8].

It’s important to understand that  HNP attacks do not require a quantum computer. However, a quantum computer can speed up the solution of lattice problems (for example, using quantum annealing or Grover’s algorithms for finding short vectors), which reduces the requirements for the number of signatures or the degree of nonce bias required for a successful attack.

4.3. Hybrid Scenario: Shore + HNP

In a real-world scenario, an attacker can combine both approaches. If the public key is already revealed (for example, in a P2PK transaction), the attacker can immediately apply Shor’s algorithm to recover  sk  without having to analyze the signature history. If the public key is hidden (P2PKH), but the network contains many signatures with biased nonces, a classical HNP attack can be performed before the quantum computer reaches the required processing power.

5. Practical resource estimates for secp256k1

Estimates of the resources required for a quantum attack on secp256k1 are constantly being refined. Key findings from current research are summarized below:

SourceLogical qubitsToffoli GatesComment
Google Research (2026)≤ 1200≤ 90 millionQubit minimization[reference:9]
Google Research (2026)≤ 1450≤ 70 millionMinimizing gates[reference:10]
IonQ / Project Eleven (2026)~20,000 physical—Rating for 26 days[reference:11]
2023 estimates~4000 logical—Key extraction in hours[reference:12]

Thus, the quantum hardware requirements for hacking Bitcoin have been reduced by an order of magnitude compared to earlier estimates. While in 2023, the estimated quantum hardware requirements were ~4,000 logical qubits, by 2026, estimates have dropped to ~1,200–1,450 logical qubits. This makes the threat more realistic in the medium term.

Practical conclusion:  A quantum computer with ~1,450 logical qubits and ~70 million Toffoli gates is capable of recovering Bitcoin’s private key from its public key. Using modern error correction methods, this corresponds to approximately 20,000 physical qubits with high accuracy—a level that leading laboratories plan to achieve by the end of this decade.

6. Specifics of attacks on Bitcoin transactions

6.1 UTXO Model and Public Key Disclosure

Bitcoin uses the UTXO (Unspent Transaction Output) model. The address is typically a hash of the public key (HASH160 = RIPEMD-160(SHA-256(pk))). The public key is not revealed on the blockchain until the address is spent. At the time of spending, the public key appears in the  scriptSig or  field witness and remains permanently in the transaction record [reference:13].

6.2. Address vulnerability levels

Address typePublic key disclosureVulnerability to Shor’s attackVolume estimation
P2PK  (Pay-to-Public-Key)The public key is visible directly in the script.Immediate~1.7 million BTC[reference:14]
P2PKH  (Pay-to-Public-Key-Hash) spentThe public key was revealed in the transaction history.Immediate~4–5 million BTC[reference:15]
P2PKH / P2WPKH , unspentThe public key is hidden behind HASH160Requires hash inversion (Grover)—
P2WPKH  (SegWit), unspentThe public key is hidden behind HASH160Requires hash inversion—

For P2PKH addresses that have never been spent, an attacker must first invert the HASH160 to obtain the public key. This requires a preimage attack on 160-bit RIPEMD-160, which, using Grover’s algorithm, reduces to approximately  O(2 80 )  quantum operations. Even under optimistic scenarios, this is computationally infeasible [reference:16].

However, for P2PK addresses and spent P2PKH addresses, the public key is already known, and Shor’s attack can be applied immediately. Glassnode estimates that approximately 6.04 million BTC are in a state where the public key is revealed [reference:17]. Other sources put the figure at up to 7 million BTC [reference:18].

6.3. Transaction Broadcast Vulnerability Window

Even for addresses whose public keys haven’t been previously exposed, there’s a window of vulnerability. When a user creates a transaction and broadcasts it to the network, the public key becomes visible in the mempool until it’s confirmed. This time in the mempool can range from several minutes to tens of minutes [reference:19]. If a quantum computer is able to recover the key within this time, an attacker can create a competing transaction with a higher fee and steal funds.

Real-time attack scenario:  Google’s research (2026) simulated a scenario in which a quantum computer recovers a Bitcoin private key approximately 9 minutes after a transaction reveals the corresponding public key.[reference:20] If this time is less than the block confirmation time, an attacker can intercept the funds.

7. Timeframe: When is Q-Day?

The term “Q-Day” refers to the moment when a quantum computer becomes powerful enough to crack modern cryptographic schemes. Estimates of this date vary widely, but in recent years they have shifted toward earlier dates.

SourceQ-Day RatingComment
Project Eleven (2026)2030–2033“More likely than not”[reference:21]
Google Research (2026)Late 2020sRevision towards acceleration[reference:22]
IBM Roadmap~20332000 qubits[reference:23]
IonQ Roadmap20281600 qubits[reference:24]
Coinbase Advisory CouncilNot urgent, but preparation is needed.Immediate planning is required[reference:25]

The consensus among experts is that the threat will become real within the next decade. Ledger CTO Charles Guillemet notes that the migration to post-quantum signatures will take years, so preparations must begin now [reference:26].

8. Post-quantum cryptography: NIST standards and migration

8.1 NIST Standards

In August 2024, the US National Institute of Standards and Technology (NIST) published the first three finalized post-quantum cryptography (PQC) standards:

  • FIPS 203 (ML-KEM):  based on CRYSTALS-Kyber – for key encapsulation.
  • FIPS 204 (ML-DSA):  Based on CRYSTALS-Dilithium – for digital signatures on lattices.
  • FIPS 205 (SLH-DSA):  based on SPHINCS+ – for digital signatures on hash functions[reference:27][reference:28].

8.2 Applicability to Bitcoin

For the Bitcoin blockchain, the preferred candidate is  SLH-DSA (FIPS 205)  , a hash function-based scheme that is highly compatible with the existing SHA-256 infrastructure. Ledger CTO notes that SLH-DSA is preferred for Bitcoin and Ethereum, while ML-DSA (Dilithium) can be used in parallel to provide security redundancy [reference:29].

Current proposals lean toward  a dual signature mechanism : the parallel use of ECDSA and PQC (e.g., Dilithium). This ensures a smooth transition and protection against potential vulnerabilities in new schemes [reference:30].

8.3. Migration issues

  • Signature size:  Post-quantum signatures are significantly longer than ECDSA, which increases transaction size and the load on the blockchain.
  • Compatibility:  Updates to the protocol, wallets, hardware devices, and the entire ecosystem are required.
  • Timeframe:  Full migration is estimated to take 5-10 years[reference:31]. If Q-Day occurs sooner, the network may be left unprotected.

Recommendation:  Migration to post-quantum signatures must begin immediately, without waiting for QDay. Experience shows that large-scale cryptographic transitions take years, and delays can lead to catastrophic consequences for asset holders.

Conclusion

Quantum computing poses a fundamental threat to the security of the Bitcoin blockchain and other cryptocurrencies based on ECDSA and elliptic curve cryptography. Shor’s algorithm provides a polynomial-time solution to the discrete logarithm problem on a set of elliptic curve points, making it possible to recover a private key from a public key. Current resource estimates indicate that an attack on the secp256k1 curve requires approximately 1200–1450 logical qubits and tens of millions of Toffoli gates. This is significantly lower than previously estimated, reducing the threat timeframe to the end of this decade.

Around 7 million BTC are stored in addresses whose public keys have already been compromised or could be compromised upon the first spend. This creates a huge incentive for attackers with a quantum computer to carry out an attack. Even for addresses with undisclosed public keys, there is a window of vulnerability during the transaction broadcast.

Post-quantum cryptography, standardized by NIST, provides ready-made security tools: ML-KEM, ML-DSA, and SLH-DSA. However, migrating the blockchain ecosystem to these standards requires significant time and coordination. A dual signature mechanism (ECDSA + PQC) is seen as a pragmatic transition path. The key takeaway: preparation for the post-quantum era must begin immediately, as delays could lead to irreversible financial losses.

Directions for further research

  1. Optimizing Quantum Circuits for ECDLP:  Further Reducing Logical Qubit and Toffoli Gate Requirements for SecP256k1 and Other Blockchain-Based Curves. Investigating Tradeoffs Between Circuit Depth, Number of Quabits, and Runtime.
  2. Quantum-resistant Bitcoin addresses:  Design and standardization of new address types that use post-quantum signatures (SLH-DSA or hybrid schemes) by default without requiring changes to the underlying protocol.
  3. Analysis of HNP attacks under quantum acceleration:  Assessing how quantum algorithms (e.g., quantum annealing, Grover’s algorithm for finding short vectors) can speed up the solution of the hidden number problem and reduce the requirement for the number of biased signatures.
  4. Real-time attack scenario modeling:  Investigation of the vulnerability window between transaction broadcast and confirmation, and development of protection methods (e.g., mandatory disclosure of the public key only after several confirmations).
  5. Hybrid Post-Quantum Schemes for Blockchain:  An Exploration of Combinations of ECDSA and PQC That Minimize Transaction Size Increases and Maintain Compatibility with Existing Infrastructure.
  6. Quantum Algorithms for Attacking Lattice PQC Schemes:  Analysis of the Resilience of ML-DSA, Falcon, and Other Post-Quantum Schemes to Quantum Attacks, Including Algorithms That Solve Lattice Problems (SVP, CVP) Faster Than Classical Algorithms.
  7. Economic and Social Aspects of Migration:  A study of incentives for asset holders and miners to migrate to post-quantum addresses, as well as mechanisms for “forced” migration to protect forgotten or lost wallets.
  8. Hardware accelerators for post-quantum cryptography:  Development of specialized chips and hardware modules for efficient generation and verification of post-quantum signatures in resource-constrained environments (e.g., hardware wallets).

References:

  1. Shor’s algorithm for ECDSA and Schnorr signatures — IACR ePrint Archive
  2. Biased Nonce Sense: Lattice Attacks against Weak ECDSA Signatures in Cryptocurrencies — IACR ePrint Archive
  3. A Fault-Tolerant Quantum Adversary – MDPI Cryptography
  4. Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities — arXiv
  5. NIST Post-Quantum Cryptography Standards – NIST
  6. Bitcoin Faces Quantum Threat as Early as 2030 – CoinMarketCap
  7. Bitcoin Quantum Threat Timeline – TheBlockBeats
  8. ‘Q-Day’ may arrive by 2030 – Digital Today