(2026-03) Semigroup Action Problems and Their Uses in Post-Quantum Cryptography
2026-03-05
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.