Cryptographic Group and Semigroup Actions

Oliver W. Gnilke; Jens Zumbrägel

Paper 2023/017

Cryptographic Group and Semigroup Actions

Oliver W. Gnilke, Aalborg University

Jens Zumbrägel, University of Passau

Abstract

We consider actions of a group or a semigroup on a set, which generalize the setup of discrete logarithm based cryptosystems. Such cryptographic group actions have gained increasing attention recently in the context of isogeny-based cryptography. We introduce generic algorithms for the semigroup action problem and discuss lower and upper bounds. Also, we investigate Pohlig-Hellman type attacks in a general sense. In particular, we consider reductions provided by non-invertible elements in a semigroup, and we deal with subgroups in the case of group actions.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: discrete logarithm problem cryptographic group action semigroup action problem
Contact author(s): owg @ math aau dk
jens zumbraegel @ uni-passau de
History: 2023-01-05: approved; 2023-01-04: received; See all versions
Short URL: https://ia.cr/2023/017
License: CC BY

BibTeX

@misc{cryptoeprint:2023/017,
      author = {Oliver W. Gnilke and Jens Zumbrägel},
      title = {Cryptographic Group and Semigroup Actions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/017},
      year = {2023},
      url = {https://eprint.iacr.org/2023/017}
}