New space-efficient quantum algorithm for binary elliptic curves using the optimized division algorithm

Hyeonhak Kim, Seokhie Hong

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

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 languageEnglish
Article number237
JournalQuantum Information Processing
Volume22
Issue number6
DOIs
Publication statusPublished - 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

Fingerprint

Dive into the research topics of 'New space-efficient quantum algorithm for binary elliptic curves using the optimized division algorithm'. Together they form a unique fingerprint.

Cite this