TY - JOUR
AU - Banegas, Gustavo
AU - Bernstein, Daniel J.
AU - van Hoof, Iggy
AU - Lange, Tanja
PY - 2020/12/03
Y2 - 2024/04/24
TI - Concrete quantum cryptanalysis of binary elliptic curves
JF - IACR Transactions on Cryptographic Hardware and Embedded Systems
JA - TCHES
VL - 2021
IS - 1
SE - Articles
DO - 10.46586/tches.v2021.i1.451-472
UR - https://tches.iacr.org/index.php/TCHES/article/view/8741
SP - 451-472
AB - <p>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<sup><em>n</em></sup> elements, this paper reduces the number of qubits to 7<em>n</em> + ⌊log<sub>2</sub>(<em>n</em>)⌋ + 9. At the same time this paper reduces the number of Toffoli gates to 48<em>n</em><sup>3</sup> + 8<em>n</em><sup>log<sub>2</sub>(3)+1</sup> + 352<em>n</em><sup>2</sup> log<sub>2</sub>(<em>n</em>) + 512<em>n</em><sup>2</sup> + <em>O</em>(<em>n</em><sup>log<sub>2</sub>(3)</sup>) with double-and-add scalar multiplication, and a logarithmic factor smaller with fixed-window scalar multiplication. The number of CNOT gates is also <em>O</em>(<em>n</em><sup>3</sup>). Exact gate counts are given for various sizes of elliptic curves currently used for cryptography.</p>
ER -