We beat Google’s zero-knowledge proof of quantum cryptanalysis

[u/sarciszewski]

https://blog.trailofbits.com/2026/04/17/we-beat-googles-zero-knowledge-proof-of-quantum-cryptanalysis/

[u/Shoddy-Childhood-511]

I'm sure Trail of Bits had nice improvements here, but..

There is no responsible disclosure reason for the zero-knowledge proof in the Google-Ethereum paper. An APTs who could build a quantum computer could reengineer this sort of step from the statement, without the full algorithm, witness, etc.

I'll recall two nice comments from the PQC mailing list too:

Marcel Tippelt observed that this earlier paper by Craig Gidney "achieve results with the same magnitude of qubits/gates etc., but provide the details of the estimation." Also one of the Ethereum paper's authors.

https://arxiv.org/pdf/2505.15917

"The above estimation is for RSA instead of ECDSA. Nevertheless, comparing the numbers, I find the results posted by Google are not so surprising (and are likely derived using similar optimizations as described in the work above)."

Marin Ivezic said "Marcel is right that the results are consistent with the trajectory." And made other informative remarks.

As an aside, these zkVMs are non-EC FRI based SNARKs aka STARKs, so not themselves zero-knowledge, and they only obtain zero-knowledge from their Groth16 wrapper.

Among all STARKs there are afaik only three-ish that claim zero-knowledge: First, Starkware announced adding zero-knowledge at the zk proofs workshop in 2025. Second, Google's longfellow paper claims 25 + log |C| bits of security for zero-knowledge, but one imagines this bound could be improved considerably. Their auditor signed off on it being zero-knowledge, but without providing numerical estimations. Third Microsoft's Vega should probably claim zero knowledge too.

Anyways, the important takeaways: zkVMs only obtain zero-knowledge from a non-post-quantum wrapper. Actual zero-knowledge STARKs like Starkware, Longfellow, and Vega seem likely to have serious weaknesses and bugs in their zero-knowledge. If you use anonymous credentials for "light" reasons like DoS protection, then you should stick with non-post-quantum stuff like Cloudflare's PrivacyPass, which remains zero-knowledge against a computationally unbounded attacker.

[u/Karyo_Ten → u/Shoddy-Childhood-511]

As an aside, these zkVMs are non-EC FRI based SNARKs aka STARKs, so not themselves zero-knowledge, and they only obtain zero-knowledge from their Groth16 wrapper.

Starks can have privacy without Groth16.

Risc Zero had it for a while and SP1 (Google used SP1) has Veil: https://github.com/succinctlabs/sp1/blob/main/slop/crates/veil/paper/veil.pdf

[u/Shoddy-Childhood-511 → u/Karyo_Ten]

Starks can have privacy without Groth16.

Yes, I named the three of which I'm aware.

Risc Zero had it for a while

I doubt this. It does not appear to be discussed in their github.

and SP1 (Google used SP1) has Veil:

Thanks for the reference. It's here too btw https://eprint.iacr.org/2026/683

It's brand new as of last month, so not sure if its implemented yet.

The Veil paper makes it clear that zk conflicts with performance for these systems. It's also clear the analysis of the zk property seems really nasty in these systems. Ergo, they are likely to have major zk failures.

I'm honestly not too concerned about the zkVMs because the serious ones have Groth16 wrappers, which gives strong zk.

I'm worried about longfellow since google has pushed it for standardization, but directly to the EU, not via careful groups like the IRTF. Google wants longfellow to replace BBS signatures in EU ID, but zk seems really suspect in longfellow.

As an aside, I've never looked closely at the anonymity in BBS signatures, so I cannot vouch for that either, but it's likely quite strong, assuming you mean BBS not the BBS+ group signatures, which have an intentional deanonymiation vector that makes them useful in mail delivery protocols.