Concrete Quantum Cryptanalysis of Binary Elliptic Curves via Addition Chain
Concrete Quantum Cryptanalysis of Binary Elliptic Curves via Addition Chain
复制标题
基于加法链的二元椭圆曲线的具体量子密码分析
DOI：
10.1007/978-3-031-30872-7_3
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Ren Taguchi and Atsushi Takayasu
中科院分区：
文献类型：
--
作者：
陸子健;金勇;山井成良;友石正彦;Ren Taguchi and Atsushi Takayasu
Thus far, several papers reported concrete resource estimates of Shor’s quantum algorithm for solving the elliptic curve discrete logarithm problem (ECDLP). In this paper, we study quantum FLT-based inversion algorithms over binary elliptic curves. There are two major algorithms proposed by Banegas et al. and Putranto et al., where the former and latter algorithms achieve fewer numbers of qubits and smaller depths of circuits, respectively. We propose two quantum FLT-based inversion algorithms that essentially outperform previous FLT-based algorithms and compare the performance for NIST curves of the degreen. Specifically, for alln, our first algorithm achieves fewer qubits than Putranto et al.’s one without sacrificing the number of Toffoli gates and the depth of circuits, while our second algorithm achieves smaller depths of circuits without sacrificing the number of qubits and Toffoli gates. For example, when, the number of qubits of our first algorithm is 74% of that of Putranto et al.’s one, while the depth of our second algorithm is 83% of that of Banegas et al.’s one. The improvements stem from the fact that FLT-based inversions can be performed with arbitrary sequences of addition chains foralthough both Banegas et al. and Putranto et al. follow fixed sequences that were introduced by Itoh and Tsujii’s classical FLT-based inversion. In particular, we analyze how several properties of addition chains, which do not affect the computational resources of classical FLT-based inversions, affect the computational resources of quantum FLT-based inversions and find appropriate sequences.
