A Subexponential Quantum Algorithm for the Semdirect Discrete Logarithm Problem

Christopher Battarbee, Delaram Kahrobaei, Ludovic Perret, Siamak F. Shahandashti

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Group-based cryptography is a relatively unexplored family in post-quantum cryptography, and the so-called Semidirect Discrete Logarithm Problem (SDLP) is one of its most central problems. However, the complexity of SDLP and its relationship to more well-known hardness problems, particularly with respect to its security against quantum adversaries, has not been well understood and was a significant open problem for researchers in this area. In this paper we give the first dedicated security analysis of SDLP. In particular, we provide a connection between SDLP and group actions, a context in which quantum subexponential algorithms are known to apply. We are therefore able to construct a subexponential quantum algorithm for solving SDLP, thereby classifying the complexity of SDLP and its relation to known computational problems.
Original languageEnglish
Title of host publicationPost-Quantum Cryptography 2024
Subtitle of host publicationproceedings
ISBN (Electronic)978-3-031-62743-9
Publication statusPublished - 14 Jun 2024
EventPost-Quantum Cryptography 2024 - University of Oxford, Mathematical Institute, Oxford, United Kingdom
Duration: 12 Jun 202414 Jun 2024

Publication series

NameLecture Notes in Computer Science


ConferencePost-Quantum Cryptography 2024
Abbreviated titlePQCrypto 2024
Country/TerritoryUnited Kingdom
Internet address

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.


  • discrete logarithm
  • semidirect product
  • group-based cryptography
  • semidirect-product key exchange
  • key exchange

Cite this