Georgia Tech's Jo and Lee Cut the Quantum Elliptic Curve Attack to 5n/2 Logical Qubits and Near-Quadratic Toffoli Gates, IACR ePrint 2026/2014, 14 September 2026
Quentir Defense Monitor
Evidence-based insights for quantum defense and security. Published by Quentir Systems LLC · September 21, 2026.
On September 14, 2026, two researchers at the Georgia Institute of Technology and the audit firm QED Audit, Sunghyeon Jo and Gye Jin Lee, posted a paper to the IACR Cryptology ePrint Archive that changes the two numbers a planner watches when pricing a quantum attack on elliptic curve cryptography. Their algorithm solves the elliptic curve discrete logarithm problem over an n-bit prime field with 5n/2 + o(n) logical qubits and a Toffoli gate count that grows only a little faster than n squared. The construction it improves on, posted in July by Han Luo and seven co-authors from Chinese institutions, needed 3n plus a logarithmic term in qubits and a gate count growing as n cubed divided by the logarithm of n. Jo and Lee lower both at once, and they do it with a single idea about how much of an extended Euclidean computation a quantum computer actually has to remember.
The paper matters to a defense reader for a plain reason. Elliptic curve Diffie-Hellman and ECDSA still authenticate software updates, sign firmware, establish TLS sessions and protect identity credentials across government and military systems, and they will keep doing so for years while migration proceeds. Planning for that migration leans on resource estimates of how many error-corrected qubits and how many expensive gates a fault-tolerant machine would need to recover a private key from a public one. Those estimates fell repeatedly in 2026, and Jo and Lee's paper is the latest fall.
What the paper proves: an exact ECDLP algorithm in 5n/2 + o(n) logical qubits and near-quadratic Toffoli gates, against Luo et al.'s 3n and near-cubic bound
The ePrint paper, 2026/2014, states its main result as Theorem 1. For an odd n-bit prime p and a curve in short Weierstrass form, given a generator G and a point Q in its subgroup, the algorithm returns the scalar d with Q equal to dG with probability at least two thirds, using 5n/2 + o(n) logical qubits and Õ(n²) Toffoli gates, where the tilde hides polylogarithmic factors. An affine point already occupies two n-qubit coordinate registers plus a flag for the point at infinity, so the construction spends only n/2 + o(n) qubits beyond the data it must hold.
The paper's own comparison table places the result against two space-efficient predecessors. Clémence Chevignard, Pierre-Alain Fouque and André Schrottenloher, in work presented at EUROCRYPT 2026, reached 3.12n + o(n) qubits under heuristic assumptions with a gate bound of order n to the fourth per run, and their method requires o(n) runs. Luo and colleagues, in the arXiv paper 2607.13816, first posted July 15 and revised on September 5, gave an exact affine construction with 3n + 6 floor(log₂ n) + O(1) qubits and 1056 n³ / log₂ n + O(n²) Toffoli gates, and they reported 835 logical qubits for a 256-bit prime-field curve. Jo and Lee's leading qubit term of 5n/2 is a reduction of about 17 percent against 3n, and their gate bound drops a full power of n. Both improvements come from the same component, which is the part of the paper worth understanding.
How the modular inverter saves memory: the invariant Rt + rT = p keeps three of four Euclidean values and rebuilds the fourth on demand
Shor's algorithm on an elliptic curve repeatedly adds points. In affine coordinates each point addition requires a modular inversion, and that inversion has historically been the most memory-hungry step in the whole circuit because the extended Euclidean algorithm carries four evolving quantities: two consecutive remainders, which the paper calls R and r, and the magnitudes of their Bézout coefficients, T and t. A reversible circuit ordinarily has to hold all four so that it can later run the computation backward and erase its intermediate data.
Jo and Lee observe that the four quantities are never independent. They satisfy Rt + rT = p exactly, so any one of the four can be recomputed from the other three and the public modulus. Their circuit therefore stores only three of them in a persistent Euclidean state and reconstructs the fourth when an update needs it, switching which three it keeps once the coefficient t passes a threshold near 2 to the power n/2. In both regimes the combined state fits in 3n/2 + o(n) qubits, and the quotient digits and control data that each Euclidean step needs are recovered from the updated state and then erased.
Two further techniques make the memory budget hold. The arithmetic queries inside those steps run in sublinear workspace using measurement-based uncomputation, in which mid-circuit measurements recycle working qubits and the phases they introduce are corrected before the next operation. Then Hua's identity, a classical algebraic identity, converts the multiplications by a variable square that affine point addition needs into inversions, so the frugal inverter does double duty. The result is an exact in-place modular inverter in 3n/2 + o(n) qubits and Õ(n) Toffoli gates, and exact controlled point addition in 5n/2 + o(n) qubits and Õ(n) Toffoli gates, against 2n plus a logarithmic term and 229 n² Toffoli gates for Luo et al.'s inverter. Since a full discrete logarithm needs roughly n controlled point additions, the near-linear gate cost per addition is what gives the whole algorithm its near-quadratic bound.
Quantum pillar: computing (cryptanalysis). Use posture: offensive. Technology readiness: TRL 1 of 9. The paper is an asymptotic algorithm with proofs and a worked numerical example, gives no concrete circuit for any cryptographic curve, and assumes a fault-tolerant machine that no disclosed hardware approaches, so it is a resource estimate on paper rather than a demonstrated attack.
Why 640 logical qubits is a leading term for P-256 and not a circuit size, and what the near-quadratic Toffoli bound changes
Coverage of the paper, including the September 15 Tech Times report by Devin Culbertson, has already produced a figure of about 640 logical qubits for a 256-bit curve. That number is 5n/2 with n set to 256, and nothing more. The paper says so directly in its related-work section: "Our analysis is asymptotic; concrete estimates at cryptographic sizes would require optimizing the polylogarithmic factors of Sections 3 and 4, and are left open." The o(n) term and the hidden polylogarithmic factors are real qubits and real gates for any specific curve, and the authors close by saying the lower-order space terms and the polylogarithmic factors are not optimized. A planner who compares 640 with Luo et al.'s 835 for the same curve is comparing a leading coefficient with a full circuit count, and the comparison is not valid. For NIST P-384, the curve in the National Security Agency's original Commercial National Security Algorithm suite, the same arithmetic gives a leading term of 960 against 1,152 for the 3n construction, with the same caveat attached.
The gate bound is the more consequential half of the result, and it is the half that headlines drop. In the fault-tolerant architectures that resource estimators assume, Toffoli gates are the non-Clifford operations that must be fed by magic-state distillation factories, and their count sets runtime, factory footprint and the error-correction distance a machine must sustain. A circuit that is narrow in qubits can still be unaffordable in time if its gate count is cubic, and Chevignard, Fouque and Schrottenloher's design shows the tradeoff from the other side: narrow, and paid for in gates and repeated runs. The strongest concrete estimate on public view remains the PRX Quantum paper by Ryan Babbush, Craig Gidney, Dan Boneh and colleagues, which priced a full 256-bit attack at fewer than 1,200 logical qubits and fewer than 90 million Toffoli gates in one tradeoff point. This Monitor examined that lineage when Circle's August 31 disclosure quoted 813 logical qubits off Eigen Labs' ECDSA.fail leaderboard, and the lesson applies here: width without gate count is one coordinate of a two-dimensional cost. Jo and Lee move both coordinates in the attacker's favor at the level of asymptotics, which is what makes the paper a genuine advance and why its concrete consequences are still unknown.
One more feature of the paper deserves attention from anyone who audits cryptanalytic claims. The authors disclose that OpenAI's GPT-5.6 Sol (Pro) was used in discovering and developing the inversion and point-addition constructions, that other AI systems were used for proof auditing and literature review, and that the authors read and verified every definition, lemma and proof and take full responsibility. The construction is fully public with proofs anyone can check, which is the standard the Monitor asked for when it examined a public quantum claim built on a private attack circuit.
What an offensive cryptanalysis result means for ECDH and ECDSA in defense systems, and what stands between an ePrint and a machine
Read as capability, the paper sits on the offensive side of the ledger in the plain sense that its value lies in breaking someone else's cryptography. The holder of a fault-tolerant machine meeting these bounds could recover any elliptic curve private key from its public counterpart: the ECDSA keys that sign firmware and software updates on fielded platforms, the ECDH exchanges behind sessions whose ciphertext an intelligence service may already hold, and the certificates that anchor identity in coalition networks. Because the same curve arithmetic serves P-256, P-384 and secp256k1 with different constants, an efficient circuit for one carries to the others. The gainer is whichever signals-intelligence establishment fields such a machine first.
What stands between this ePrint and an operational capability is, first, the concrete circuit the authors have explicitly left open; second, a fault-tolerant machine capable of sustaining the required non-Clifford computation without error, when the leading public hardware result is a handful of logical qubits held below threshold; and third, the engineering that turns a circuit into a run against a real key. None of those steps is announced here. What the paper does establish is that the cost of the attack keeps falling on paper, well below the 2017 baseline of about 9n qubits from Martin Roetteler and colleagues at Microsoft Research, and that the fall now touches gate count as well as width.
For a program office the operational reading is unchanged in direction and sharpened in timing. The National Institute of Standards and Technology's draft transition report, NIST IR 8547, places quantum-vulnerable signature and key-establishment uses providing 112-bit security strength on a path to deprecation after 2030 and disallowance after 2035. Entries providing at least 128-bit security strength, including the relevant P-256 and P-384 uses, specify disallowance after 2035 without that intermediate deprecation date. The Cybersecurity and Infrastructure Security Agency's post-quantum cryptography initiative asks organizations to build a current inventory of systems vulnerable to quantum decryption, engage their vendors, and plan the migration. The case for that post-quantum migration was never a machine arriving next year. It is that replacing vulnerable algorithms and their dependent implementations and credentials across a large installed base takes most of a decade, that data protected by ECDH today has a shelf life that may outlast the algorithm, and that the published cost of the attack moves in only one direction. A buyer reading Jo and Lee should file it as a strengthened reason to know exactly where P-256 and P-384 live in their estate, and as no reason to believe the machine exists.
Sources
Primary source: Sunghyeon Jo and Gye Jin Lee (Georgia Institute of Technology and QED Audit), "Quantum Discrete Logarithms on Elliptic Curves with 5n/2 + o(n) Logical Qubits and Õ(n²) Toffoli Gates," IACR Cryptology ePrint Archive 2026/2014, posted September 14, 2026. Other material: Han Luo and co-authors' arXiv preprint 2607.13816 on space-efficient point addition; NIST IR 8547 on the transition timeline; CISA's post-quantum cryptography initiative page; Devin Culbertson's September 15, 2026 report in Tech Times.