Problem: Given N = p×q, find the prime factors p and q.
Speedup achieved:
This is an exponential speedup — Shor's turns hard problems into easy ones.
Why it matters: Elliptic curve discrete log (ECDLP) is also polynomial-time on a quantum computer.
Problem: Find x such that f(x) = target in an unstructured search space of size N.
Speedup achieved:
Only a quadratic speedup — not exponential. Halves security level in bits.
Fix: Double the hash output size. SHA-256 → 256-bit output still gives 128-bit quantum security.
Lightning Network Cryptography — Quantum Impact
Click any row for a detailed explanation of what breaks and why.
| Component | Cryptography | Shor's Threat | Grover's Threat | Action |
|---|---|---|---|---|
| Node identity keys | secp256k1 ECDSA |
❌ BROKEN | ✅ N/A | Replace key scheme |
ECDSA on secp256k1: Node keys sign channel announcements and gossip messages. Shor's algorithm can compute the private key from the public key in polynomial time. An adversary with a CRQC could impersonate any LN node, forge routing messages, and drain channels. This is the most fundamental break — the entire identity layer collapses.
| ||||
| Schnorr signatures | secp256k1 Schnorr |
❌ BROKEN | ✅ N/A | Replace with PQ sig |
Taproot / MuSig2: Schnorr signatures (BIP-340) are used in Taproot channels. They rely on the same ECDLP hardness as ECDSA. Shor's algorithm directly extracts the private key. Schnorr also underlies MuSig2 (used in 2-of-2 channel funding) and adaptor signatures for PTLCs — the entire Taproot channel model breaks.
| ||||
| HTLC hash lock | SHA-256 |
✅ Safe | 🔶 Weakened | Monitor / upgrade |
SHA-256 in HTLCs: The hash lock H(r) only needs preimage resistance. Grover's algorithm reduces SHA-256's effective security from 256-bit to 128-bit. For practical payment security, 128-bit is still far beyond brute force. However, if SHA-256 were replaced with a 128-bit output hash (bad practice), it would drop to 64-bit quantum security — definitely insecure. Current 256-bit output is adequate.
| ||||
| HTLC preimage | SHA-256 |
✅ Safe | 🔶 Weakened | 128-bit quantum security |
Payment preimage r: Random 256-bit preimage r satisfying SHA-256(r) = H. Finding r by brute force classically requires 2^256 operations. Grover's reduces this to 2^128 quantum operations — still computationally infeasible. The 32-byte preimage space is large enough. No immediate action required, but long-term if SHA-256 is deprecated, HTLCs must be renegotiated.
| ||||
| Adaptor signatures / PTLCs | Schnorr (secp256k1) |
❌ BROKEN | ✅ N/A | PQ adaptor sigs needed |
Adaptor signatures for PTLCs: An adaptor signature σ̃ on a statement T allows completing it to a valid signature σ only by learning the discrete log t of T. This linear structure (σ = σ̃ + t) is unique to Schnorr over elliptic curves. If Shor's breaks ECDLP, an adversary can compute t from T directly, instantly redeeming all PTLC-locked funds without cooperation. The Erwig et al. (FC 2021) construction aims to fix this — see Section 4.
| ||||
| Onion routing (Sphinx) | ECDH + ChaCha20 |
❌ BROKEN (ECDH) | ✅ ChaCha20 OK | Replace ECDH layer |
Sphinx packet construction: Each hop derives a shared secret via ECDH(node_pubkey, ephemeral_privkey). Shor's algorithm can recover the ephemeral private key from the ephemeral public key (recorded in the onion packet), allowing decryption of all hops in the packet. Once the private key is known, all layered encryption collapses. ChaCha20 (symmetric cipher) and HMAC-SHA256 remain safe — only the ECDH key agreement needs replacement, e.g., with ML-KEM (Kyber).
| ||||
| Channel funding (2-of-2) | P2WSH multisig → Taproot |
❌ BROKEN | ✅ N/A | Requires L1 PQ fork |
Channel funding transaction: A 2-of-2 multisig output (either P2WSH or Taproot) uses ECDSA/Schnorr keys. A quantum adversary can compute either party's private key, construct a valid unilateral close transaction, and steal all channel funds. This is an on-chain problem: fixing it requires Bitcoin consensus changes to support post-quantum public key formats (larger keys, larger signatures, higher fees).
| ||||
| Peer encryption (BOLT #8 Noise) | ECDH + ChaCha20-Poly1305 |
❌ BROKEN (ECDH) | ✅ ChaCha20 OK | PQ Noise hybrid needed |
BOLT #8 Noise_XK handshake: The Lightning peer transport layer uses a Noise protocol framework variant with ECDH for key agreement and ChaCha20-Poly1305 for authenticated encryption. The ECDH step is vulnerable to Shor's. A recorded handshake can be decrypted retrospectively when a CRQC becomes available — the "harvest now, decrypt later" attack. The symmetric encryption layer (ChaCha20-Poly1305) is quantum-safe. Solution: hybrid Noise_XK with ML-KEM alongside classical ECDH.
| ||||
*Breaking 256-bit ECC requires ~4,000 error-corrected logical qubits. With current error rates (~1%), each logical qubit needs ~1,000–5,000 physical qubits → ~20 million physical qubits total. Current best: ~1,400 noisy physical qubits. Gap is ~4 orders of magnitude in quality. Estimates vary widely — 10–20 years is the expert consensus range.
☠ "Harvest Now, Decrypt Later" — The Immediate Threat
Even today, a well-resourced adversary can record all encrypted Lightning Network traffic — peer handshakes, onion packets, channel announcements. When a cryptographically relevant quantum computer (CRQC) eventually exists, they decrypt everything retroactively. Historical payment flows, channel partner identities, and routing patterns are exposed. This threat applies to today's LN traffic, not just future traffic. Cryptographic agility (ability to upgrade protocols) matters now, not after CRQCs exist.
Why size matters for Lightning
Bitcoin transactions have weight limits. Larger PQ keys and signatures directly increase transaction fees for channel open/close operations. A Dilithium signature (2,420 bytes) is 37× larger than Schnorr (64 bytes). With current Bitcoin fee markets, this could make channel operations significantly more expensive. Falcon-512 (666 bytes) is the most practical candidate — still 10× Schnorr, but much better than Dilithium.
Core contribution: A generic construction of post-quantum adaptor signatures from any identification scheme (Sigma protocol), instantiated with lattice-based schemes to yield quantum-resistant adaptor signatures — the key primitive for PTLC-based PCN.
Why Adaptor Signatures Are Critical for PCN
PTLCs (Point Time-Lock Contracts) replace HTLCs in modern Lightning Network design. They rely on adaptor signatures to atomically link payment across hops. If Schnorr signatures are broken by quantum computers, the entire PTLC mechanism fails — routing payments become insecure.
Adaptor Signature Recall
A pre-signature σ̃ on statement T is "complete-able" to a full signature σ only by knowing the witness w (the discrete log of T). Learning σ from σ̃ reveals w; having w lets you compute σ from σ̃. This bidirectional "bind" enables atomic cross-hop payment correlation without a trusted third party.
The Challenge: Why PQ Adaptor Sigs Are Hard
Schnorr's linear structure makes adaptor signatures natural:
Lattice-based signatures (Dilithium) and hash-based signatures (SPHINCS+) have no such linear relation. The adaptor cannot simply be "completed" by adding a secret — entirely different algebraic structure is needed.
Shor's computes t from T = g^t directly. Structure collapses.
Security reduces to Module-LWE hardness. Quantum-resistant.
Erwig et al. Construction Summary
Framework: Given any Σ-protocol (commit-challenge-respond) for a hard problem:
- Pre-sign by running the protocol up to the response phase with a "masked" response
- The mask is the witness w — verifier can check the structure without seeing w
- Completion reveals w, allowing the masked response to be unmasked into a full response
- Extractor: given full response and pre-response, recovers w
Instantiation: Using a Dilithium-like identification scheme over Module lattices. Security proof reduces to Module-LWE and Module-SIS hardness assumptions.
| Property | Schnorr adaptor | Dilithium adaptor (Erwig et al.) |
|---|---|---|
| Pre-signature size | 64 bytes | ~2,400 bytes |
| Verification time | Very fast | Moderate |
| Witness extraction | Trivial subtraction | Requires dedicated algorithm |
| Security assumption | ECDLP (broken by Shor's) | Module-LWE (quantum-hard) |
| Bitcoin-compatible | ✅ Yes | ❌ Requires protocol redesign |
| PTLC-compatible | ✅ Works today (Schnorr path) | 🔶 Research stage, not deployed |
| Quantum-safe | ❌ No | ✅ Yes |
| Two-party construction | ✅ Natural | ✅ Yes (shown in paper) |
Open Challenge: Efficiency Gap
The Erwig et al. construction proves feasibility, but a 2,400-byte pre-signature for each hop in a PTLC route is impractical. A 10-hop route requires 24,000 bytes of adaptor signature material. Research focus: reducing pre-signature size (Falcon-style lattice sigs offer ~666 bytes per sig) and designing more efficient PQ witness commitment schemes.
Click each layer to expand the migration checklist and dependency details.
- Bitcoin soft fork to support PQ signature algorithms (new witness version)
- New address format encoding PQ public keys (256×+ byte keys vs 33-byte secp256k1)
- Script extensions for PQ multisig (2-of-2 for channel funding)
- Transaction weight reconsideration (PQ sigs are 40× larger → fee model revision)
- Consensus on which PQ algorithm(s) Bitcoin supports (Dilithium? Falcon? Hash-based?)
- Hybrid PQ+classical multisig for transition period security
- Channel funding: migrate to PQ 2-of-2 multisig once L1 supports it
- Commitment transactions: PQ signatures for each channel state update
- Revocation keys: revocation scheme requires PQ key derivation
- HTLC output scripts: update preimage/hash scripts if needed
- Penalty transactions: PQ-sign pre-signed breach remediation txs
- Splicing: PQ-native splice-in/splice-out protocol
- Sphinx onion: replace ECDH with ML-KEM key encapsulation (BOLT #4)
- Node identity authentication: replace secp256k1 Schnorr with PQ signature (gossip layer)
- BOLT #8 peer transport: replace Noise_XK ECDH with hybrid PQ Noise variant
- Route blinding: ensure blinded path descriptors use PQ keys
- BOLT #12 offers: PQ signatures for invoice authentication
- Trampoline routing: PQ-sign trampoline payment packets
- Deploy PQ adaptor signatures (Erwig et al. or successor with better efficiency)
- PQ PTLC construction: witness-binding without ECDLP structure
- PQ atomic swaps: cross-chain atomicity without discrete log relation
- PQ DLCs: discreet log contracts on PQ basis
- Efficiency improvements: reduce adaptor sig size to <500B per hop
The pragmatic near-term strategy: combine classical and post-quantum cryptography so security holds if either remains unbroken. This protects against harvest-now-decrypt-later while also hedging against undiscovered flaws in new PQ schemes.
If Kyber is broken but ECDH is safe: session key still secure.
If ECDH broken by Shor's but Kyber safe: session key still secure.
Both must be simultaneously broken.
This mirrors TLS 1.3 hybrid PQ experiments (X25519 + Kyber768). BOLT #8 Noise_XK upgrade would follow the same pattern: run both handshakes, derive combined key via HKDF.
Draft: PQ Noise_XK_Hybrid for BOLT #8
A proposed BOLT #8 replacement performs both a classical Noise_XK handshake (ECDH with secp256k1 or X25519) and a parallel ML-KEM encapsulation. The final session key is derived via HKDF from the concatenation of both shared secrets. This is a software-only change to the LN peer transport — no Bitcoin consensus required. Prototype implementations exist (e.g., in academic proof-of-concept LN implementations), but no BOLT PR has been formally submitted.
In Sphinx, each routing hop performs an ECDH key exchange using an ephemeral key embedded in the packet header. Replacing ECDH with ML-KEM changes the structure because KEM (Key Encapsulation Mechanism) is not a Diffie-Hellman protocol — it uses a different API: Encapsulate(pk) → (ciphertext, shared_key) instead of ECDH(my_sk, their_pk) → shared_key.
Trade-off: Packet Overhead vs Security
The current Sphinx packet (1,366 bytes) is carefully sized. Adding ML-KEM per-hop ciphertexts (~1,088 bytes each) would balloon a 20-hop packet to >22KB — a 16× increase. This may require reducing maximum hop count, increasing the minimum channel balance for routing, or redesigning the onion packet format (BOLT #4 revision). One approach: "compressed" KEM where intermediate nodes share a common encapsulation; another: reduce to 10 hops maximum in PQ mode.
- • Hybrid BOLT #8 (ECDH + ML-KEM)
- • PQ Sphinx packet format
- • QROM anonymity proofs
- • PQ channel funding scripts
- • PQ commitment transactions
- • Watchtower protocol update
- • Compact PQ adaptor sigs
- • PQ threshold / multisig
- • Efficient PQ PTLCs
- • PQ channel factories
- • Seamless channel migration
- • Full PQ LN re-specification