Paper 2022/1165

A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

Christopher Battarbee, University of York, Sorbonne University
Delaram Kahrobaei, Queens College, CUNY
Ludovic Perret, Sorbonne University
Siamak F. Shahandashti, University of York
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. PQCrypto 2024
Keywords
key exchangehidden shift problemsemidirect productgroup action
Contact author(s)
cb2036 @ york ac uk
DKahrobaei @ gc cuny edu
ludovic perret @ lip6 fr
siamak shahandashti @ york ac uk
History
2024-06-07: last of 3 revisions
2022-09-06: received
See all versions
Short URL
https://ia.cr/2022/1165
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1165,
      author = {Christopher Battarbee and Delaram Kahrobaei and Ludovic Perret and Siamak F. Shahandashti},
      title = {A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1165},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1165}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.