At the end of March, Google announced that they had come up with a design for a quantum computer circuit that was much more efficient at running Shor's algorithm and capable of breaking ECDSA signatures with significantly fewer qubits than everyone thought was necessary (#1462657).
Then they did this weird thing where they said the results were so scary that they weren't going to release the actual circuit design and instead published a zk-proof of it (#1462804)
Then Trail of Bits published a paper showing some errors in the zk-proof stuff software that Google was using (#1480284) which in my mind didn't cast any doubt on Google's results, but did make me wonder what the point of being coy and using a zk-proof was.
Then, today we got a couple of new things:
A French guy named André Schrottenloher published "Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms" which pretty much identifies the main optimization that the Google team discovered but didn't reveal.
Then, quantum expert Craig Gidney published a blog post "The French Have the Quantum Circuits", saying that he had discovered the same optimization about a year ago.
And then somebody made a website to crowdsource further optimizations: ecdsa.fail
I'm no quantum expert, but I think this is sort of like designing ASICs for elliptic curve cryptography-breaking quantum computers. It doesn't mean anyone has actually built such ASICs, but they've got the designs. If people can figure out how to build them, the quantum computers will be much faster at cracking elliptic curve cryptography than previously expected.
The ecdsa fail website seems to be blind leading the blind. A bunch of people throwing stuff at the same LLMs in hope that something sticks. It won't. LLMs are terrible at numerical problems. They are pattern recognizers + randomness.
André Schrottenloher's paper is an important result for reproducibility.
Well…that’s scary. The diff over the last 24 hours is insane let alone the last few days. Do you think this discovery is causing the sell off right now?
not at all. The number of people who actually pay attention to quantum stuff is small. and I don't think this is actually moving the needle that much. Maybe it means quantum resistant signatures on bitcoin are more likely now.
For anyone wondering how ECDSA is broken mathematically when a nonce ($k$) is reused:
The signature equations for two messages $m_1$ and $m_2$ signed with the same private key $d$ and the same nonce $k$ are:
s1=k−1(z1+r⋅d)(modn)
s2=k−1(z2+r⋅d)(modn)
where $z_i$ are the message hashes, $r$ is the signature x-coordinate (which is identical for both signatures because $k$ is the same), and $d$ is the private key we want to recover.
By subtracting the two equations:
s1−s2=k−1(z1−z2)(modn)
We can compute the nonce $k$ directly:
k=(z1−z2)⋅(s1−s2)−1(modn)
Once we recover the nonce $k$, computing the private key $d$ is trivial from either signature:
d=r−1(s1⋅k−z1)(modn)
This is why nonce reuse is completely fatal. Even if the nonce isn't fully reused but only biased (e.g. knowing a few bits of $k$ across several signatures), the private key can be recovered in polynomial time using Lattice Reduction (LLL algorithm applied to the Hidden Number Problem).