The Quantum Threat: Which Proof Systems Survive and Which Don’t — Article 7 of the ZKP Systems Series

--

Every cryptographer working on zero-knowledge proofs carries the same quiet concern: somewhere in the next decade or two, a quantum computer will arrive that can break the mathematical problems our systems depend on. The question is not whether, but when — and whether the systems we build today will survive the transition.

This article is the most direct answer this series can give to that question.

We will go system by system, assumption by assumption, and be precise about what breaks, what survives, and what the migration path looks like. By the end, you will be able to look at any proof system — including ones published after this series — and immediately classify its quantum posture.

The Two Quantum Algorithms That Matter

Before evaluating systems, you need to know exactly which quantum algorithms are relevant. There are two.

Shor’s Algorithm (1994)

Shor’s algorithm efficiently solves the discrete logarithm problem and the integer factorization problem in polynomial time. On a sufficiently powerful quantum computer:

def shors_attack_complexity(n_bits):
    """
    Classical discrete log attack: O(2^(n/2)) — exponential
    Shor's algorithm:             O(n^3)      — polynomialFor 256-bit elliptic curve discrete log:
    Classical: 2^128 operations ≈ 10^38 - infeasible
    Shor's:    256^3 ≈ 16 million operations - trivial
    """
    classical = 2 ** (n_bits // 2)
    quantum = n_bits ** 3
    print(f"Field size: {n_bits} bits")
    print(f"Classical attack: ~2^{n_bits//2} = {classical:.2e} operations")
    print(f"Shor's attack:    ~{n_bits}^3   = {quantum:,} operations")
    print(f"Quantum advantage: {classical/quantum:.2e}x speedup")
    print()
shors_attack_complexity(256)
# Field size: 256 bits
# Classical attack: ~2^128 = 3.40e+38 operations
# Shor's attack:    ~256^3 = 16,777,216 operations
# Quantum advantage: 2.03e+31x speedup

What Shor’s breaks:

• Elliptic curve discrete logarithm (ECDLP) — the basis of KZG, IPA, Pedersen commitments
• RSA / integer factorization
• Diffie-Hellman key exchange
• All pairing-based cryptography (Groth16, PLONK, Marlin verification equations)

What Shor’s does NOT break:

• Hash functions (SHA-256, Keccak, Poseidon, Blake3)
• Symmetric encryption (AES)
• Lattice-based cryptography

Grover’s Algorithm (1996)

Grover’s algorithm provides a quadratic speedup for unstructured search. Against an n-bit hash function:

def grovers_impact(n_bits):
    """
    Classical preimage attack: O(2^n)
    Grover's algorithm:        O(2^(n/2))Mitigation: double output size
    SHA-256: quantum cost = 2^128 - still completely infeasible
    SHA-512: quantum cost = 2^256 - astronomically infeasible
    """
    classical = 2 ** n_bits
    quantum = 2 ** (n_bits // 2)
    speedup = classical // quantum
    print(f"Hash output: {n_bits} bits")
    print(f"Classical preimage: 2^{n_bits}")
    print(f"Grover's attack:    2^{n_bits//2}")
    print(f"Speedup factor:     2^{n_bits//2} = {quantum:.2e}x")
    print(f"Still secure at 256-bit output: {'Yes' if n_bits//2 >= 128 else 'No'}")
    print()
grovers_impact(256)
# Hash output: 256 bits
# Classical preimage: 2^256
# Grover's attack:    2^128
# Speedup factor:     2^128 = 3.40e+38x
# Still secure at 256-bit output: Yes
# The key insight: Grover halves the security level
# SHA-256 with 256-bit output → 128-bit quantum security
# This is still infeasible - no known quantum computer
# can perform 2^128 operations in any reasonable timeframe

What Grover’s weakens but doesn’t break:

• Hash functions (security halved — manageable by doubling output size)
• Symmetric encryption (AES-256 remains secure; AES-128 is borderline)

The critical difference: Shor’s provides an exponential speedup — it makes problems that are computationally infeasible become trivially easy. Grover’s provides only a quadratic speedup — security is weakened but remains computationally hard with appropriate parameter choices.

This asymmetry is why hash-based systems are post-quantum safe and elliptic curve systems are not.

System-by-System Quantum Assessment

Groth16 — BROKEN

Quantum vulnerability: Critical Timeline to breakage: ~10–20 years (when large-scale quantum computers exist)

Groth16’s verification equation is:

e(π_A, π_B) = e(α, β) · e(vk_input, γ) · e(π_C, δ)

Every term here is an elliptic curve pairing. Breaking ECDLP on the BN254 or BLS12–381 curves allows an attacker to:

1. Compute the toxic waste τ from the public parameters
2. Forge arbitrary proofs that pass verification for any statement

There is no parameter upgrade. There is no migration path within the Groth16 framework. A quantum attacker who can break ECDLP can retroactively forge proofs for any past Groth16-verified system — including every Zcash Sapling transaction ever made.

Systems affected: Zcash Sapling, Tornado Cash, Polygon Hermez (original), any application using snarkjs groth16.

Migration path: Replace with STARK-based or Plonky2/Plonky3-based systems. Zcash has already begun this transition with Orchard (Halo2) and is evaluating further post-quantum options.

PLONK — BROKEN

Quantum vulnerability: Critical

PLONK uses KZG polynomial commitments. The security of KZG reduces to ECDLP:

# KZG commitment: C = f(τ) · G
# where G is the curve generator, τ is the toxic waste
# A quantum attacker with Shor's algorithm can:
# 1. Compute τ from the public SRS: [G, τG, τ²G, ..., τⁿG]
#    → solve discrete log: τ = dlog(τG, G)  [trivial with Shor's]
# 2. Construct a fake polynomial f'(x) ≠ f(x) such that
#    f'(τ) = f(τ)  [now possible since τ is known]
# 3. Submit f' with the original commitment C - verification passes
# Result: the verifier accepts a false statement
# The "binding" property of KZG is completely broken

This affects every PLONK variant: UltraPLONK, TurboPLONK, HyperPLONK, and every zkEVM built on PLONK (Scroll, Taiko’s PLONK mode, Aztec).

Migration path: Replace KZG with FRI. This is exactly what Plonky2 and Plonky3 do — PLONK arithmetization with FRI commitment scheme. The constraint system survives; only the commitment scheme needs replacing.

Marlin — BROKEN

Quantum vulnerability: Critical

Marlin also uses KZG. Same vulnerability as PLONK. Aleo’s production system (Marlin+) would need to migrate to a hash-based commitment scheme.

Sonic — BROKEN

Quantum vulnerability: Critical

Sonic uses KZG. Mostly a research system now, but the same analysis applies.

Bulletproofs — BROKEN

Quantum vulnerability: Critical

Bulletproofs does not use pairings or KZG — it uses Pedersen commitments and inner product arguments based on the discrete log assumption in elliptic curve groups. This is still ECDLP.

# Pedersen commitment: C = v·G + r·H
# Hiding: given C, you can't find v (discrete log hardness)
# Binding: you can't find v' ≠ v with the same C (discrete log hardness)
# Shor's algorithm breaks discrete log in elliptic curve groups
# → Pedersen commitments become non-binding under quantum attack
# → Bulletproofs range proofs become forgeable
# A quantum attacker can find v from C = v·G + r·H
# because Shor's solves: given P = k·G, find k

This is important: Bulletproofs eliminated trusted setup, but it did NOT eliminate ECDLP. No trusted setup ≠ post-quantum safe. Monero’s confidential transactions would be fully exposed under a quantum attack.

Migration path: Replace with hash-based range proofs. Several lattice-based and hash-based range proof constructions exist in the research literature but none are yet as compact as Bulletproofs.

Halo and Halo2 — BROKEN

Quantum vulnerability: Critical

A common misconception: because Halo2 uses IPA (Inner Product Argument) instead of KZG, people assume it avoids the quantum problem. It does not.

IPA security reduces to the discrete log problem in elliptic curve groups — specifically the Pasta curves (Pallas and Vesta). Shor’s algorithm breaks discrete log on Pallas and Vesta exactly as efficiently as on BN254 or BLS12–381.

# IPA commitment: uses Pedersen multi-commitment
# [f] = f_0·G_0 + f_1·G_1 + ... + f_n·G_n
# Security: computing f_i from [f] requires solving discrete log
# Shor's breaks this:
# Given [f] and G_0..G_n, compute f_0..f_n via quantum discrete log
# → the commitment is no longer binding
# → Halo2 proofs become forgeable
# This affects: Zcash Orchard, Scroll, Taiko (Halo2 mode), PSE projects

Halo2 is transparent (no trusted setup) and recursive — important properties — but it is not post-quantum safe. These are orthogonal axes.

Migration path: Replace IPA with a hash-based commitment scheme. This is a significant engineering effort. Zcash is actively researching post-quantum alternatives for Orchard.

Ligero — SAFE ✓

Quantum vulnerability: Grover only (manageable)

Ligero’s security reduces entirely to the collision resistance of the hash function used for its commitments. Under quantum attack:

• Grover halves collision-finding complexity: SHA-256 (256-bit) → 128-bit quantum security
• 128 bits of quantum security is currently considered sufficient
• No Shor-vulnerable component anywhere in the construction

# Ligero commitment: Merkle tree of evaluations
# commit(f) = MerkleRoot(SHA256(f(x_0)), SHA256(f(x_1)), ..., SHA256(f(x_n)))
# Quantum attack on SHA-256:
# Classical collision: O(2^128)
# Grover's collision:  O(2^64) per pair - NOT enough to break commitments
# (Breaking binding requires finding f' ≠ f with same root - harder than collision)
# Verdict: Ligero with SHA-256 provides ~128-bit post-quantum security
# Upgrade to SHA-512 → ~256-bit post-quantum security

Caveat: The security proof uses the random oracle model — SHA-256 is modeled as a truly random function. Known attacks on SHA-256’s structure don’t apply to ZK usage, but this is an assumption, not a proof.

Aurora — SAFE ✓

Quantum vulnerability: Grover only (manageable)

Aurora builds on Ligero’s hash-based foundation with Reed-Solomon codes and the IOP framework. Its security reduces to hash function collision resistance — no ECDLP anywhere.

The Reed-Solomon component is information-theoretic (not computational) — it’s secure even against computationally unbounded adversaries, quantum or classical.

Virgo — SAFE ✓

Quantum vulnerability: Grover only (manageable)

Virgo uses hash-based polynomial commitments over its GKR-based sumcheck protocol. Same analysis as Aurora — security reduces to hash collision resistance.

zk-STARK — SAFE ✓

Quantum vulnerability: Grover only (manageable)

STARKs are built entirely on FRI, which uses Merkle trees (SHA-256 or Keccak commitments) and Reed-Solomon codes. No elliptic curves. No pairings. No discrete log.

# STARK security assumptions:
# 1. FRI soundness: Reed-Solomon proximity — information-theoretic
# 2. Fiat-Shamir binding: hash function collision resistance
# 3. Merkle tree binding: hash function collision resistance
# Under quantum attack:
# - Reed-Solomon: unaffected (information-theoretic)
# - Hash collision resistance: 2^128 → 2^64 per Grover step
#   BUT: soundness errors multiply across FRI layers
#   Practical quantum attack requires >> 2^64 operations
# StarkWare uses 252-bit field elements + 128-bit security parameter
# Post-quantum estimate: ~100-bit security (conservative)
# Mitigation: increase query count in FRI → easy parameter adjustment
# Production STARKs (StarkNet) are considered post-quantum safe
# with appropriate parameter choices
print("STARK post-quantum security: manageable with parameter adjustment")
print("No fundamental redesign required")

Nova — BROKEN

Quantum vulnerability: Critical

Nova uses Pedersen commitments for its folding scheme — ECDLP-based. Despite being transparent and not requiring a trusted setup, Nova is not post-quantum safe.

# Nova's relaxed R1CS commitment:
# [W] = w_0·G_0 + w_1·G_1 + ... + w_n·G_n  (Pedersen multi-commitment)
# Security: discrete log in elliptic curve groups
# Shor's breaks this → Nova folding is not post-quantum safe
# SuperNova, HyperNova (as currently implemented): same vulnerability
# Exception: HyperNova variants using FRI commitments → post-quantum safe
# This is active research territory as of 2024

Plonky2 — SAFE ✓

Quantum vulnerability: Grover only (manageable)

Plonky2 uses FRI over the Goldilocks field. No elliptic curves, no pairings, no discrete log. Security reduces to:

1. FRI soundness (information-theoretic + hash)
2. Poseidon2 hash collision resistance (quantum-safe with 256-bit output)

# Plonky2 field: Goldilocks = 2^64 - 2^32 + 1
# This is NOT an elliptic curve — it's a prime field for polynomial arithmetic
# No discrete log problem involved
# Hash function: Poseidon2 (STARK-friendly hash, 256-bit output)
# Quantum attack: Grover → 128-bit quantum security
# Status: considered post-quantum safe
# Note: "Goldilocks" refers to the prime field, not a curve
# The field arithmetic has no quantum vulnerability
print("Plonky2: FRI + Poseidon2 → post-quantum safe")
print("No elliptic curves in the construction")

Plonky3 — SAFE ✓

Quantum vulnerability: Grover only (manageable)

Plonky3 inherits Plonky2’s post-quantum properties with additional flexibility. The Mersenne31 field is a prime field — not an elliptic curve — with no ECDLP-based assumptions.

The configurable hash functions (Poseidon2, Blake3, Keccak) all reduce to hash collision resistance under quantum attack.

SP1 — SAFE ✓

Quantum vulnerability: Grover only (manageable)

SP1 uses Plonky3 as its proving backend. The RISC-V ISA being proved has no cryptographic assumptions — it’s just a computation model. Post-quantum security inherits from Plonky3.

Press enter or click to view image in full size

The Migration Landscape

The quantum threat creates a clear migration story:

Immediate action needed (production systems):

Systems with long-term security requirements — privacy protocols, identity systems, cross-chain bridges — should begin migration planning now. The cryptographic community’s estimate of 10–20 years to relevant quantum computers is not a guarantee; it’s a median estimate with significant uncertainty.

The migration playbook:

KZG-based system (PLONK, Marlin, Groth16)
  → Replace KZG with FRI
  → Keep arithmetization (R1CS, PLONK gates)
  → Result: STARK-like system with same programming model
  → Example: PLONK + KZG → Plonky2 (PLONK + FRI)
IPA-based system (Halo2)
  → Replace IPA with hash-based commitment
  → Keep PLONK arithmetization and recursion
  → Result: post-quantum Halo2 variant
  → Active research: multiple teams working on this
Nova-based system
  → Replace Pedersen commitments with hash-based folding
  → HyperNova with FRI backend
  → Active research: not yet production-ready
Application layer:
  → Migrate to SP1 or Plonky3-based systems
  → No circuit rewriting required - just switch the prover

The good news: The arithmetization layer (R1CS, PLONK gates, AIR) is quantum-neutral. The vulnerability lives entirely in the commitment scheme. This means migrating from a quantum-vulnerable to a quantum-safe system is a commitment scheme swap, not a full redesign.

The bad news: Proof sizes grow significantly. Groth16’s 200-byte proof becomes a Plonky2 proof of ~100KB–1MB. For on-chain verification, this is a real cost — more calldata, more gas. The field is actively working on reducing STARK proof sizes; recursive aggregation mitigates the problem at scale.

“Harvest Now, Decrypt Later”

There is one threat that is already active, not future: harvest now, decrypt later attacks.

An adversary today can record encrypted transactions or ZK proofs and store them. When quantum computers arrive, they decrypt the stored data. For privacy-sensitive ZK applications — Zcash shielded transactions, confidential DeFi, anonymous credentials — this means data generated today is at risk in the future.

# Harvest now, decrypt later — timeline example
class HarvestAttack:
    def __init__(self):
        self.harvested_proofs = []
    def harvest(self, groth16_proof, public_inputs):
        """
        Store proof + public inputs today.
        The proof itself is public - no attack needed to collect it.
        """
        self.harvested_proofs.append({
            "proof": groth16_proof,   # 200 bytes, publicly visible
            "inputs": public_inputs,  # public
            "timestamp": "2024"
        })
        print(f"Stored proof. Total harvested: {len(self.harvested_proofs)}")
    def decrypt_later(self, quantum_computer):
        """
        In ~2035: use quantum computer to break ECDLP
        Recover the witness (private inputs) from old proofs.
        """
        for stored in self.harvested_proofs:
            witness = quantum_computer.break_groth16(
                stored["proof"],
                stored["inputs"]
            )
            print(f"Recovered private inputs from 2024 proof: {witness}")
            # This reveals: private transaction amounts, private keys,
            # identity attributes, anything proved with Groth16
# For hash-based proofs: harvest now, decrypt later doesn't work
# SHA-256 preimage is hard classically AND quantum - no future threat

For applications where long-term privacy matters, this is an argument for migrating to hash-based systems now, not in 10 years.

What to Remember from This Article

• Shor’s algorithm breaks ECDLP exponentially — this kills Groth16, PLONK, Marlin, Bulletproofs, Halo2, Nova
• Grover’s algorithm gives only a quadratic speedup on hash functions — manageable by doubling security parameters
• The vulnerability lives in the commitment scheme, not the arithmetization — migration is a commitment scheme swap
• Hash-based systems (STARK, Ligero, Aurora, Virgo, Plonky2, Plonky3, SP1) survive quantum attacks with parameter adjustments
• “Harvest now, decrypt later” is a current threat for long-lived privacy applications — don’t wait 10 years to migrate
• No trusted setup ≠ post-quantum safe — Halo2 and Nova prove this. Transparency and quantum resistance are independent properties
• The migration cost is real: proof sizes grow from ~200 bytes (Groth16) to ~100KB–1MB (STARK/Plonky2). Recursive aggregation is the engineering answer

Next up: the full grand comparison — every system, every dimension, in one place.

Article 8: Grand Comparison — Proof Size, Speed, Setup, and PQ Status for All 28 Systems

References

• Shor, P. — “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer” (SIAM 1997)
• Grover, L. — “A Fast Quantum Mechanical Algorithm for Database Search” (STOC 1996)
• NIST — “Post-Quantum Cryptography Standardization” (2024 final standards)
• Bernstein, Lange — “Post-quantum cryptography” (Nature 2017)
• Banegas et al. — “CTIDH: faster constant-time CSIDH” (2021) — class group alternatives
• StarkWare — “A Cambrian Explosion of Crypto Proofs” (blog, 2021)
• Zcash — “The Orchard Shielded Pool” (documentation, 2021)