Toffoli gate count Optimized Space-Efficient Quantum Circuit for Binary Field Multiplication

KIM, SUNYEOP; KIM, INSUNG; Seonggyeom Kim; Seokhie Hong

Paper 2022/1095

Toffoli gate count Optimized Space-Efficient Quantum Circuit for Binary Field Multiplication

KIM, SUNYEOP, Institute of Cyber Security & Privacy (ICSP), Korea University, South Korea

KIM, INSUNG, Institute of Cyber Security & Privacy (ICSP), Korea University, South Korea

Seonggyeom Kim, Institute of Cyber Security & Privacy (ICSP), Korea University, South Korea

Seokhie Hong, Institute of Cyber Security & Privacy (ICSP), Korea University, South Korea

Abstract

Shor's algorithm solves Elliptic Curve Discrete Logarithm Problem(ECDLP) in polynomial time. To optimize Shor's algorithm for binary elliptic curve, reducing the cost for binary field multiplication is essential because it is most cost-critical basic arithmetic. In this paper, we propose Toffoli gate count optimized space-efficient quantum circuits for binary field multiplication. To do so, we take advantage of Karatsuba-like formula and show that its application can be provided without ancillary qubits and optimized them in terms of CNOT gate and depth. Based on the Karatsuba-like formula, we drive a space-efficient CRT-based multiplication with two types of out-of-place multiplication algorithm to reduce CNOT gate cost. Our quantum circuits do not use ancillary qubits and have extremely low TOF gates count where is a function named iterative logarithm that grows very slowly. Compared to recent Karatsuba-based space-efficient quantum circuit, our circuit requires only of Toffoli gate count with comparable depth for cryptographic field sizes . To the best of our knowledge, this is the first result that utilizes Karatsuba-like formula and CRT-based multiplication in quantum circuits.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Quantum Multiplication Karatsuba Multiplication CRT Binary Field Toffoli gate
Contact author(s): kin3548 @ gmail com
History: 2022-08-29: approved; 2022-08-24: received; See all versions
Short URL: https://ia.cr/2022/1095
License: CC0

BibTeX

@misc{cryptoeprint:2022/1095,
      author = {KIM, SUNYEOP and KIM, INSUNG and Seonggyeom Kim and Seokhie Hong},
      title = {Toffoli gate count Optimized Space-Efficient Quantum Circuit for Binary Field Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1095},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1095}
}