Quantum Cryptanalysis Landscape of Shor's Algorithm for Elliptic Curve Discrete Logarithm Problem.

Shor’s algorithm is recognized as one of the most influential algorithms that shape the research interest in quantum computation and quantum cryptanalysis today. In particular, the algorithm is one of the firsts to show clear applicability of quantum computation to solve classically intractable problems underpinning the widely used public-key cryptosystems (i.e., RSA and ECC), igniting an ever-growing research interest in the respective fields. However, of the two algorithms introduced by Peter Shor in 1994, i.e., Shor’s quantum factoring algorithm and Shor’s discrete logarithm problem, the latter is not discussed as often. In this paper, we discuss the works done on Shor’s algorithm to solve the elliptic curve discrete logarithm problem. In particular, we introduce the methods and optimizations proposed by researchers from the early era to the most recent ones and map them to obtain a comprehensive overview of the existing works. From our mapping, we analyze some of the trends in optimizations that help carve the research direction in Shor’s algorithm for the elliptic curve discrete logarithm problem.