Generic Models for Group Actions

Julien Duman; Dominik Hartmann; Eike Kiltz; Sabrina Kunzweiler; Jonas Lehmann; Doreen Riepel

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 Actions CSIDH Generic Group Action Model Algebraic Group Action Model Twists
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: 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},
      note = {\url{https://eprint.iacr.org/2023/186}},
      url = {https://eprint.iacr.org/2023/186}
}