International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Concrete quantum cryptanalysis of binary elliptic curves

Authors:
Gustavo Banegas , Chalmers University of Technology, Gothenburg, Sweden
Daniel J. Bernstein , University of Illinois at Chicago, Chicago, USA; Ruhr University Bochum, Bochum, Germany
Iggy van Hoof , Eindhoven University of Technology, Eindhoven, The Netherlands
Tanja Lange , Eindhoven University of Technology, Eindhoven, The Netherlands
Download:
DOI: 10.46586/tches.v2021.i1.451-472
URL: https://tches.iacr.org/index.php/TCHES/article/view/8741
Search ePrint
Search Google
Abstract: This paper analyzes and optimizes quantum circuits for computing discrete logarithms on binary elliptic curves, including reversible circuits for fixed-base-point scalar multiplication and the full stack of relevant subroutines. The main optimization target is the size of the quantum computer, i.e., the number of logical qubits required, as this appears to be the main obstacle to implementing Shor’s polynomial-time discrete-logarithm algorithm. The secondary optimization target is the number of logical Toffoli gates. For an elliptic curve over a field of 2n elements, this paper reduces the number of qubits to 7n + ⌊log2(n)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48n3 + 8nlog2(3)+1 + 352n2 log2(n) + 512n2 + O(nlog2(3)) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also O(n3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.
Video from TCHES 2020
BibTeX
@article{tches-2020-30774,
  title={Concrete quantum cryptanalysis of binary elliptic curves},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2021, Issue 1},
  pages={451-472},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8741},
  doi={10.46586/tches.v2021.i1.451-472},
  author={Gustavo Banegas and Daniel J. Bernstein and Iggy van Hoof and Tanja Lange},
  year=2020
}