A Subexponential Quantum Algorithm for the Semidirect Discrete Logarithm Problem

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.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. arXiv
Keywords
key exchange hidden shift problem semidirect product group action
Contact author(s)
cb2036 @ york ac uk
DKahrobaei @ gc cuny edu
ludovic perret @ lip6 fr
siamak shahandashti @ york ac uk
History
2022-11-02: revised
See all versions
Short URL
https://ia.cr/2022/1165

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},
note = {\url{https://eprint.iacr.org/2022/1165}},
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.