A more efficient implementation of Shor's algorithm

Top comment on LWN is a very interesting read (although neither the commenter nor myself claim any such trickery was involved in this case).

> Trail of Bits were able to craft an input that beats Google's circuit and prove it... by virtue of a bug in the verifier: https://blog.trailofbits.com/2026/04/17/we-beat-googles-zero... Google patched the vuln and the original proof still stands, but this is a pretty strange path we seem to be walking down [...]

Publishing a zero knowledge proof rather than the solution is pretty clever.

>We contend that the amount of time remaining before the arrival of CRQCs still exceeds the amount of time needed to migrate public blockchains to PQC, though the margin for error is increasingly narrow. Therefore, we have offered updated resource estimates for quantum attacks on blockchain cryptography together with an analysis of vulnerabilities and mitigations in order to urge all vulnerable cryptocurrency communities to begin PQC transition immediately while its timely completion is still the likely prospect.

they really couldn't be shouting "mitigate now or never" any louder. I'm curious how they arrived at the efficiency improvements, but perhaps any mention of that would be similar to releasing the circuit.

Wait, the article mentions that Shor's algorithm is factoring (which is what I understood), but then it's talking about elliptic curve cryptography? I thought ECC didn't use the same mathematical foundations of RSA, and RSA has been slowly phased out anyways...

How is it possible to provide a zero knowledge proof that their circuit works for large problem instances if there is no efficient way to run or simulate the circuit with the required instance size?

Checking the required hardware noise performance:

>On superconducting architectures with 10−3 physical error rates...

So still 1-2 orders of magnitude better than what we can achieve.

This is against a 256 bit elliptic curve. For some reason most people are stating the difficulty of using Shor's against 2048 bit RSA. Elliptic curves are easier to break with Shor's. I wonder how much of the optimization came from that fact alone...

> If the paper's authors had chosen to release their circuit, they would certainly have been recognized for the important progress they made in the science of quantum computing. Other researchers would have gone on to build on their work, and the entire scientific community would be richer for it.

... and the world could well have been unsafer. There is pretty strong reason not to release insights which could be used as an attack on public key cryptography. We already know the fix anyway, post quantum cryptography algorithms.

Sometimes scientific curiosity has to step back when it comes to potentially dangerous research. Scott Aaronson recently [1] compared this case to when scientists stopped publishing on nuclear fission research because the possibility of developing an atomic bomb became concrete:

> When I got an early heads-up about these results—especially the Google team’s choice to “publish” via a zero-knowledge proof—I thought of Frisch and Peierls, calculating how much U-235 was needed for a chain reaction in 1940, but not publishing it, even though the latest results on nuclear fission had been openly published just the year prior.

1: https://scottaaronson.blog/?p=9665

However, the author managed to squeeze the word "however" eleven times in this article, however.