Published: December 12, 2024
Author(s)
Christopher Battarbee (Sorbonne Universities), Giacomo Borin (IBM Research Europe, University of Zurich), Julian Brough (BSI), Ryann Cartor (Clemson University), Tobias Hemmert (BSI), 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 (NIST), Daniel Smith-Tone (NIST, University of Louisville), Rainer Steinwandt (University of Alabama in Huntsville)
Conference
Name: Asiacrypt 2024
Dates: 12/09/2024 - 12/13/2024
Location: Kolkata, India
Citation: Advances in Cryptology – ASIACRYPT 2024, vol. 15491, pp. 330-357
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.
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...
See full 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.
Hide full abstract
Keywords
Group-Based Cryptography; Semidirect Discrete Logarithm Problem; Post-Quantum Cryptography
Control Families
None selected
