Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
Open accessThe DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.
Abstract
We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Pioneer work by the University of Waterloo and Microsoft Research estimated that the number of logical qubits necessary to implement quantum algorithms that can break 256 bit-long digital signatures generated with (EC)DSA, typically used in current blockchain networks, are 150077 and 233078, respectively.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [78]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · cited 8×
“Our findings imply that attacking elliptic curve cryptography is indeed easier than attacking RSA, even for relatively small key sizes.”
BackgroundInfluentialAlgorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059 · cited 1×
“Thirty years after their introduction to cryptography [27,24], they are used to instantiate public key mechanisms such as key exchange [10] and digital signatures [15,20] that are widely deployed in various cryptographic systems.”
BackgroundKoblitz, N. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866109-5 · Cited by 5,634 · cited 1×
“Thirty years after their introduction to cryptography [27,24], they are used to instantiate public key mechanisms such as key exchange [10] and digital signatures [15,20] that are widely deployed in various cryptographic systems.”
BackgroundTor: The Second-Generation Onion Router
Dingledine, R., Mathewson, N., & Syverson, P. (2004) · doi:10.21236/ada465464 · Cited by 4,104
Use of Elliptic Curves in Cryptography
Miller, V. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39799-x_31 · Cited by 3,946
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Modular multiplication without trial division
Montgomery, P. L. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777282-x · Cited by 2,669 · cited 2×
“In [28], Montgomery introduced a representation for an integer modulo p he called a p-residue that is now called the Montgomery representation.”
BackgroundThe Elliptic Curve Digital Signature Algorithm (ECDSA)
Johnson, D., Menezes, A., & Vanstone, S. (2001) · International Journal of Information Security · doi:10.1007/s102070100002 · Cited by 2,239
The Arithmetic of Elliptic Curves
Silverman, J. H. (2009) · Graduate texts in mathematics · doi:10.1007/978-0-387-09494-6 · Cited by 2,233
A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms
ElGamal, T. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39568-7_2 · Cited by 1,604
The Transport Layer Security (TLS) Protocol Version 1.2
Dierks, T., & Rescorla, E. (2008) · doi:10.17487/rfc5246 · Cited by 1,576
(2005) · doi:10.1007/0-387-28979-8 · Cited by 719
Parallel Collision Search with Cryptanalytic Applications
van Oorschot, P. C., & Wiener, M. J. (1999) · Journal of Cryptology · doi:10.1007/pl00003816 · Cited by 639
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits
Amy, M., Maslov, D., Mosca, M., & Roetteler, M. (2013) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2013.2244643 · Cited by 549
Self-citationBernstein, D. J., Birkner, P., Jóye, M., Lange, T., & Peters, C. (2008) · Springer eBooks · doi:10.1007/978-3-540-68164-9_26 · Cited by 466 · cited 1×
“One such example is the twisted Edwards form of an elliptic curve [3].”
BackgroundSemiclassical Fourier Transform for Quantum Computation
Griffiths, R. B., & Niu, C.-S. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3228 · Cited by 431 · cited 2×
“The phase shift matrices Shor’s algorithm to compute the discrete logarithm in the subgroup of an elliptic curve generated by a point P , analogous to the algorithms from [2,19,21].”
MethodShor's discrete logarithm quantum algorithm for elliptic curves
Proos, J., & Zalka, C. (2003) · Quantum Information and Computation · doi:10.26421/qic3.4-3 · Cited by 421
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Gordon, D. M. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406010 · Cited by 322
Quantum circuits ofT-depth one
Selinger, P. (2013) · Physical Review A · doi:10.1103/physreva.87.042302 · Cited by 225 · cited 1×
“…x, y, z (cid:105) (cid:55)→ | x, y, z ⊕ xy (cid:105) is known to be universal for reversible computing [34] and can be implemented exactly over the Clifford+ T gate set, see [41] for a T -depth 1 implementation using a total of 7 qubits and [1] for a T -depth 3 realization using a total of 3 qubits.”
MethodLangley, A., Hamburg, M., & Turner, S. (2016) · doi:10.17487/rfc7748 · Cited by 195 · cited 1×
“More recently, Bernstein’s Curve25519 [49], a Montgomery curve over a 255-bit prime field, has seen more and more deployment, and it has been recommended to be used in the next version of the TLS protocol [25] along with another even more recent curve proposed by Hamburg called Goldilocks [17].”
MethodThe Montgomery inverse and its applications
Kaliski, B. S. (1995) · IEEE Transactions on Computers · doi:10.1109/12.403725 · Cited by 174 · cited 3×
“As the counter can take values between n and 2n only [22], it can be implemented using dlog2(n) + 1e qubits only.”
BackgroundMethodInfluentialComputational problems associated with Racah algebra
Stein, J. (1967) · Journal of Computational Physics · doi:10.1016/0021-9991(67)90047-2 · Cited by 172 · cited 1×
“We use a reversible circuit for the extended binary greatest common divisor algorithm [47] that implements Kaliski’s algorithm [25] for inverting a number xR mod p given in Montgomery representation for R = 2; i.”
MethodElliptic Curve Cryptography (ECC) Cipher Suites for Transport Layer Security (TLS)
Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., & Moeller, B. (2006) · doi:10.17487/rfc4492 · Cited by 169
Kangaroos, Monopoly and Discrete Logarithms
Pollard, J. M. (2000) · Journal of Cryptology · doi:10.1007/s001450010010 · Cited by 164 · cited 1×
“The currently best known classical algorithms to solve the ECDLP are based on parallelized versions of Pollard’s rho algorithm [32,46,33].”
MethodPractical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits
Kliuchnikov, V., Maslov, D., & Mosca, M. (2015) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2409842 · Cited by 156 · cited 1×
“This means that it can be used to approximate any given target unitary single qubit operation to within precision ε using sequences of length 4 log2(1/ε) [38,23], and using an entangling gate such as the CNOT gate, the Clifford+T gate set can approximate any unitary operation.”
MethodLIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing
Wecker, D., & Svore, K. M. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.4467 · Cited by 151 · cited 3×
“We implemented the reversible algorithm for elliptic curve point addition on elliptic curves E in short Weierstrass form defined over a prime field Fp, where p has n bits, as shown in Algorithm 1 and Figure 10 in Section 4 in F# within the quantum computing software tool suite LIQUi|〉 [47].”
MethodInfluentialSelf-citationRecent progress on the elliptic curve discrete logarithm problem
Galbraith⋆, S. D., & Gaudry, P. (2015) · Designs Codes and Cryptography · doi:10.1007/s10623-015-0146-7 · Cited by 149 · cited 1×
“See [14] for further details and [5] for a concrete, implementationbased security assessment.”
BackgroundComplete Addition Formulas for Prime Order Elliptic Curves
Renes, J., Costello, C., & Batina, L. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49890-3_16 · Cited by 119 · cited 1×
“For classical computations, this comes at the cost of a relatively small slowdown [35].”
BackgroundJoux, A., & Lercier, R. (2002) · Mathematics of Computation · doi:10.1090/s0025-5718-02-01482-5 · Cited by 117 · cited 1×
“discrete logarithms are exponential in the size of the input parameters2, whereas there exist subexponential algorithms for factoring [26,8] and finite field discrete logarithms [16,21].”
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers
Ekerå, M., & Håstad, J. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-59879-6_20 · Cited by 62
Complete Systems of Two Addition Laws for Elliptic Curves
Bosma, W., & Lenstra, H. W. (1995) · Journal of Number Theory · doi:10.1006/jnth.1995.1088 · Cited by 60 · cited 1×
“(Complete addition formulas) There exist complete formulas for the group law on an elliptic curve in Weierstrass form [6].”
Method(2006) · Lecture notes in computer science · doi:10.1007/11745853 · Cited by 34
Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer
Stebila, D., & Green, J. (2009) · doi:10.17487/rfc5656 · Cited by 28
A Low-Resource Quantum Factoring Algorithm
Bernstein, D. J., Biasse, J., & Mosca, M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59879-6_19 · Cited by 25
Elliptic and Hyperelliptic Curves: A Practical Security Analysis
Bos, J. W., Costello, C., & Miele, A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_12 · Cited by 21
(2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-59879-6 · Cited by 20
Research works printed but not linked: 7
- 2. Stephane Beauregard. Circuit for Shor's algorithm using 2n+3 qubits. Quantum Info. Comput. , 3(2):175-185, March 2003.
- 21. Thomas H¨ aner, Martin Roetteler, and Krysta M. Svore. Factoring using 2 n +2 qubits with Toffoli based modular multiplication. Quantum Information and Computation , 18(7&8):673-684, 2017.
- 31. Dmitri Maslov, Jimson Mathew, Donny Cheung, and Dhiraj K. Pradhan. An O(m 2 )-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2 m ). Quantum Information & Computation , 9(7):610-621, 2009.
- 35. Michael. A. Nielsen and Ike. L. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, Cambridge, UK, 2000.
- 37. John M. Pollard. Monte Carlo methods for index computation mod p . Math. Comput. , 32(143):918924, 1978.
- 43. Peter Selinger. Efficient Clifford+ T approximation of single-qubit operators. Quantum Information & Computation , 15(1-2):159-180, 2015.
- 49. Yasuhiro Takahashi, Seiichiro Tani, and Noboru Kunihiro. Quantum addition circuits and unbounded fan-out. Quantum Information & Computation , 10(9&10):872-890, 2010.
Cited by
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
“In particular, consider the Toffoli count for computing discrete logarithms over elliptic curves reported by [17].”
BackgroundMethodToward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
“) Quantum algorithms for classically hard instances of the elliptic curve discrete logarithm problem have roughly comparable cost (37).”
BackgroundThe Roadmap to 6G Security and Privacy
Porambage, P., Gur, G., Osorio, D. P. M., Liyanage, M., Gurtov, A., & Ylianttila, M. (2021) · IEEE Open Journal of the Communications Society · doi:10.1109/ojcoms.2021.3078081 · Cited by 416
“The discrete logarithmic problem, which is the basis of current asymmetric cryptography, may become solv-able in polynomial time with the development of quantum algorithms (e.g., Shor) [117].”
BackgroundNoise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304075 · Cited by 411
“A QC system with 72 fully-entangled qubits and sufficiently-precise operations (“gates”) would likely be sufficient to show “quantum advantage” over the largest classical supercomputers, but would still be 5-6 orders of magnitude smaller than the resource requirements of Shor’s well-known QC algorithm for factoring la…”
MethodQuantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2023) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2026-02888 · Cited by 361
Metadata
- Authors
- Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K.
- Affiliations
- Microsoft (United States) (US)
- Corresponding author
- Roetteler, Martin
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer International Publishing
- Published
- 2017
- Volume
- 2017
- Pages
- 241-270
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2949288242
- Cited by
- 212
- References
- 37
- Citations by year
- 2026: 24 · 2025: 24 · 2024: 28 · 2023: 29 · 2022: 33 · 2021: 28 · 2020: 18 · 2019: 12 · 2018: 13 · 2017: 3
- FWCI
- 5.74
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Licence
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- Locations
- Lecture notes in computer science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- IACR Cryptology ePrint Archive (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Keywords
- elliptic curve discrete logarithm problem, Shor's algorithm, quantum resource estimation, qubit requirements, quantum circuit complexity, elliptic curve cryptography, post-quantum cryptography
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.