A genuine milestone in the physics of randomness, and already being miscast by parts of the trade press as a fix for the quantum threat. Here is the precise version.
June 2, 2026 – In March 2026, Google Quantum AI published what may have been the most consequential quantum cryptanalysis paper of the year. The Babbush et al. paper demonstrated that Shor’s algorithm could break 256-bit elliptic curve cryptography with roughly 1,175 logical qubits and about 2.6 million Toffoli gates. But the team made an unusual choice: instead of publishing their circuit designs, they hid them behind zero-knowledge proofs. The justification was responsible disclosure. The concern was that detailed circuits might help attackers more than defenders.
Two months later, the secret is out. André Schrottenloher, a researcher at Inria’s Centre at the Université de Rennes, has published a preprint with independently constructed circuits that match Google’s results on qubits and beat them on gate count. Craig Gidney, the Google Quantum AI researcher who designed the original circuits, confirmed the match on his blog the same day: “My congratulations to André on being the first to match our circuits. Not only did he get it done in two months, he improved the Toffoli count a little bit!”
Gidney’s post goes further. He concedes the zero-knowledge approach failed and states plainly: “We should just publish openly.”
Schrottenloher provides two circuit variants for secp256k1 (the curve used by Bitcoin and Ethereum), along with a generic variant for any prime-field curve. The comparison with Google’s circuits:
| Circuit | Qubits | Toffoli gates |
|---|---|---|
| Google space-optimized (secp256k1) | 1,175 | 2^21.36 (~2.7M) |
| Google gate-optimized (secp256k1) | 1,425 | 2^21.00 (~2.1M) |
| Schrottenloher space-optimized (secp256k1) | 1,192 | 2^21.19 (~2.4M) |
| Schrottenloher gate-optimized (secp256k1) | 1,446 | 2^20.83 (~1.9M) |
| Schrottenloher space-optimized (any prime) | 1,192 | 2^21.78 (~3.6M) |
| Schrottenloher gate-optimized (any prime) | 1,462 | 2^21.42 (~2.8M) |
For the full Shor’s algorithm on secp256k1 (28 windowed point additions), Schrottenloher’s gate-optimized circuit requires 1,462 logical qubits and 2^25.78 Toffoli gates, compared to 2^25.94 for Google’s equivalent. That is roughly a 10% reduction in Toffoli count at the cost of ~1.5% more qubits.
Both Schrottenloher’s paper and code are fully open. The implementation uses the Qarton library, and the complete point addition circuits are available on Inria’s GitLab.
Gidney’s blog post is remarkably candid about why the secret was never going to last. The core technique behind Google’s circuits, he explains, was already visible in a prior paper the team had published on Decoded Quantum Interferometry (DQI) in October 2025. That DQI paper introduced an efficient method for space-efficient quantum-quantum in-place modular multiplication, and multiplication is the most expensive operation in elliptic curve point addition.
“We knew that all anyone had to do, to unmask our ZKPs, was read over our prior papers and put two and two together,” Gidney writes.
Schrottenloher did precisely that. His circuit architecture separates the Extended Euclidean Algorithm into two sub-circuits: a forward Euclidean algorithm that records its decisions into a compressed bit-vector, and a Bézout reconstruction algorithm that replays those decisions to compute the modular inverse. This separation (drawn from the DQI paper’s technique) allows the in-place multiplication to be performed without a separate inversion step, saving both qubits and gates. The space complexity ends up at 4.355n + O(√n) for n-bit primes, with the Bézout reconstruction step as the binding constraint.
Schrottenloher also introduces a specialized optimization for pseudo-Mersenne primes (primes of the form 2^u – f where f is small), which is why the secp256k1 circuits are cheaper than the generic versions. The secp256k1 prime, 2^256 – 4294968273, allows modular reductions to be replaced with small constant additions, cutting the cost of modular arithmetic inside the reconstruction loop.
The March 2026 paper’s use of zero-knowledge proofs to conceal circuit details was, at the time, unprecedented in quantum cryptanalysis. Gidney’s blog post now reads as a surprisingly honest autopsy of the approach. He identifies three structural problems.
The Streisand effect drew attention to the problem. Saying “we have a solution but won’t share it” attracted far more scrutiny to ECC circuit optimization than open publication would have. The fact that a solution existed was itself useful information. Gidney invokes the George Dantzig anecdote: knowing that a problem is solvable can eliminate the hardest part of solving it. And the ZKP identified exactly who to pressure for details, which Gidney describes with characteristic bluntness using the term “rubber-hose cryptanalysis.”
Even before Schrottenloher’s reconstruction, the ZKP approach had already taken damage. In April, Trail of Bits found and exploited vulnerabilities in Google’s Rust-based ZKP prover code. Keegan Ryan’s team discovered that unsafe blocks in the prover’s deserializer, combined with a pair of jump-table bugs, allowed them to forge a proof claiming zero Toffoli gates and fewer qubits than Google. The bugs were in the prover’s code, not the cryptographic claims, but they demonstrated that ZKPs shift trust from domain expertise to software implementation quality. Google patched the code, and the scientific claims remained valid, but the episode underscored Gidney’s broader point: ZKPs for responsible disclosure introduce new attack surfaces without delivering lasting secrecy.
This paper closes a chapter that began in March, and the conclusion is unambiguous. The responsible-disclosure-by-ZKP experiment lasted exactly 63 days. The idea was creative, and Gidney deserves credit for trying something novel. But the outcome validates what most of the cryptography community suspected: in a field built on published algorithms and shared mathematical techniques, attempting to conceal a circuit design while publishing the resource estimates it achieves is a contradiction.
What Schrottenloher has produced is, in practical terms, exactly what the community needed from the Babbush paper in March: verifiable, reproducible, open circuit designs that confirm the ~1,200-qubit, ~2-million-Toffoli-gate operating point for ECDLP-256. Security teams modeling quantum risk can now use these numbers with confidence. The circuits have been tested, the code compiles, the gate counts are verifiable. There is no longer a trust gap between the claim and the evidence.
The technical achievement here is worth separating from the disclosure story. Schrottenloher is the same researcher whose EUROCRYPT 2026 paper with Chevignard and Fouque achieved the lowest qubit count for ECDLP at ~1,193 qubits, albeit with a ~1,000x gate penalty. He now has circuits at both ends of the width-depth tradeoff: minimum qubits (the EUROCRYPT paper) and minimum spacetime volume (this paper). That is a commanding position in the field.
When I covered the Babbush paper in April, I noted that the roughly 10x reduction in spacetime volume for ECDLP-256 was the technically precise achievement, compressing both qubit count and gate count simultaneously relative to prior published work by Litinski (2023). Schrottenloher’s reproduction confirms that assessment. The improvement over Litinski is real: roughly 2x fewer qubits and 3x fewer gates, cutting the full Shor’s algorithm for secp256k1 from ~200 million Toffoli gates to ~56 million.
For CRQC timeline modeling within my CRQC Quantum Capability Framework, this paper matters because it moves the ECDLP algorithmic track from “claimed but unverifiable” to “confirmed and reproducible.” The algorithmic requirements for breaking ECC-256 are now well-characterized across multiple independent research groups: roughly 1,100-1,500 logical qubits depending on the width-depth tradeoff, with Toffoli counts ranging from ~2 million (Schrottenloher/Babbush operating point) to the low billions (Chevignard’s width-minimized approach). The uncertainty in Q-Day estimates for ECC now sits almost entirely on the hardware and error correction side: below-threshold operation, decoder performance, continuous operation, and engineering scale.
One observation that deserves attention: this is now three major ECDLP papers in three months from European and Chinese researchers, with Google as the catalyst but not the sole driver. Schrottenloher (France), Chevignard-Fouque-Schrottenloher (France), and Luo et al. (Tsinghua/Peking University, China) have collectively produced the most productive quarter in ECDLP resource estimation since Shor’s original 1994 paper. The field has shifted from RSA-centric optimization to treating ECC as the primary target, which is exactly the rebalancing I argued was overdue.
Gidney’s parting line resonates: “We should just publish openly.” He is right. The PQC migration decisions that CISOs and CTOs need to make depend on accurate, verifiable resource estimates. Those estimates now exist, and they are public.
My company - Applied Quantum - helps governments, enterprises, and investors prepare for both the upside and the risk of quantum technologies. We deliver concise board and investor briefings; demystify quantum computing, sensing, and communications; craft national and corporate strategies to capture advantage; and turn plans into delivery. We help you mitigate the quantum risk by executing crypto‑inventory, crypto‑agility implementation, PQC migration, and broader defenses against the quantum threat. We run vendor due diligence, proof‑of‑value pilots, standards and policy alignment, workforce training, and procurement support, then oversee implementation across your organization. Contact me if you want help.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。