Improved Quantum Circuits for Elliptic Curve Discrete Logarithms

Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken

Abstract

We present improved quantum circuits for elliptic curve scalar multiplication, the most costly component in Shor's algorithm to compute discrete logarithms in elliptic curve groups. We optimize low-level components such as reversible integer and modular arithmetic through windowing techniques and more adaptive placement of uncomputing steps, and improve over previous quantum circuits for modular inversion by reformulating the binary Euclidean algorithm. Overall, we obtain an affine Weierstrass point addition circuit that has lower depth and uses fewer T gates than previous circuits. While previous work mostly focuses on minimizing the total number of qubits, we present various trade-offs between different cost metrics including the number of qubits, circuit depth and T-gate count. Finally, we provide a full implementation of point addition in the Q# quantum programming language that allows unit tests and automatic quantum resource estimation for all components.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.PQCrypto 2020
Keywords
discrete logarithm problemquantum cryptanalysisShor's algorithmresource estimates
Contact author(s)
samuel jaques @ materials ox ac uk
mnaehrig @ microsoft com
History
Short URL
https://ia.cr/2020/077

CC BY

BibTeX

@misc{cryptoeprint:2020/077,
author = {Thomas Häner and Samuel Jaques and Michael Naehrig and Martin Roetteler and Mathias Soeken},
title = {Improved Quantum Circuits for Elliptic Curve Discrete Logarithms},
howpublished = {Cryptology ePrint Archive, Paper 2020/077},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/077}},
url = {https://eprint.iacr.org/2020/077}
}

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