Paper 2023/1052

A quantum algorithm for semidirect discrete logarithm problem on elliptic curves

Abstract

Shor's algorithm efficiently solves the discrete logarithm problem (DLP) by taking advantage of the commutativity structure of the group underlying the problem. To counter Shor's algorithm, Horan et al. propose a DLP analogue in the semidirect product semigroup $G⋊\mathrm{End}(G)$, given a (semi)group $G$, to construct a quantum-resistant Diffie-Hellman key exchange based on it. For general (semi)groups, the semidirect discrete logarithm problem (SDLP) can be reduced to the hidden shift problem where Kuperberg's subexponential quantum algorithm is applicable. In this paper, we consider a specific case where $G$ is an elliptic curve over a finite field and we show that SDLP on elliptic curves can be solved efficiently using an adaptation of Shor's algorithm for the standard elliptic curve discrete logarithm problem (ECDLP). The key implication of the result is that one should not use elliptic curves as the platforms for the semidirect product key exchange.