Trail of Bits Blog
Follow
We beat Google’s zero-knowledge proof of quantum cryptanalysis
Google's Quantum AI group claimed first-gen quantum computers could break elliptic curve cryptography in 9 minutes using a zero-knowledge proof. Trail of Bits created a forged zero-knowledge proof that significantly improved Google's metrics by exploiting vulnerabilities in Google's Rust prover code. These vulnerabilities included memory safety issues and logic flaws, which Google has since patched. Trail of Bits' proof lowered the total operations to 8.3 million and qubits to 1,164, while eliminating Toffoli gates. The forged proof still passed Google's unpatched verification and was indistinguishable from a legitimate proof. Google's proof used a zero-knowledge virtual machine (zkVM) to calculate costs of quantum circuits. The zkVM simulation involves proving that a program, with private inputs like a quantum circuit, generates a specific public output which includes resource bounds. A key vulnerability involved bypassing the Toffoli gate counter by manipulating the operation type in the circuit's assembly script. This manipulation allowed the program to perform operations without correctly reporting their costs, effectively forging the proof. The incident displays the unique attack surface introduced by zero-knowledge proof systems.
