Welcome to the resource topic for 2022/1095
Title:
Toffoli gate count Optimized Space-Efficient Quantum Circuit for Binary Field Multiplication
Authors: KIM, SUNYEOP, KIM, INSUNG, Seonggyeom Kim, Seokhie Hong
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.
ePrint: https://eprint.iacr.org/2022/1095
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .