Paper 2023/553
Concrete Quantum Cryptanalysis of Binary Elliptic Curves via Addition Chain
Abstract
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 degree
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. Minor revision. CT-RSA2023
- Keywords
- ECDLPquantum cryptanalysisFLT-based inversionquantum resource estimateaddition chain
- Contact author(s)
-
rtaguchi-495 @ g ecc u-tokyo ac jp
takayasu-a @ g ecc u-tokyo ac jp - History
- 2023-08-03: revised
- 2023-04-19: received
- See all versions
- Short URL
- https://ia.cr/2023/553
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/553, author = {Ren Taguchi and Atsushi Takayasu}, title = {Concrete Quantum Cryptanalysis of Binary Elliptic Curves via Addition Chain}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/553}, year = {2023}, url = {https://eprint.iacr.org/2023/553} }