In the past years, research on Shor's algorithm for solving elliptic curves for discrete logarithm problems (Shor's ECDLP), the basis for cracking elliptic curve-based cryptosystems (ECC), has started to garner more significant interest. To achieve this, most works focus on quantum point addition subroutines to realize the double scalar multiplication circuit, an essential part of Shor's ECDLP, whereas the point doubling subroutines are often overlooked. In this paper, we investigate the quantum point doubling circuit for the stricter assumption of Shor's algorithm when doubling a point should also be taken into consideration. In particular, we analyze the challenges on implementing the circuit and provide the solution. Subsequently, we design and optimize the corresponding quantum circuit, and analyze the high-level quantum resource cost of the circuit. Additionally, we discuss the implications of our findings, including the concerns for its integration with point addition for a complete double scalar multiplication circuit and the potential opportunities resulting from its implementation. Our work lays the foundation for further evaluation of Shor's ECDLP.

arXiv:2306.07530Jun 13, 20230 citations

Enhancing Quantum Cryptanalysis of Binary Elliptic Curves Through Optimized Out-of-Place Point Addition and ECPM Integration

Dedy Septono Catur Putranto, Rini Wisnu Wardhani, Howon Kim

Shor’s algorithm remains a cornerstone of quantum cryptanalysis, driving active research into reducing quantum resource overheads in both spatial and temporal dimensions. This work presents a dual-optimization framework targeting resource-efficient Shor-based quantum cryptanalysis on binary elliptic curves. Our approach conducts a comprehensive resource assessment across multiple abstraction levels—ranging from finite field arithmetic to elliptic curve group operations. At the low-level layer, we benchmark various quantum arithmetic constructor designs—including GCD-based, FLT-based, FLT-Basic or extended variants, in-place, and out-of-place execution models—analyzing Toffoli gate counts, qubit requirements, and circuit depths. At the group operation layer, we examine point addition and doubling circuits, employing complete iterations of Shor’s algorithm with elliptic curve point multiplication (ECPM) that require point addition (PA) only (with (2n+ 2) PA) and point doubling (PD) utilization (2nPD + 2 PA). We further simulate selected (2nPD + 2 PAoutplace) circuit designs, highlighting the advantages of optimized out-of-place PA circuits and integrated ECPM techniques from prior work. Additionally, we explore decompositions of multi-controlled gates to achieve a practical trade-off between qubit count and overall depth.

IEEE AccessJan 1, 20250 citations