Proving the Unverifiable: ZK Proofs for Quantum Cryptanalysis and Why the Competition Matters

The Trust Problem Nobody Talks About

When a quantum computer eventually runs Shor’s algorithm on RSA-2048 and factors the modulus, the field of applied cryptography will face two simultaneous crises. The first is obvious: the cryptographic primitive is broken. The second is less discussed and in some ways harder: how does anyone else verify the claim?

You cannot simply publish the factors. Publishing factors of a 2048-bit semiprime would be proof on its own, but in many threat scenarios, the attacker benefits from secrecy. You cannot replay the quantum computation classically; that is the entire point. You cannot easily send the quantum hardware to a third party for independent verification. What you need is a way to certify a quantum computation to a skeptical classical verifier, and that is the problem that zero-knowledge proofs are now being applied to.

Trail of Bits recently published their result beating Google’s ZK proof for quantum cryptanalysis, which is a meaningful result in a narrow but consequential area. To understand why it matters, you need to understand both the verification problem and the specific difficulties of applying ZK proofs to quantum circuits.

ZK Proof Systems: A Brief Map

Modern ZK proof systems fall into two broad families. SNARKs (Succinct Non-interactive Arguments of Knowledge) produce very small proofs, typically 200 bytes or fewer for Groth16 and around 500 bytes for PLONK, but many variants require a trusted setup ceremony. STARKs (Scalable Transparent Arguments of Knowledge) require no trusted setup, use hash functions as their only cryptographic primitive, and are considered post-quantum secure, but their proofs are significantly larger, often tens to hundreds of kilobytes depending on the computation.

The trusted setup distinction matters here. Groth16, introduced by Jens Groth in 2016, is the workhorse of most deployed ZK systems. Its proofs consist of just three elliptic curve group elements. But its circuit-specific trusted setup means that if the setup is compromised, soundness fails entirely. PLONK, published by Gabizon, Williamson, and Ciobotaru in 2019, uses a universal trusted setup that works for any circuit up to a given size, which makes it more practical for systems that update circuits frequently.

For quantum computation verification specifically, the choice between these families carries extra weight. A SNARK for quantum circuit execution that relies on elliptic curve pairings is only classically secure; a sufficiently large quantum computer running Shor’s algorithm could potentially forge proofs if it could break the underlying discrete log assumption. A STARK, by contrast, relies only on collision-resistant hash functions, which remain post-quantum secure under Grover’s algorithm with doubled security parameters. This is a structural irony: you want to build a ZK proof that survives the quantum regime, to certify computations performed on quantum hardware that could break the proof system you are using.

Why Quantum Circuits Are Hard to Arithmetize

Every ZK proof system works by arithmetizing a computation: converting it into a set of polynomial constraints over a finite field, then generating a proof that those constraints are satisfied. For classical boolean circuits, this is well-understood. Each AND gate, XOR gate, and NOT gate maps to a simple low-degree polynomial identity. A 100,000 gate circuit becomes a polynomial system of comparable size, and the whole machinery of FRI commitments or KZG commitments handles the proof generation efficiently.

Quantum circuits break these assumptions at the foundation. A quantum circuit on n qubits operates in a Hilbert space of dimension 2^n. A 50-qubit intermediate state is a superposition of 2^50 basis states, each with a complex amplitude. Encoding that state naively into field elements is exponentially expensive. You cannot checkpoint mid-computation and write out the state without destroying the quantum superposition.

Several approaches exist to work around this. The Mahadev protocol from 2018 provides classical verification of quantum computations using Learning With Errors (LWE) assumptions. The prover commits to measurement outcomes using a homomorphic hash function derived from LWE, then the verifier challenges with a basis choice that the prover must respond to consistently. The protocol achieves soundness against a computationally bounded quantum prover but requires multiple rounds of interaction.

Stabilizer circuit decompositions offer another route. Clifford circuits, those built exclusively from Hadamard, CNOT, and phase gates, can be simulated efficiently on a classical computer via the Gottesman-Knill theorem. A quantum circuit that factors an integer using Shor’s algorithm is not a pure Clifford circuit, but it can be decomposed into a Clifford part plus a bounded number of T-gate injections. Each T-gate roughly doubles the simulation overhead, but for circuits with modest T-count relative to their Clifford complexity, this decomposition makes ZK proof generation tractable. The magic state model of quantum computation makes this decomposition systematic.

Tensor network methods are a third avenue. Circuits with limited entanglement admit efficient classical description as matrix product states. For verification purposes, you do not need to represent the full quantum state; you need to prove specific output statistics are consistent with the circuit having been executed. Tensor contractions over low-entanglement subgraphs of the quantum circuit can be efficiently arithmetized.

What Google Built and What Trail of Bits Improved

Google’s quantum team has been in the ZK proof space for a while, motivated by the quantum supremacy problem. Their 2019 Sycamore result used cross-entropy benchmarking (XEB) as a verification method: run the same random circuit on the quantum processor and classically, compare the output distributions, and measure how closely they match. XEB is efficient but it is not a cryptographic proof; Gao and Duan showed in 2018 that XEB can be spoofed under certain conditions, and subsequent work from Aaronson and Gunn in 2019 clarified the precise conditions under which spoofing is and is not possible.

