Abstract
In the previous research on solving the elliptic curve discrete logarithm problem, quantum resources were concretely estimated. In Banegas et al. (IACR Trans Cryptogr Hardw Embed Syst 2021(1):451–472, 2020. https://doi.org/10.46586/tches.v2021.i1.451-472), the quantum algorithm was optimized for binary elliptic curves, with the main optimization target being the number of the logical qubits. The division algorithm was primarily optimized in Banegas et al. (2020) since every ancillary qubit is used in the division algorithm. In this paper, we propose a new quantum division algorithm on the binary field that uses fewer qubits. Specifically, for elements in a field of 2 n , our algorithm saves n- 3 ⌊ log n⌋ - 2 qubits instead of using n2- 64 n⌊ log (n) ⌋ + O(n) more Toffoli gates, which leads to a more space-efficient quantum algorithm for binary elliptic curves. For the small size n of 16, 127, 163, 233, 283 and 571, both the number of qubits and the number of Toffoli gates are actually reduced. When the size n is 571, the reduction in ancillary qubits amounts to approximately 23% compared to the previous algorithm.
Original language | English |
---|---|
Article number | 237 |
Journal | Quantum Information Processing |
Volume | 22 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2023 Jun |
Bibliographical note
Publisher Copyright:© 2023, The Author(s).
Keywords
- Elliptic curves
- Quantum cryptanalysis
- Quantum resource estimation
- Shor’s algorithm
ASJC Scopus subject areas
- Electronic, Optical and Magnetic Materials
- Statistical and Nonlinear Physics
- Theoretical Computer Science
- Signal Processing
- Modelling and Simulation
- Electrical and Electronic Engineering