The Trail of Bits team published a result today that, on the surface, sounds like a cryptography headline. They beat Google’s zero-knowledge proof of quantum cryptanalysis. But the interesting part is not the headline; it is the specific failure mode that made it possible, because that failure mode is not unique to quantum computing or to Google.
A zero-knowledge proof has three properties: completeness, zero-knowledge, and soundness. Soundness is the one that matters here. It says a cheating prover, one who does not actually possess the witness the proof requires, cannot convince a verifier to accept. When Trail of Bits says they “beat” the proof, they mean they satisfied the verifier without holding the witness the proof was supposed to certify. That is a soundness failure, and the question worth examining is precisely what witness the proof was designed to certify in the first place.
The Distinction Between a Result and a Process
Most ZKP applications prove knowledge of a classical object. I know the discrete logarithm of this group element. I know a preimage for this hash. I know a satisfying assignment for this circuit. In each case, the witness is a value, and the soundness argument reduces to the hardness of finding that value without already knowing it.
Quantum cryptanalysis claims are structurally different. The claim is not “I know the factorization of N” but rather “I found the factorization of N using a quantum computer.” The distinction matters because classical factoring is also possible for small enough N, and even for large N, if the proof system does not correctly bind the witness to the quantum process that produced it, then anyone with the answer, regardless of how they obtained it, can generate an accepting proof.
This is what Trail of Bits found. The proof system collapsed from “proof of quantum computation” to “proof of classical verification of a known answer.” A circuit that encodes the verification of a factorization is satisfied by anyone who holds the factors. It does not encode anything about how the factors were obtained.
This failure mode has a name in the ZKP auditing community: it is the gap between the intended language and the encoded language. The circuit was supposed to be a proof of quantum computation; the actual circuit was a proof of solution possession. These are different languages, and they have different soundness properties.
Why This Is Predictable
ZKP circuits for complex computations are written by engineers who understand the intended semantics but who reason about arithmetic constraints. Converting a quantum circuit into a polynomial constraint system is a multi-step translation: quantum gates become arithmetic operations, quantum states become field elements, measurement outcomes become constraint inputs. Each translation step is an opportunity to lose something.
The specific thing that gets lost, almost universally, is process fidelity. Verification circuits check that a result is consistent with a computation, but they typically cannot verify that the computation was performed in the intended way rather than by some other method that produces the same result. For classical computations, this is usually fine; if the only known way to compute X efficiently requires a specific method, then proving you have X is tantamount to proving you used that method. For quantum computations, this assumption breaks down because the classical answer exists independently of whether quantum hardware was involved.
Trail of Bits has documented this class of bug across dozens of ZKP audits. Their Circomspect static analyzer targets Circom circuits and flags under-constrained variables, which is the technical name for the same failure: a variable that the circuit leaves underdetermined can be assigned any value by a cheating prover, allowing the proof to be satisfied without a valid witness. Under-constrained circuits are the most common serious soundness bug in deployed ZKP systems, and the quantum-specific version of this bug is structurally similar.
The Adversarial Model Problem
There is a second layer to this that makes quantum-specific ZKPs unusually hard to get right. For classical ZKPs, soundness is typically proven under assumptions like the hardness of discrete logarithm or the hardness of finding hash collisions. These are assumptions about classical adversaries. The prover is modeled as a classical probabilistic polynomial-time machine.
For a ZKP designed to certify quantum cryptanalysis, the prover has quantum resources. This creates a problem for proof systems that rely on elliptic curve pairings, which is what Groth16 and most deployed SNARK systems use. A prover with a quantum computer running Shor’s algorithm could potentially break the discrete logarithm assumption underlying the pairing and forge proofs of computations that never occurred. The ZKP system you use to certify quantum computation needs to be secure against a quantum prover, which means it cannot rely on hardness assumptions that quantum computation breaks.
This points toward STARKs and hash-based proof systems, which rely only on collision resistance. STARKs, developed by Eli Ben-Sasson and colleagues, achieve transparency without a trusted setup and their security reduces to properties of hash functions, which are conjectured to remain hard under Grover’s algorithm with doubled security parameters. The structural irony is explicit: to certify a quantum computation, you need a proof system that survives quantum adversaries, and that constraint rules out most of the efficient deployed ZKP infrastructure.
Neither existing post about this story addresses a practical follow-on question: if you use a hash-based proof system, you give up the very small proof sizes that make ZK certificates practical for broadcast. Groth16 proofs are 192 bytes; STARK proofs for comparable computations can be tens of kilobytes. For a quantum cryptanalysis certificate that might need to be published, distributed, and independently verified at scale, proof size matters. Solving for post-quantum soundness and compact proofs simultaneously is an open engineering problem.
What a Correct Solution Requires
Building a ZKP that genuinely certifies quantum computation, rather than just certifying knowledge of the computation’s output, requires encoding something about the quantum process itself in the arithmetic constraint system. This is not straightforward.
The Mahadev protocol, published in 2018, is the cleanest theoretical answer. It is an interactive protocol where a classical verifier issues challenges that force the quantum prover to commit to measurement outcomes before the measurement basis is revealed. The protocol achieves soundness against a computationally bounded quantum prover under the Learning With Errors assumption, which is believed to be post-quantum hard. The problem is that it requires multiple rounds of interaction and substantial communication overhead, making it impractical for non-interactive certification.
Converting Mahadev or similar interactive protocols to non-interactive proofs using the Fiat-Shamir heuristic is possible in principle but introduces new soundness questions in the quantum random oracle model. The QROM (quantum random oracle model) proof techniques are more demanding than their classical counterparts, and many Fiat-Shamir transformations that are sound classically do not have known QROM proofs.
The engineering path forward likely involves a combination of: tight arithmetization of quantum circuit execution that encodes the measurement process rather than just the measurement outcomes; hash-based commitments that bind the prover to circuit execution before the verifier’s challenge; and recursive proof composition to keep the final certificate size manageable. Nova and similar folding scheme approaches could be relevant here, since they enable incremental verification of sequential computation steps.
What This Changes for the Migration
NIST finalized ML-KEM, ML-DSA, and SLH-DSA in August 2024. The post-quantum migration is underway but slow. Most organizations are operating on the assumption that cryptographically relevant quantum computing is years away, and their migration timelines reflect that assumption.
A credible, independently verifiable ZK certificate of RSA or ECC factoring at meaningful key sizes would be a precise signal that the timeline has collapsed. The absence of such a certificate is not proof that quantum cryptanalysis is not happening; it might mean it is happening and the results are being kept secret. But a valid certificate would be unambiguous.
Trail of Bits showing that Google’s certificate system was unsound does not mean quantum cryptanalysis is not advancing. Google’s Willow chip, announced in December 2024, represents real progress on error correction, and the hardware trajectory is independent of whether any particular proof system was correctly constructed. What the result does mean is that the verification infrastructure, the machinery that would let a quantum lab prove capability to the world without disclosing a recovered key, has not yet been built correctly.
That infrastructure matters as much as the underlying capability, because it determines whether the cryptographic community gets a warning or gets surprised. Trail of Bits finding this flaw is worth more than the headline suggests. The harder work is building the version that does not have it.