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 .