Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms
André Schrottenloher · 2026
Read Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms by André Schrottenloher (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-02235.txt.
Introduction
Schrottenloher optimizes point addition circuits for elliptic curve discrete logarithms. Shor's algorithm is the main quantum threat to cryptography. Precise cost estimates decide how real that threat is. Many authors have worked to cut those costs. Work splits between logical and physical levels of design.
Factoring RSA keys got cheaper through better arithmetic recently. Elliptic curve discrete logarithms saw a similar jump. Babbush and co-authors cut gate and qubit counts by a factor of two to three. Their result rests on optimized point addition circuits. Those circuits work on elliptic curves over prime fields. Schrottenloher pushes that circuit optimization further here. Resource estimates for quantum attacks gain precision. Cryptographers can judge timelines with better numbers.
Catalog record
| CREATOR | André Schrottenloher |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.02235
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms André Schrottenloher Abstract Shor’s algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field. 1 Introduction Since Shor’s breakthrough paper [ 21 ] , it has been known that once a large-scale quantum computer becomes available, public-key cryptography based on the hardness of integer factoring (e.g., the RSA cryptosystem) and discrete logarithms (e.g., cryptography based on finite fields [ 16 ] and elliptic curve groups [ 16 ] ) can be considered as broken, the underlying problems being solved in quantum polynomial time. This impact motivates the early adoption of post-quantum cryptography, with a first batch of public-key encryption and signature schemes standardized by the NIST as a result of a large-scale public standardization process [ 18 ] . After Shor’s paper, many authors have quantified the exact gate and qubit counts of the algorithm, especially for its main cryptographic applications: factoring RSA integers, computing discrete logarithms in finite fields, and in elliptic curves of prime order. This paper focuses on the latter. Most of these studies [ 19 , 13 , 4 ] have considered logical quantum circuits, that is, without any implementation constraints. As the technology has matured, several works have also examined the cost of physically implementing the algorithm under specific assumptions regarding the capabilities and scale of the available hardware. Both logical algorithms and physical mappings have advanced in parallel. As an example, in 2021, Gidney and Ekerå [ 10 ] estimated that 20 million superconducting qubits could be necessary to factor RSA-2048 public keys (classically secure). A more recent paper by Gidney [ 9 ] reached one million qubits. Roughly half of this 20\times reduction (i.e., a factor 4) comes from logical circuits based on (and improving over) [ 3 ] , while the rest comes from an improved physical implementation. Babbush et al.’s Result. In a recent preprint, Babbush et al. [ 2 ] improved logical quantum circuits for computing elliptic curve discrete logarithms, and discussed the risks for cryptocurrencies using this non-post-quantum cryptography. In this paper, we only focus on their logical circuit results. Babbush et al.’s result is based on an improved (windowed) elliptic curve point addition circuit on the curve secp256k1 . Their circuits are “kickmick” circuits, which allow measurement-based uncomputation and phases but are ultimately efficient to simulate classically. They did not publish any detail on their circuit architecture, relying instead on a zero-knowledge proof to prove that they obtained circuits with the claimed gate and qubit counts, which performed point addition with a reasonable success probability. Succeeding on random inputs is enough to run Shor’s algorithm. The decision not to publish the circuit is justified in [ 2 ] by concerns on the feasibility of such quantum attacks in practice on the medium term. This paper follows instead the practice of previous works [ 15 , 11 , 9 ] , which intend to make the result fully reproducible. We believe that a full discussion of the arguments in [ 2 ] would be out of scope of the current paper. Our Result. We obtain two circuits for point addition on secp256k1 , reaching similar results as Babbush et al. [ 2 ] , with a slight improvement in Toffoli gate count. The design principles of these circuits are described in this paper. We programmed and tested them using Qarton 1 1 1 https://gitlab.inria.fr/capsule/qarton . In particular, the circuits are not exact: they will fail with some probability. Testing on random inputs shows that this probability of failure is comparable to the one of [ 2 ] . While the gate count varies depending on implementation details, the number of qubits is around 4.355n+\mathcal{O}\!\left(\sqrt{n}\right) in the version that we selected, where n is the bit-size of the prime. It could be reduced up to 4.12n+\mathcal{O}\!\left(\sqrt{n}\right) using a different implementation, which would likely increase the Toffoli gate count. Another recent work [ 4 ] achieved a space of 3.12n+\mathcal{O}\!\left(\sqrt{n}\right) , but the technique employed is very different and yields a sharp increase in gate count for a relatively small gain in memory on relevant instances. A comparison between the qubit and gate counts of Babbush et al. [ 2 ] and ours is given in Table 1 . Table 1: Costs of our circuits and comparison with [ 2 ] . The “Toffolis” column counts together CCX, CCZ as well as And gates. All circuits have a failure probability at most 2^{-13.3} (succeeding on 10 000 randomly chosen inputs). The number of qubits and gates given here do not account for the small window of size w=16 : it costs 16 qubits more and 3\times 2^{w} Toffoli gates to run the actual “windowed point addition” circuit. Type Qubits Toffolis Total gates Reference Space-optimized for secp256k1 1175 2^{21.36} \simeq 2^{24} [ 2 ] Gate-optimized for secp256k1 1425 2^{21.00} \simeq 2^{24} [ 2 ] Space-optimized for secp256k1 1192 2^{21.19} \simeq 2^{24} Ours Gate-optimized for secp256k1 1446 2^{20.83} \simeq 2^{24} Ours Space-optimized for any prime 1192 2^{21.78} \simeq 2^{24.5} Ours Gate-optimized for any prime 1446 2^{21.42} \simeq 2^{24.5} Ours Following the same reasoning as [ 2 ] , the Toffoli count of the entire Shor’s algorithm on secp256k1 is roughly: 28\times(3\times 2^{16}+Q_{A}) (1) where Q_{A} is the Toffoli count of a single windowed addition circuit as given in Table 1 , while the qubit count is the one of Table 1 plus 16 (roughly). The algorithm needs to run only once to retrieve the discrete logarithm (contrary to trade-offs for RSA like in [ 9 ] , which require multiple runs). The resulting numbers are summarized in Table 2 . The best previous result was from Litinski [ 15 ] using around 200 million Toffoli gates (i.e., 2^{27.57} ) to compute a single discrete logarithm, with about twice as much qubits. Table 2: Cost of running Shor’s algorithm entirely and comparison with [ 2 ] . The “Toffolis” column counts together CCX, CCZ as well as And gates. Type Qubits Toffolis Reference Space-optimized for secp256k1 1191