up:: Foundations MOC

Zero-Knowledge Proofs

A zero-knowledge proof (ZKP) is a way for one party to convince another that a statement is true while revealing nothing beyond the fact of its truth. You can prove you know a password without sending it, prove a transaction is valid without exposing the amounts, or prove a whole computation ran correctly without re-running it. The quantum question does not have one answer for the whole family, because it splits cleanly by how the proof is built. Hash-based proofs called STARKs rest only on a hash function and are post-quantum secure, while many of the most popular succinct proofs, the pairing-based SNARKs like Groth16, rest on the elliptic-curve discrete logarithm problem and are broken by Shor’s algorithm. Knowing which kind a system uses tells you whether its proofs survive the transition.

Source: E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive 2018/046, IACR.

The short version:

• A zero-knowledge proof proves a statement is true and leaks nothing else, satisfying three properties: completeness (true statements verify), soundness (false ones do not), and the zero-knowledge property (the verifier learns only the truth value).
• The two dominant families are SNARKs (succinct, tiny proofs, often needing a trusted setup) and STARKs (larger proofs, no trusted setup, transparent).
• The quantum split runs along the math underneath. Hash-based STARKs rest only on a hash function and are post-quantum secure.
• Many popular SNARKs, Groth16 and KZG-based PLONK, are pairing-based, so they rest on the elliptic-curve discrete logarithm problem and Shor’s algorithm breaks them.
• For long-lived, quantum-safe verifiable computation, the move is toward hash-based STARKs and lattice-based proof systems, away from pairing-based SNARKs.

Picture a friend who is colorblind holding two balls, one red and one green, that look identical to them. You want to prove the balls really are different colors without telling your friend which is which. They hide both behind their back, show you one, then either swap them or not before revealing again, and you say whether they swapped. If the balls were truly identical you would be guessing and would fail half the time, but because you can see the colors you call it right every single round. After enough rounds your friend is convinced the balls differ, yet they never learn which ball is red. That is a zero-knowledge proof: certainty about the statement, and nothing about the secret behind it.

What is a zero-knowledge proof?

A zero-knowledge proof is a protocol between a prover and a verifier in which the prover convinces the verifier that some statement holds, without conveying any information apart from the statement’s truth. The concept was introduced by Goldwasser, Micali, and Rackoff in the 1980s, and every zero-knowledge proof is defined by three properties working together:

1. Completeness. If the statement is true and both parties follow the protocol, an honest verifier is convinced.
2. Soundness. If the statement is false, no cheating prover can convince the verifier except with negligible probability. This is the property that keeps a proof from being forged.
3. Zero-knowledge. The verifier learns nothing beyond the fact that the statement is true, so the proof reveals no part of the secret, the witness, that made it true.

Source: E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive 2018/046, IACR.

Modern zero-knowledge proofs are usually non-interactive, meaning the prover produces a single self-contained proof object that anyone can check later without a back-and-forth. They have become the engine behind privacy-preserving cryptocurrencies, validity rollups that scale blockchains by proving a batch of transactions ran correctly, and private authentication systems. The security of that whole edifice, whether it survives a quantum computer, depends entirely on the cryptographic assumption the specific proof system is built on, which is where the family divides.

What are the main kinds of zero-knowledge proof?

Two families dominate real deployments, and the split between them decides both their practical tradeoffs and their quantum fate. The distinction is worth holding precisely, because the marketing names sound similar while the math underneath is different.

1. SNARKs (Succinct Non-interactive Arguments of Knowledge). These produce extremely small proofs that verify very fast, which is why they became the default for on-chain use. The catch is that the most efficient SNARKs, Groth16 chief among them, are pairing-based and require a trusted setup ceremony to generate their public parameters. Their succinctness comes from a pairing-product check, and that pairing dependency is exactly what makes them quantum-vulnerable.
2. STARKs (Scalable Transparent Arguments of Knowledge). These use no number theory at all. A STARK’s soundness rests only on the collision resistance of a hash function plus an error-correcting-code construction, which means no trusted setup (transparent) and no discrete-log or pairing assumption to break. The cost is larger proof sizes than a SNARK, the price of dropping the structured-math dependency.

