A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

09/06/2022
by   Christopher Battarbee, et al.
0

Group-based cryptography is a relatively young family in post-quantum cryptography. In this paper we give the first dedicated security analysis of a central problem in group-based cryptography: the so-called Semidirect Product Key Exchange (SDPKE). We present a subexponential quantum algorithm for solving SDPKE. To do this we reduce SDPKE to the Abelian Hidden Shift Problem (for which there are known quantum subexponential algorithms). We stress that this does not per se constitute a break of SDPKE; rather, the purpose of the paper is to provide a connection to known problems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset