Semigroup Action Problems and Their Uses in Post-Quantum Cryptography

Joachim Rosenthal; Silvia Sconza

Paper 2026/462

Semigroup Action Problems and Their Uses in Post-Quantum Cryptography

Joachim Rosenthal

, University of Zurich

Silvia Sconza

, University of Zurich

Abstract

This survey article provides an overview of the Semigroup Action Problem (SAP) as a pivotal generalization of the Discrete Logarithm Problem (DLP), tracing its theoretical evolution from foundational algebraic cryptography in the early 2000s to its application in the National Institute of Standards and Technology (NIST) Post-Quantum Cryptography (PQC) standardization process. We examine the mathematical framework of semigroup actions, contrasting them with classical group-theoretic assumptions, and detail the generalizations of Diffie-Hellman and ElGamal protocols within this broader context. Finally, the paper investigates the renaissance of group and semigroup actions in the design of next-generation digital signatures, providing a detailed algebraic analysis of candidates in the current NIST competition.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Public Key Cryptography Semigroup Action Problem Post-Quantum Cryptography
Contact author(s): rosenthal @ math uzh ch
silvia sconza @ math uzh ch
History: 2026-03-07: approved; 2026-03-05: received; See all versions
Short URL: https://ia.cr/2026/462
License: CC BY

BibTeX

@misc{cryptoeprint:2026/462,
      author = {Joachim Rosenthal and Silvia Sconza},
      title = {Semigroup Action Problems and Their Uses in Post-Quantum Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/462},
      year = {2026},
      url = {https://eprint.iacr.org/2026/462}
}