Source: J. Groth, “On the Size of Pairing-based Non-interactive Arguments,” Cryptology ePrint Archive 2016/260, IACR.

The naming can mislead, because “SNARK” is sometimes used loosely for any succinct proof, and a handful of newer SNARK constructions are hash-based rather than pairing-based. What decides quantum safety is never the acronym. It is whether the proof’s soundness rests on a hash function or on a number-theoretic problem like the discrete logarithm problem, which is the question the next section answers.

Are zero-knowledge proofs quantum-safe?

It depends on the construction, and this is the single most important thing to carry out of the note: a zero-knowledge proof is quantum-safe if and only if it rests on quantum-hard math, which the hash-based ones do and the pairing-based ones do not. The verdict tracks the assumption underneath:

1. Hash-based STARKs are post-quantum secure. A STARK’s soundness comes only from the security of a hash function. Hash functions face only Grover’s algorithm, a quadratic search speedup that a wide digest absorbs, so there is no structured problem for Shor’s algorithm to attack. STARKs were designed with post-quantum security as an explicit goal.
2. Pairing-based SNARKs are quantum-broken. Groth16 and KZG-based PLONK rest on the elliptic-curve discrete logarithm problem inside pairing-friendly groups, the exact problem Shor’s algorithm solves in polynomial time. A quantum attacker recovers the trapdoor behind the trusted setup and can then forge proofs of false statements, defeating soundness.

Source: E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive 2018/046, IACR.

The consequence of a broken SNARK is worth stating plainly, because it is worse than a privacy leak. If Shor’s algorithm defeats the soundness of a pairing-based proof system, an attacker can produce a valid-looking proof of a false statement. On a validity rollup that means proving a fraudulent state transition, which could let the attacker drain assets the honest system never held. The zero-knowledge property protects secrecy, and soundness protects correctness, and it is the correctness guarantee that a quantum-broken SNARK loses.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, SIAM.

Why do STARKs survive when pairing-based SNARKs fall?

The difference is the assumption each one leans on. A pairing-based SNARK buys its tiny proof size by embedding an elliptic-curve pairing, and that pairing carries the elliptic-curve discrete logarithm problem with it, a structured number-theoretic problem with the hidden periodicity Shor’s algorithm is purpose-built to find. When Shor’s collapses that discrete logarithm, the SNARK’s soundness collapses with it, the same fate that ends pairing-based signatures and ordinary elliptic-curve cryptography.

A STARK is built on a hash function and an error-correcting code, with no number theory anywhere in its soundness argument. Factoring, the discrete logarithm, and pairings are all absent, so nothing structured is left for a quantum computer to exploit, and the strongest quantum attack available is Grover’s algorithm, which only speeds up brute-force search quadratically. That mild pressure is handled by using a wide-enough hash digest, so a STARK’s post-quantum security is a design property rather than a hope. This is the same logic that keeps SHA-256 and hash-based signatures standing through the transition.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, NIST.

What should teams using zero-knowledge proofs do about quantum?

The practical work is to identify which proof systems are in play and route the pairing-based ones toward hash-based or lattice-based replacements before a quantum computer forces the issue. The steps that matter:

1. Inventory the proof systems alongside the ciphers. A cryptographic inventory that catches RSA and ECDSA can still miss a Groth16 verifier or a PLONK circuit, because those are pairing-based and hide under proof-system names rather than algorithm names.
2. Classify each system by its assumption. Pairing-based (Groth16, KZG-based PLONK, and their kin) is quantum-broken. Hash-based (STARKs, and hash-based SNARK variants) is post-quantum secure. Lattice-based proof systems are an emerging post-quantum option. The assumption, not the acronym, is the verdict.
3. Sequence the migration by exposure. A pairing-based proof whose soundness guards long-lived value, a rollup bridge or a settlement layer, is a real-time forgery risk the moment a capable quantum computer exists, so it belongs early in the plan.

