okay here’s a nerdy bug thing idk.
So two weeks ago, google announced a quantum circuit so optimised it can break most elliptical key crypto things in about 9 minutes. This research group then found memory safety bugs in the code google used to prove this result, and used that to develop a much better circuit. Lmao.
Google used a “zero-knowledge virtual machine” (zkVM) to calculate the cost of a quantum circuit such as total number of operations, total number of qubits and so on.
This group have forged an improvement. Hah.
A zkVM is a way to prove that you know which private inputs for an arbitrary guest program generate some public output.
Okay so for an example, say the guest program added two numbers (the private inputs) together and told you the result (the public output). A user can run this program with 2 and 3 and get a proof that the result was 5. Anyone else can verify the proof, but would gain zero knowledge (eyyy) about whether the inputs were 2, 3 or 1,4 or 0 and 0xffffffffff. I seeeee kinda.
This works in practice by compiling down to RISC-V ELF binary, because then the operations on the registers and so on are deterministic functions of their state before hand, and we can reason about that. CompSci has gotten good at this, and we can now prove things about complex programs.
In this case, the private input is some description of a quantum circuit and the guest program is a simulator that checks it. The public output includes bounds on gate number and so on. “kickmix” circuits are a subset of all possible quantum circuits, and “kickmix” circuits can be simulated classically.
The simulator effectively does a monte-carlo simulation of the quantum circuit, iteratively applying the steps of the circuit to random input. it panics if the output is wrong. The “proof” then is of correctness with a high probability.
The input circuit here is to compute one elliptic curve point addition, which is a critical subroutine of Shor’s algorithm. It also checks bounds on the number of gates and such.
So the attack target is things like deserialization bugs when parsing the kickmix circuit, and any logic bugs in the simulator. If they can find a circuit that verifies to be better than googles by taking advantage of these, then it still works as a quantum circuit (passes the proof) it just might be better.
you know what the more i read of this more it sounds like we have a strong case of computer science brain.
Yeah so they bypass one of the constraint counters, but that doesn’t mean their circuit is any better, just that it isn’t being marked? When you build it it still has the things you want to minimize, its just the checker didn’t find them. What good is that?
Okay yea ur very clever and forged this circuit but like… for aught.
HAHAHAHA “it turns out that programming a quantum computer is way more challenging than i anticipated”
Okay yeah they found another bug that basically means that they can trick the solver into ignoring a key constraint and then do what they like. So the circuit they make is useless, quantumly!! It just passed the same solver because that solver had memory safety bugs. that’s so boring. wtf. get over yourself.
okay but one cool thing is by doing this work they read enough prior literature to kinda work out what googles secret encryption breaking circuit was doing. that’s good at least.