### Concrete quantum cryptanalysis of binary elliptic curves

Gustavo Banegas, Daniel J. Bernstein, Iggy van Hoof, and Tanja Lange

##### 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 2^n elements, this paper reduces the number of qubits to 7n+[log_2(n)]+9. At the same time this paper reduces the number of Toffoli gates to 48n^3+8n^(log_2(3)+1)+352n^2 log_2(n)+512n^2+O(n^(log_2(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(n^3). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.

Note: This is the full version of the paper accepted to TCHES.

##### Metadata
Available format(s)
Category
Implementation
Publication info
A major revision of an IACR publication in TCHES 2021
Keywords
Quantum cryptanalysiselliptic curvesquantum resource estimationquantum gatesShor’s algorithm
Contact author(s)
authorcontact-binecc @ box cr yp to
History
2020-10-19: received
Short URL
https://ia.cr/2020/1296
License

CC BY

BibTeX

@misc{cryptoeprint:2020/1296,
author = {Gustavo Banegas and Daniel J.  Bernstein and Iggy van Hoof and Tanja Lange},
title = {Concrete quantum cryptanalysis of binary elliptic curves},
howpublished = {Cryptology ePrint Archive, Paper 2020/1296},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1296}},
url = {https://eprint.iacr.org/2020/1296}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.