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.

Presentation

Cryptographic Corollaries of the Classification of Finite Simple Groups: Analysis of a candidate problem in post-quantum cryptography

July 10, 2024

Presenters

Christopher Battarbee - Sorbonne University (France)
Giacomo Borin - IBM Research Zurich & University of Zurich (Switzerland)

Description

Abstract. 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 joint work with Ryann Cartor, Nadia Heninger, David Jao, Laura Maddison, Edoardo Persichetti, Angela Robinson, Daniel Smith-Tone, Rainer Steinwandt.

Suggested readings: ia.cr/2022/1165, ia.cr/2023/1953, ia.cr/2024/905

Presented at

Crypto Reading Club talk on 2024-Jul-10

Parent Project

See: Crypto Reading Club

Related Topics

Security and Privacy: cryptography

Created June 20, 2024, Updated July 11, 2024