Improved quantum attack on ECDSA from Google?

[si...@hoerder.net]

Hi,

Has there been any independent review of the improved quantum attack on ECDSA from Google? https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf 

Usually I’m quite doubtful about attack claims where the details are being withheld and where there is no computer big enough to actually run it yet but the paper does have some very well reputed names on it and it seems that the improved attack motivated Google to publish a more aggressive migration timeline than all the nation-state migration timelines known to me?

One of the questions that would interest me is how much security margin sits between the attack and the 2029 date from Google’s migration timeline. Unfortunately, the paper doesn’t really discuss that. (Of course, the usual disclaimer paraphrased from Karl Valentin applies: All predictions are uncertain, difficult and debatable. Predictions concerning future security margins doubly so.)

Thanks,

Simon

[Marcel Tiepelt]

Hello,

well, at some point last year this was posted (by reputable researchers) who achieve results with the same magnitude of qubits/ gates etc., but which provide the details of the estimation.

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). 

Cheers,
Marcel 

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/59089462-27CE-43EB-AD9B-49F8EB955EB6%40hoerder.net.

[Marin Ivezic]

Simon, Marcel,

A few points that might be useful to the list:

On Simon's question about independent review — the paper uses a zero-knowledge proof so the circuit claims are cryptographically verifiable without access to the circuits themselves. Which is the responsible disclosure approach. Besides it being responsible, it's arguably stronger form of verification than traditional peer review (for this specific type of claim).

The author list (Babbush, Gidney, Zalcman, Neven from Google, plus Boneh from Stanford and Drake from the Ethereum Foundation) is notable. Craig Gidney is the same researcher behind the landmark RSA-2048 resource estimates that Marcel referenced.

Marcel is right that the results are consistent with the trajectory. The Google paper's specific achievement is compressing the spacetime volume for ECDLP-256 by roughly 10x. Prior work forced a trade-off: Chevignard et al. (EUROCRYPT 2026) (https://eprint.iacr.org/2026/280) achieved ~1,100 logical qubits but required over 10^11 Toffoli gates; Litinski (2023) needed (only) ~200 million gates but needed ~2,500 qubits. Google is in most practical middle 1,200–1,450 logical qubits and 70–90 million Toffoli gates.

If we are talking about papers over the last few days, you should also check the Oratomic/Caltech/UC Berkeley paper (https://arxiv.org/abs/2603.28627) that dropped the same day as Google's, claiming Shor's algorithm can run on as few as 10,000 neutral atom qubits.

Lots of caveats on this latest paper, and all others, but still overall a huge resource estimation reduction in three papers over last three weeks. But that's just theory on paper. The engineering gap between what any of these papers assume and what has actually been demonstrated in hardware is huge.  E.g. the best demonstrated logical circuit depth on any platform is roughly 10,000 operations; breaking RSA-2048 requires 6.5 billion. That means that on this one metric alone we need to improve 650,000x to get to CRQC (even with these latest optimized algorithms). 

I've published a detailed scorecard mapping these resource estimates against demonstrated hardware and also maintain an interactive tool where you can plug in your own assumptions about growth rates. Happy to share links if useful.

Best,
Marin

[Jeffrey Burdges]

> On 2 Apr 2026, at 11:04, Marcel Tiepelt <marcel....@kit.edu> wrote:
>
> well, at some point last year this was posted (by reputable researchers) who achieve results with the same magnitude of qubits/ gates etc., but which provide the details of the estimation.
> 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).

Very interesting, thanks! It’s not my field but..

I’ve not checked but I’d assume the google circuit only randomises one side of the EC point addition. You’d always do fixed base point addition in Shor, so real implementations would be one sided like that.

As a result, their zk circuit tells us little about how they choose & handle that fixed base point, only that the other point was selected randomly. This would still be much less guilty of baking the factorisation into the algorithm than what factoring and RSA papers do, but still fairly consistent with past trends.

There is clearly no responsible disclosure concern here, since an APT can always hire people who’ll eventually reproduce a result like this, but the zk proof is a cute way to generate buzz, and to give yourself time to finish one or more other papers before revealing your flavour of the trick.

Jeff