Paper 2017/598

Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms

Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2017
Keywords
Quantum cryptanalysiselliptic curve cryptographyelliptic curve discrete logarithm problem.
Contact author(s)
mnaehrig @ microsoft com
History
2017-10-31: last of 4 revisions
2017-06-21: received
See all versions
Short URL
https://ia.cr/2017/598
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/598,
      author = {Martin Roetteler and Michael Naehrig and Krysta M.  Svore and Kristin Lauter},
      title = {Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/598},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/598}},
      url = {https://eprint.iacr.org/2017/598}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.