The French have the Quantum Circuits
The French have the Quantum Circuits
01 Jun 2026
MathJax was blocked.<br>Formulas like $\frac{a}{b}$ won't render into .
Allow scripts from algorithmicassertions.com and mathjax.org to fix.
Almost exactly one year ago, I found a way to make quantum attacks on elliptic curve cryptosystems ten times cheaper.<br>Specifically, I found a better way to perform elliptic curve point addition on a quantum computer.<br>I wanted to publish these improved point addition circuits, to enable cryptographers to make informed decisions about when they’d need to transition away from quantum-vulnerable cryptosystems.<br>I’ve done this several times over the past decade.<br>However, this time, something new happened: I got pushback on publishing.
The estimated cost of quantum attacks has plummeted over the past decade.<br>It seems possible that cryptographically relevant quantum computers (CRQCs) could exist within years.<br>Now, to be clear, I don’t think that’s likely (as in >50% chance).<br>But it’s possible (as in >10% chance), and if your job is security then that’s dispositive.<br>Anyways, a short timeline is really inconvenient, because it means some companies (especially hardware companies) could fail to transition in time.<br>Consequently, in a short CRQC timeline world, releasing information about quantum attacks might be a bad idea.<br>It might help attackers more than defenders.<br>And the sheer scale of the problem makes traditional disclosure mechanisms questionable.
Eventually, a compromise was reached.<br>Instead of publishing the details of the point addition circuits, we’d publish zero knowledge proofs (ZKPs) that they existed.<br>This would provide defenders the information they need for planning, without providing attackers the information they need for attacking.<br>I have to admit, it wasn’t very hard to convince me to go the ZKP route.<br>I think zero knowledge proofs are cool as fuck and I’ve always wanted to publish one.
In March 2026, we published the paper with the zero knowledge proofs.
…but we didn’t expect the proofs to survive the year.
Secrets Revealed
The problem with secrets is that, like lies, they’re contagious.<br>To keep one secret, you have to keep another.<br>Elliptic curve circuits are built out of the same basic ingredients as other circuits: adders, multipliers, table lookups, and so forth.<br>This commonality means that techniques used to improve one circuit inevitably improve another.
The most expensive thing that happens during a quantum elliptic curve point addition is a multiplication (a quantum-quantum inplace modular multiplication, to be specific).<br>Multiplication is also a key cost in an algorithm called Decoded Quantum Interferometry (DQI).<br>Four months earlier, we’d published a paper on DQI that explained a new technique for making multiplication more space efficient…<br>are you seeing the glaring problem?<br>We knew that all anyone had to do, to unmask our ZKPs, was read over our prior papers and put two and two together.
Today, almost exactly two months after we published the ZKPs, André Schrottenloher<br>(a researcher at le Centre Inria de l’Université de Rennes in France)<br>published a preprint showing how to construct circuits with similar costs to ours.<br>He read our prior papers, and he put two and two together.<br>The exact details of his construction are a bit different, but the key ideas are the same.
My congratulations to André on being the first to match our circuits.<br>Not only did he get it done in two months, he improved the Toffoli count a little bit!<br>Seriously, congratulations.
The Problem with ZKPs
Even if the key ideas hidden behind the zero knowledge proofs weren’t betrayed by our prior papers, I wouldn’t have expected the secrets to last any substantial amount of time.<br>I wanted to try the experiment, but there are clear reasons to expect ZKPs to fail for this use case in the future.<br>Here’s three big ones.
The first big problem with sharing research by ZKP is the Streisand effect.<br>Saying you have a solution, but that you won’t share it, is a great way to draw attention.<br>Compared to computer science as a whole, or even to just cryptography, quantum computing is a tiny field.<br>Drawing wide attention to a quantum computing problem could easily increase the number of people working on it by two orders of magnitude.<br>For example, the secp256k1 Point-Addition Challenge is being created as a direct consequence of our paper.<br>This is not the kind of environment where techniques stay secret for long.
The second big problem with sharing research by ZKP is that, sometimes, just knowing a solution exists is enough to solve the problem.<br>The famous case of George Dantzig cracking two unsolved problems in statistics because he thought they were homework comes to mind.<br>Knowing that you don’t even need to consider that a solution won’t exist can be very helpful.<br>Often the hard part is just knowing to work on a problem at all!
The third big problem with sharing research by ZKP is rubber-hose...