International Association for Cryptologic Research

International Association
for Cryptologic Research


Generic Models for Group Actions

Julien Duman , Ruhr Universität Bochum
Dominik Hartmann , Ruhr Universität Bochum
Eike Kiltz , Ruhr Universität Bochum
Sabrina Kunzweiler , Ruhr Universität Bochum
Jonas Lehmann , Ruhr Universität Bochum
Doreen Riepel , Ruhr Universität Bochum
DOI: 10.1007/978-3-031-31368-4_15
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2023
Abstract: We define the Generic Group Action Model (GGAM), an adaptation of the Generic Group Model to the setting of group actions (such as CSIDH). Compared to a previously proposed definition by Montgomery and Zhandry (ASIACRYPT~'22), our GGAM more accurately abstracts the security properties of group actions. We are able to prove information-theoretic lower bounds in the GGAM for the discrete logarithm assumption, as well as for non-standard assumptions recently introduced in the setting of threshold and identification schemes on group actions. Unfortunately, in a natural quantum version of the GGAM, the discrete logarithm assumption does not hold. To this end we also introduce the weaker Quantum Algebraic Group Action Model (QAGAM), where every set element (in superposition) output by an adversary is required to have an explicit representation relative to known elements. In contrast to the Quantum Generic Group Action Model, in the QAGAM we are able to analyze the hardness of group action assumptions: We prove (among other things) the equivalence between the discrete logarithm assumption and non-standard assumptions recently introduced in the setting of QROM security for Password-Authenticated Key Exchange, Non-Interactive Key Exchange, and Public-Key Encryption.
  title={Generic Models for Group Actions},
  author={Julien Duman and Dominik Hartmann and Eike Kiltz and Sabrina Kunzweiler and Jonas Lehmann and Doreen Riepel},