International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On the Semidirect Discrete Logarithm Problem in Finite Groups

Authors:
Christopher Battarbee , Sorbonne University
Giacomo Borin , IBM Zurich & UZH
Ryann Cartor , Clemson University
Nadia Heninger , University of California, San Diego
David Jao , University of Waterloo
Laura Maddison , University of Ottawa
Edoardo Persichetti , Florida Atlantic University
Angela Robinson , NIST
Rainer Steinwandt , University of Alabama in Huntsville
Daniel Smith-Tone , NIST
Delaram Kahrobaei , Departments of Computer Science and Mathematics, Queens College, City University of New York, U.S.} and {Department of Computer Science and Engineering, Tandon School of Engineering, New York University, U.S.
Tobias Hemmert , Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany
Julian Brough , Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: We present an efficient quantum algorithm for solving the semidirect discrete logarithm problem ($\SDLP$) in \emph{any} finite group. The believed hardness of the semidirect discrete logarithm problem underlies more than a decade of works constructing candidate post-quantum cryptographic algorithms from non-abelian groups. We use a series of reduction results to show that it suffices to consider $\SDLP$ in finite simple groups. We then apply the celebrated Classification of Finite Simple Groups to consider each family. The infinite families of finite simple groups admit, in a fairly general setting, linear algebraic attacks providing a reduction to the classical discrete logarithm problem. For the sporadic simple groups, we show that their inherent properties render them unsuitable for cryptographically hard $\SDLP$ instances, which we illustrate via a Baby-Step Giant-Step style attack against $\SDLP$ in the Monster Group. Our quantum $\SDLP$ algorithm is fully constructive, up to the computation of maximal normal subgroups, for all but three remaining cases that appear to be gaps in the literature on constructive recognition of groups; for these cases $\SDLP$ is no harder than finding a linear representation. We conclude that $\SDLP$ is not a suitable post-quantum hardness assumption for any choice of finite group.
BibTeX
@inproceedings{asiacrypt-2024-34654,
  title={On the Semidirect Discrete Logarithm Problem in Finite Groups},
  publisher={Springer-Verlag},
  author={Christopher Battarbee and Giacomo Borin and Ryann Cartor and Nadia Heninger and David Jao and Laura Maddison and Edoardo Persichetti and Angela Robinson and Rainer Steinwandt and Daniel Smith-Tone and Delaram Kahrobaei and Tobias Hemmert and Julian Brough},
  year=2024
}