Cryptographic Corollaries of the Classification of Finite Simple Groups
Date:
The Semidirect Discrete Logarithm Problem (SDLP) is a potentially appealing generalisation of the standard Discrete Logarithm Problem (DLP) arising from a more involved algebraic structure. It was hoped that there would be a gap between the quantum complexity of SDLP and that of DLP, allowing for development of post-quantum schemes based on SDLP.Unfortunately, in the case of SDLP with respect to finite groups, this turns out not to be the case. In this talk we present two powerful tools allowing us to reach this conclusion: the first is a method of decomposition of a generic instance of SDLP into several instances of SDLP in a finite simple group; the second is a survey of SDLP in each finite simple group, aided by the celebrated classification theorem.
Based on a joint work with Christopher Battarbee, Ryann Cartor, Nadia Heninger, David Jao, Laura Maddison, Edoardo Persichetti, Angela Robinson, Daniel Smith-Tone, Rainer Steinwandt.
Presented at Crypto Reading Club talk on 2024-Jul-10, see the slides here. See the preprint at ia.cr/2024/905.
Acknowledgments. This collaboration was initiated during the Post-Quantum Group-Based Cryptography workshop at the American Institute of Mathematics (AIM), April 29-May 3, 2024 organized by Delaram Kahrobaei, Ludovic Perret and the AIM team.
Summary:
