Soundness Is the Only Thing That Matters: Trail of Bits on Google's Quantum Cryptanalysis Proof

Trail of Bits published a detailed breakdown today describing how they beat Google’s zero-knowledge proof of quantum cryptanalysis. The framing matters: they are not claiming Google’s quantum hardware is incapable of cryptanalysis, and they are not refuting the underlying cryptographic result. They beat the proof, which is a distinct and in some ways more consequential problem.

What a ZKP of quantum cryptanalysis is trying to do

Zero-knowledge proofs have three foundational properties. Completeness guarantees that an honest prover possessing a valid witness can always convince a verifier. Zero-knowledge guarantees the verifier learns nothing about the witness beyond the bare fact of its existence. Soundness is the property that closes the system: a cheating prover, one who does not actually hold a valid witness, cannot produce a proof the verifier will accept.

Soundness is what makes a ZKP mean anything. A proof system without it is just an elaborate theater. The verifier sees a valid transcript and has no way to know whether the prover did the work or not.

When Google claims quantum cryptanalysis via a ZKP, the intended meaning is: “our quantum computer broke cryptographic primitive X, and we can prove this without revealing X itself.” The ZKP lets Google demonstrate the capability without handing over a factored RSA key or a recovered private key, which would obviously be damaging. The witness in this context is the cryptographic secret: the factorization, the discrete logarithm, whatever Google’s circuit solved.

For that proof to be meaningful, it needs to be sound against a classical adversary. Specifically, it should be infeasible for a classical computer to generate an accepting proof without actually knowing the witness. If a classical machine can forge a convincing proof, the ZKP no longer tells you whether quantum computation happened. It just tells you that someone ran a verifier.

Why this property is subtle for quantum computation claims

Most ZKP applications prove membership in an NP language: I know a satisfying assignment for this circuit, I know a discrete log for this group element, I know a preimage for this hash. The witness is a classical object, and the soundness argument reduces to the hardness of finding that object without knowing it in advance.

Quantum advantage claims introduce a structural complication. The statement is not just “I know X” but something closer to “I found X using a process that a classical computer cannot efficiently replicate.” The witness is still a classical value, but the proof of quantum advantage requires capturing something about how the witness was obtained, not just that it was obtained.

This is where ZKP circuits for quantum claims tend to leak. A circuit that encodes “I know a factorization of N” proves exactly that, regardless of how the factorization was found. If N is small enough that classical factoring is feasible, or if the ZKP’s constraint system has a soundness flaw that allows cheating without a witness at all, then satisfying the verifier says nothing about quantum hardware.

Trail of Bits, whose cryptography group has broken ZKP implementations in Groth16-based systems and audited constraint systems across dozens of projects, found a path to satisfy Google’s verifier without going through the quantum computation the proof was meant to certify.

The mechanics of a soundness attack

The common failure modes in ZKP systems are well-documented. Trusted setup vulnerabilities allow anyone who recovers the toxic waste from a powers-of-tau ceremony to forge arbitrary proofs; this is why ceremonies like Zcash’s Sapling MPC and Ethereum’s KZG ceremony involve hundreds of participants, so that a single party would need to compromise all of them. Constraint system incompleteness allows a prover to satisfy a circuit with values that do not correspond to any valid witness in the intended language. Range check omissions let provers substitute out-of-range values that satisfy the polynomial constraints without satisfying the semantic intent.

For quantum-specific ZKPs, there is an additional failure mode: the circuit encodes the verification of a classical result rather than the quantum process that produced it. If I give you the answer to a hard problem and ask you to verify it, the verification circuit proves nothing about how the answer was found. A ZKP over a verification circuit lets anyone with the answer, quantum computer or not, generate a valid proof.

This distinction between proving knowledge of a solution and proving quantum computation of a solution is not pedantic. It is precisely the gap Trail of Bits appears to have exploited. The specifics are in their post, but the structure of the attack is recognizable: find the point at which the proof system collapses from “proof of quantum computation” to “proof of classical verification of a known answer,” then produce that verification.

What this does and does not imply

This result does not mean Google’s quantum hardware cannot perform cryptanalysis. Willow, Google’s 105-qubit chip announced in December 2024, demonstrated meaningful progress on below-threshold error correction, which is the prerequisite for fault-tolerant quantum computation at cryptographically relevant scale. The hardware trajectory has not changed because a proof system was flawed.

What the result does imply is that the ZKP Google used to certify the cryptanalysis was not a valid certificate. It verified without the computation it was meant to certify. That is a significant claim in itself, because ZKP-based certification is precisely the mechanism that was supposed to make quantum cryptanalysis claims auditable without the defender needing access to the quantum hardware.

For the post-quantum cryptography community, the immediate practical implications are limited. NIST finalized ML-KEM (FIPS 203), ML-DSA (FIPS 204), and SLH-DSA (FIPS 205) in 2024. The migration from RSA and elliptic curve cryptography to lattice-based and hash-based schemes does not depend on quantum computers having already broken anything; it depends on the reasonable expectation that they eventually will. That expectation is unchanged by a flawed proof.

But the result matters methodologically. If quantum cryptanalysis ever advances to the point where it threatens real-world key sizes, the cryptographic community will need a trustworthy way to verify those claims. ZKPs are the obvious candidate: they would let a quantum lab prove capability without handing over a recovered key. Trail of Bits has now demonstrated that designing such a proof correctly is a hard problem that the current approaches have not solved.

Why Trail of Bits is positioned to find this

Trail of Bits has spent years building tooling for ZKP circuit auditing. Their Circomspect static analyzer flags common constraint system bugs in Circom circuits. Their work on Weierstrass curve implementations and Bulletproofs has repeatedly shown that ZKP security proofs in papers do not automatically translate to correct implementations. Their team includes people who think in terms of algebraic constraint satisfaction and polynomial identity testing, which is exactly the lens needed to find gaps between a ZKP’s intended semantics and its actual constraint system.

A ZKP that claims to prove quantum cryptanalysis is, from Trail of Bits’ perspective, just another constraint system to audit. The exotic framing, quantum computers, cryptanalysis, Google, does not change the underlying problem: does the circuit correctly encode the statement it is supposed to prove, and is the proof system sound against a cheating prover with classical resources?

The answer, in this case, was no. That is worth understanding carefully, both for how quantum advantage claims get made and verified, and for the harder problem of building certification infrastructure that will actually hold when quantum cryptanalysis eventually becomes real.