A genuine ZK proof, rather than statistical benchmarking, would be much stronger. Google’s effort in this direction applies ZK techniques to certifying the output of specific quantum cryptanalytic subroutines, particularly the quantum period finding at the core of Shor’s algorithm. The arithmetization strategy used representations of quantum states through their action on Clifford group elements, exploiting the structure of the quantum Fourier transform to limit the number of non-Clifford operations that need to be verified.

Trail of Bits’ improvement comes on at least two axes that are standard competitive metrics in ZK proof research: proof size and verification time. A smaller proof means less bandwidth and storage overhead for distributing a certificate of quantum cryptanalytic success. Faster verification means the classical party can check the proof with commodity hardware in reasonable time. Trail of Bits has a documented track record of ZK circuit optimization, and their work on constraint systems for Groth16 and PLONK through audit engagements has given them deep familiarity with where arithmetic circuit representations waste constraints.

The specific gains likely come from a tighter arithmetization of the period-finding subproblem. Shor’s algorithm has a well-characterized gate complexity. For factoring an n-bit integer, the quantum circuit requires O(n^3) gates in the standard textbook presentation, though more optimized implementations like Beauregard’s 2002 circuit bring this down substantially. The key insight for ZK proofs is that you do not need to prove the entire circuit executed correctly; you need to prove that the classical post-processing of measurement outcomes is consistent with a valid quantum period-finding execution. That is a weaker but still cryptographically meaningful statement, and it is much cheaper to prove.

The Soundness Question

Proof size and verification time are the obvious metrics, but soundness is the harder one to reason about, and it matters most for quantum cryptanalysis specifically.

A ZK proof system is sound if no cheating prover, even a computationally unbounded one in the information-theoretic setting, can convince a verifier of a false statement except with negligible probability. For SNARKs, soundness is computational: it holds against bounded adversaries under specific hardness assumptions. For STARKs, soundness is information-theoretic in the random oracle model, which is a stronger guarantee.

For quantum cryptanalysis certificates, the soundness model has an unusual structure. The prover has access to quantum hardware. If the ZK proof system’s soundness relies on assumptions that quantum hardware could break (like elliptic curve discrete log), then a sufficiently capable quantum prover can forge certificates of computations it never performed. This would undermine the entire point of the verification scheme.

A ZK proof for quantum cryptanalysis that is itself quantum-insecure is therefore deeply problematic. Trail of Bits’ work appears to use a hash-based commitment scheme, avoiding pairing-based assumptions. This matters. If the proof system survives in the same adversarial environment where quantum cryptanalysis operates, certificates issued today remain meaningful as quantum hardware scales.

The analogy in classical security is certificate transparency: a system for making TLS certificate issuance auditable. Certificate transparency works precisely because the logs use hash-based Merkle trees, not signatures under a single CA key. The security assumption is collision resistance, not the CA’s private key remaining uncompromised. A quantum cryptanalysis certificate that uses similarly conservative assumptions has the same character: its trust comes from structural properties, not assumptions about secret material.

Why This Matters for the Migration

The NIST post-quantum cryptography standards finalized in August 2024 give organizations ML-KEM (CRYSTALS-Kyber), ML-DSA (CRYSTALS-Dilithium), and SLH-DSA (SPHINCS+) as primary alternatives. The migration from RSA and elliptic-curve Diffie-Hellman to these lattice and hash-based systems is underway but nowhere near complete. Most public-facing TLS deployments have not yet made the switch; most internal enterprise PKI infrastructure has not either.

The migration decision involves a timing question that ZK proofs for quantum cryptanalysis directly inform. Organizations need to know when classical cryptography becomes practically vulnerable. That answer depends on quantum hardware maturity, which is notoriously difficult to assess from outside the laboratories. Cross-entropy benchmarking results are easy to publish but hard to interpret in terms of real cryptanalytic capability. A credible ZK certificate of successful factoring of a meaningful key size would be a precise, verifiable signal that the transition is urgent.

It would also remove any plausible deniability for organizations that have delayed migration. Once a ZK proof of RSA-1024 factoring circulates and verifiers can check it in under a second on a laptop, the question shifts from “has anyone broken it?” to “when will they break my key size?” The existence of a credible verification mechanism changes the incentive structure for disclosure and creates audit trail infrastructure for tracking quantum cryptanalytic capability.

For security tooling, the practical implication is that the ZK proof generation side of this problem needs to live close to quantum hardware vendors. A quantum cloud provider that can attest the results of cryptanalytic computations via succinct ZK proofs has a significantly more credible threat model to present to customers than one that only offers raw measurement outputs and XEB scores. Trail of Bits building better tooling in this space positions them well for that market.

The Broader Competition

ZK proof performance has improved dramatically over the past five years. Proof generation times that once required minutes on a GPU cluster now run in seconds on commodity hardware for many applications. Recursive proof composition, the ability to generate a proof of a proof, has made it possible to aggregate large computations into constant-size certificates. Nova, Halo2, and Plonky2 all represent meaningful advances in the past three years.

Applying this toolchain to quantum circuit verification is genuinely new territory, and the fact that Trail of Bits and Google are both working in this space suggests the problem is now tractable enough to produce competitive results. The race to build better ZK proofs for quantum cryptanalytic certification is, in a sense, a race to build the audit infrastructure for a coming capability threshold. Whoever gets there first with a sound, efficient, post-quantum-secure proof system owns the most credible attestation layer for one of the most consequential events in the history of applied cryptography.

That is worth paying attention to.