NOTICE: Due to a lapse in annual appropriations, most of this website is not being updated. Learn more.
Form submissions will still be accepted but will not receive responses at this time. Sections of this site for programs using non-appropriated funds (such as NVLAP) or those that are excepted from the shutdown (such as CHIPS and NVD) will continue to be updated.
An official website of the United States government
Here’s how you know
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
On the Semidirect Discrete Logarithm Problem in Finite Groups
Published
Author(s)
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
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 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.
Battarbee, C.
, Borin, G.
, Brough, J.
, Cartor, R.
, Hemmert, T.
, Heninger, N.
, Jao, D.
, Kahrobaei, D.
, Maddison, L.
, Persichetti, E.
, Robinson, A.
, Smith-Tone, D.
and Steinwandt, R.
(2024),
On the Semidirect Discrete Logarithm Problem in Finite Groups, Cryptology ePrint Archive, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=958103, https://ia.cr/2024/905
(Accessed October 9, 2025)