Paper 2024/228
On the Untapped Potential of the Quantum FLTbased Inversion
Abstract
Thus far, several papers estimated concrete quantum resources of Shor’s algorithm for solving a binary elliptic curve discrete logarithm problem. In particular, the complexity of computing quantum inversions over a binary field F2n is dominant when running the algorithm, where n is a degree of a binary elliptic curve. There are two major methods for quantum inversion, i.e., the quantum GCDbased inversion and the quantum FLTbased inversion. Among them, the latter method is known to require more qubits; however, the latter one is valuable since it requires much fewer Toffoli gates and less depth. When n = 571, KimHong’s quantum GCDbased inversion algorithm (Quantum Information Processing 2023) and TaguchiTakayasu’s quantum FLTbased inversion algorithm (CTRSA 2023) require 3, 473 qubits and 8, 566 qubits, respectively. In contrast, for the same n = 571, the latter algorithm requires only 2.3% of Toffoli gates and 84% of depth compared to the former one. In this paper, we modify TaguchiTakayasu’s quantum FLTbased inversion algorithm to reduce the required qubits. While TaguchiTakayasu’s FLTbased inversion algorithm takes an addition chain for n−1 as input and computes a sequence whose number is the same as the length of the chain, our proposed algorithm employs an uncomputation step and stores a shorter one. As a result, our proposed algorithm requires only 3, 998 qubits for n = 571, which is only 15% more than KimHong’s GCDbased inversion algorithm. Furthermore, our proposed algorithm preserves the advantage of FLTbased inversion since it requires only 3.7% of Toffoli gates and 77% of depth compared to KimHong’s GCDbased inversion algorithm for n = 571.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Published elsewhere. Minor revision. ACNS2024
 DOI
 10.1007/9783031547737_4
 Keywords
 ECDLPquantum cryptanalysisFLTbased inversionquantum resource estimateaddition chain
 Contact author(s)

rtaguchi495 @ g ecc utokyo ac jp
takayasua @ g ecc utokyo ac jp  History
 20240219: revised
 20240214: received
 See all versions
 Short URL
 https://ia.cr/2024/228
 License

CC0
BibTeX
@misc{cryptoeprint:2024/228, author = {Ren Taguchi and Atsushi Takayasu}, title = {On the Untapped Potential of the Quantum {FLT}based Inversion}, howpublished = {Cryptology ePrint Archive, Paper 2024/228}, year = {2024}, doi = {10.1007/9783031547737_4}, note = {\url{https://eprint.iacr.org/2024/228}}, url = {https://eprint.iacr.org/2024/228} }