Semirings and semigroup actions in public-key cryptography

In this dissertation, several generalizations of cryptographic protocols based on the Discrete Logarithm Problem (DLP) are examined.; It is well known that the Pohlig-Hellman algorithm can reduce the computation of a DLP in an abelian group to the computation of DLPs in simple abelian groups. As an example of this, we consider the DLP in rings of the form $Fqx/I$, where I is a zero-dimensional ideal. This example culminates in an interesting primary decomposition algorithm for zero-dimensional ideals (over $Q$).; In the next chapter, we consider the possible difficulty of the DLP in semirings. Since more general versions of the Pohlig-Hellman algorithm may apply, an extended discussion of finite, additively commutative, congruence-free (i.e., simple) semirings follows. We classify such semirings, except for the additively idempotent ones.; Finally, a generalization of the DLP itself is discussed. It is shown that every semigroup action on a finite set gives rise to a Diffie-Hellman type protocol. A Pollard-rho type algorithm is given for solving instances of the group action problem. A particular semigroup action of Mat _n($Z$) on Hn, where H is an abelian semigroup, is discussed as an example where the semigroup action problem may be hard enough to build a cryptosystem on it.