Semigroup Action Problem (SAP) and other Generalizations of the DLP

Appears in collection : 2024 - T3 - WS2 - Emerging topics in design and cryptanalysis of post-quantum schemes

The Discrete Logarithm Problem (DLP) in a group has been a corner stone of modern cryptography. In this overview talk we first show that it is possible to relax the group axioms to consider semigroups and Moufang loops to study the DLP problem. Then we concentrate on the Semigroup Action Problem (SAP) which vastly generalizes the DLP. This general concept was introduced by G. Maze, C. Monico and the speaker in 2002. It encompasses many group based public key protocols currently under intense investigation. It turns out that when the acting semigroup is abelian one readily can build a key exchange as well as onway trapdoor function. For general semigroup actions (not necessarily commutative) one still can create a zero knowledge proof and hence a digital signature protocol. The last part is devoted to construction techniques of interesting semigroup actions starting from semirings. Tropical semirings have been employed by J. Chen, D. Grigoriev and V. Shpilrain. In this talk we concentrate on congruence-simple finite semirings which were classified by J. Zumbrägel in 2008.

Mathematics
and Interactions

Not Only Scalar Curvature Seminar

Geometric structures and discrete group actions / Structures géométriques et actions de groupes discrets

Misha Gromov : Mathematical Description of Biological Structures

Applications of NonCommutative Geometry to Gauge Theories, Field Theories, and Quantum Space-Time / Applications de la Géométrie Non Commutative aux Théories de Jauge, à la Théorie des Champs et aux Espaces-Temps Quantiques

Semigroup Action Problem (SAP) and other Generalizations of the DLP

Information about the video

Citation data

Domain(s)

Bibliography

MSC codes

Last related questions on MathOverflow

Ask a question on MathOverflow

Analytic delta invariant and weighted Kähler geometry Lecture 1

Analytic delta invariant and weighted Kähler geometry Lecture 2

Local dynamics of tangent to the identity biholomorphisms in dimension two lecture 1

Local dynamics of tangent to the identity biholomorphisms in dimension two lecture 2

Local dynamics of tangent to the identity biholomorphisms in dimension two lecture 3

Semigroup Action Problem (SAP) and other Generalizations of the DLP

Information about the video

Citation data

Domain(s)

Bibliography

MSC codes

Last related questions on MathOverflow

Ask a question on MathOverflow

Register