[Resource Topic] 2023/1052: A quantum algorithm for semidirect discrete logarithm problem on elliptic curves

Welcome to the resource topic for 2023/1052

Title:
A quantum algorithm for semidirect discrete logarithm problem on elliptic curves

Authors: Muhammad Imran

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\rtimes \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.

ePrint: https://eprint.iacr.org/2023/1052

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .