Paper 2022/501

Another Concrete Quantum Cryptanalysis of Binary Elliptic Curves

Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Harashta Tatimma Larasati, and Howon Kim

Abstract

This paper presents concrete quantum cryptanalysis for binary elliptic curves for a time-efficient implementation perspective (i.e., reducing the circuit depth), complementing the previous research by Banegas et al., that focuses on the space-efficiency perspective (i.e., reducing the circuit width). To achieve the depth optimization, we propose an improvement to the existing circuit implementation of the Karatsuba multiplier and FLT-based inversion, then construct and analyze the resource in Qiskit quantum computer simulator. The proposed multiplier architecture, improving the quantum Karatsuba multiplier by Van Hoof et al., reduces the depth and yields lower number of CNOT gates that bounds to O(nlog2(3)) while maintaining a similar number of Toffoli gates and qubits. Furthermore, our improved FLT-based inversion reduces CNOT count and overall depth, with a tradeoff of higher qubit size. Finally, we employ the proposed multiplier and FLT-based inversion for performing quantum cryptanalysis of binary point addition as well as the complete Shor’s algorithm for elliptic curve discrete logarithm problem (ECDLP). As a result, apart from depth reduction, we are also able to reduce up to 90% of the Toffoli gates required in a single-step point addition compared to prior work, leading to significant improvements and give a new insights on quantum cryptanalysis for a depth-optimized implementation.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Contact author(s)
dedy septono @ pusan ac kr
History
2022-04-28: received
Short URL
https://ia.cr/2022/501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/501,
      author = {Dedy Septono Catur Putranto and Rini Wisnu Wardhani and Harashta Tatimma Larasati and Howon Kim},
      title = {Another Concrete Quantum Cryptanalysis of Binary Elliptic Curves},
      howpublished = {Cryptology ePrint Archive, Paper 2022/501},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/501}},
      url = {https://eprint.iacr.org/2022/501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.