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