Source: E. Ben-Sasson, I. Bentov, Y. Horesh, M. Riabzev, “Scalable, transparent, and post-quantum secure computational integrity,” Cryptology ePrint Archive 2018/046, IACR.

The move toward hash-based and lattice-based proofs is a tradeoff, usually paying larger proof sizes for a foundation a quantum computer cannot dismantle, and building that swap in cleanly is exactly what crypto-agility is for. The comparison across the family:

Proof family	Example	Rests on	Trusted setup	Quantum verdict
Pairing-based SNARK	Groth16, KZG-PLONK	EC discrete log	Usually required	Broken by Shor’s
Hash-based STARK	STARK	Hash function	None (transparent)	Post-quantum secure
Lattice-based proof	(emerging)	Lattice hardness	Varies	Post-quantum candidate

Common misconceptions

• “All zero-knowledge proofs are quantum-safe because they hide information.” Hiding information (the zero-knowledge property) is separate from resting on quantum-hard math (soundness). Pairing-based SNARKs hide information yet are quantum-broken, while hash-based STARKs are quantum-safe.
• “SNARKs and STARKs are basically the same thing with a different letter.” The letter change marks a different foundation. SNARKs are often pairing-based and quantum-vulnerable, while STARKs are hash-based and post-quantum secure.
• “A quantum computer breaking a SNARK just leaks the private data.” It defeats soundness, which is worse. An attacker can prove a false statement, so on a rollup they could validate a fraudulent transaction rather than merely read a hidden one.
• “Zero-knowledge means the proof itself can never be forged.” Forgeability is the soundness property, and soundness rests on a cryptographic assumption. If that assumption is the discrete logarithm, Shor’s algorithm makes forgery feasible.
• “Groth16 is safe because it’s the standard for on-chain proofs.” Wide adoption says nothing about quantum resistance. Groth16 is pairing-based, so it is quantum-broken, which is why long-horizon systems are looking at hash-based STARKs.

Questions people ask

Are zero-knowledge proofs quantum-safe? Some are and some are not. Hash-based STARKs rest only on a hash function and are post-quantum secure, while pairing-based SNARKs like Groth16 rest on the elliptic-curve discrete logarithm problem and are broken by Shor’s algorithm. The construction decides the answer.

Is a zk-STARK post-quantum secure? Yes. A STARK’s soundness comes only from the security of a hash function, which faces just Grover’s mild quadratic speedup and no Shor-style break, so STARKs were designed to be post-quantum secure from the start.

Are zk-SNARKs broken by quantum computers? The pairing-based ones are. Groth16 and KZG-based PLONK rest on the elliptic-curve discrete logarithm, which a quantum computer solves, letting an attacker forge proofs. A few newer SNARK constructions are hash-based instead, so the assumption underneath, not the SNARK label, is what matters.

What does it mean for a proof system to be broken by quantum? It means an attacker can defeat soundness and produce a valid-looking proof of a false statement. That is a correctness failure: on a validity rollup it could authorize a fraudulent state change, which is more damaging than a leak of hidden data.

Which zero-knowledge proof should I use for long-term security? For workloads that must stay trustworthy past a quantum computer’s arrival, hash-based STARKs are the quantum-safe choice today, with lattice-based proof systems maturing as an alternative. Pairing-based SNARKs buy smaller proofs at the cost of a quantum-vulnerable foundation.

Do I need to inventory zero-knowledge proofs in a migration? Yes, because a pairing-based proof system will not show up in a scan as RSA or ECDSA. It shows up as Groth16, PLONK, or a rollup circuit, and a cryptographic inventory has to reach that layer to catch it.

---

Everything here is the map, given freely. When your team needs its own proof systems sorted into what survives the quantum transition and what has to move, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.