Paper 2023/186

Generic Models for Group Actions

Julien Duman, Ruhr University Bochum
Dominik Hartmann, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum
Sabrina Kunzweiler, Ruhr University Bochum
Jonas Lehmann, Ruhr University Bochum
Doreen Riepel, Ruhr University Bochum
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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in PKC 2023
Keywords
Group ActionsCSIDHGeneric Group Action ModelAlgebraic Group Action ModelTwists
Contact author(s)
julien duman @ rub de
dominik hartmann @ rub de
eike kiltz @ rub de
sabrina kunzweiler @ rub de
jonas lehmann-c6j @ rub de
doreen riepel @ rub de
History
2023-02-15: approved
2023-02-13: received
See all versions
Short URL
https://ia.cr/2023/186
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/186,
      author = {Julien Duman and Dominik Hartmann and Eike Kiltz and Sabrina Kunzweiler and Jonas Lehmann and Doreen Riepel},
      title = {Generic Models for Group Actions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/186},
      year = {2023},
      url = {https://eprint.iacr.org/2023/186}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.