Paper 2022/1095

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

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 $(\mathbb{F}_{2^{n}})$ 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 $O(n2^{\log_{2}^{\ast}n})$ where $\log_{2}^{\ast}$ is a function named iterative logarithm that grows very slowly. Compared to recent Karatsuba-based space-efficient quantum circuit, our circuit requires only $(12 \sim 24 \% )$ of Toffoli gate count with comparable depth for cryptographic field sizes $(n = 233 \sim 571)$. To the best of our knowledge, this is the first result that utilizes Karatsuba-like formula and CRT-based multiplication in quantum circuits.