On the Semidirect Discrete Logarithm Problem in Finite Groups

Christopher Battarbee; Giacomo Borin; Julian Brough; Ryann Cartor; Tobias Hemmert; Nadia Heninger; David Jao; Delaram Kahrobaei; Laura Maddison; Edoardo Persichetti; Angela Robinson; Daniel Smith-Tone; Rainer Steinwandt

Paper 2024/905

On the Semidirect Discrete Logarithm Problem in Finite Groups

Christopher Battarbee, Sorbonne University

Giacomo Borin, IBM Research Europe, University of Zurich

Julian Brough, Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany

Ryann Cartor, Clemson University

Tobias Hemmert, Bundesamt für Sicherheit in der Informationstechnik, Bonn, Germany

Nadia Heninger, University of California, San Diego

David Jao, University of Waterloo

Delaram Kahrobaei, City University of New York, New York University

Laura Maddison, University of Ottawa

Edoardo Persichetti, Florida Atlantic University

Angela Robinson, National Institute of Standards and Technology

Daniel Smith-Tone, National Institute of Standards and Technology

Rainer Steinwandt, University of Alabama in Huntsville

Abstract

We present an efficient quantum algorithm for solving the semidirect discrete logarithm problem (SDLP) in 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 nonabelian 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 compu- tation 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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A minor revision of an IACR publication in ASIACRYPT 2024
Keywords: Group-Based Cryptography Semidirect Discrete Logarithm Problem Post-Quantum Cryptography
Contact author(s): christopher battarbee @ lip6 fr
giacomo borin @ ibm com
rcartor @ clemson edu
nadiah @ cs ucsd edu
djao @ uwaterloo ca
DKahrobaei @ gc cuny edu
lmadd036 @ uottawa ca
epersichetti @ fau edu
angela robinson @ nist gov
daniel-c smith @ louisville edu
rs0141 @ uah edu
History: 2024-09-20: last of 3 revisions; 2024-06-06: received; See all versions
Short URL: https://ia.cr/2024/905
License: CC BY

BibTeX

@misc{cryptoeprint:2024/905,
      author = {Christopher Battarbee and Giacomo Borin and Julian Brough and Ryann Cartor and Tobias Hemmert and Nadia Heninger and David Jao and Delaram Kahrobaei and Laura Maddison and Edoardo Persichetti and Angela Robinson and Daniel Smith-Tone and Rainer Steinwandt},
      title = {On the Semidirect Discrete Logarithm Problem in Finite Groups},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/905},
      year = {2024},
      url = {https://eprint.iacr.org/2024/905}
}