The discrete logarithm problem is the basic ingredient of many
public-key cryptosystems. It can be stated as follows: Given a
cyclic group (G,?) of order n, a
generator g of G, and another
element h?G, find the unique
integer a?[0,n) such that
h=gˆa. The integer a is called
the discrete logarithm of
h to the base g.
There are key agreement protocols, public-key encryption schemes,
and digital signatures employing the discrete logarithm problem.
One example is the Diffie-Hellman key agreement protocol. It allows
two parties, A and B, to agree on a secret key over an insecure
channel. In order to achieve this goal they fix a finite cyclic
group G and a generator g of G. Then A and B
pick random integers a,b respectively and exchange
and hB=gˆb. Finally they
and hAˆb=gˆab, and
since gˆab=gˆba this element
can be used as their secret key.
It is clear that solving the underlying discrete logarithm problem
is sufficient for breaking the Diffie-Hellman protocol. For this
reason one has been searching for groups in which the discrete
logarithm problem is considered to be a computationally hard
problem. Among the groups that have been proposed as candidates are
the multiplicative group of a finite field and the group over an
elliptic curve. It should however be pointed out that the
infeasibility of the discrete logarithm problem has not been proved
in any concrete group.
Discrete logarithm based cryptosystems can be generalized in the
framework of semigroup actions (see e.g. [Maze, Monico,
Rosenthal, 2007]). Here, an action
(a,x)?a.x of a semigroup A
on a set X substitutes the role of the exponentiation
(Zn,?)xG?G in a cyclic
group G of order n. The semigroup action must satisfy
(at least) the following two conditions.
- The semigroup action discrete logarithm (SDL) problem
is hard: Given elements g,h?X such
that h?A.g, the orbit generated
by g, find an element a?A such that
- There is a way to generate pairs of commuting elements
It is an open problem at this point whether the SDL problem is
harder to solve than the discrete logarithm problem. If this is
true, the parameter sizes could be reduced in comparison to the
discrete logarithm based protocols, leading to more efficient
cryptosystems. To explore this issue it is clearly beneficial to
create and study many examples.
A novel and promising approach to build interesting semigroup
actions is based on finite simple semirings. A concrete example of
such a construction is a two-sided action of matrices over a
semiring. In order to avoid a Pohlig-Hellman-type reduction attack
it is important that the semiring involved is simple.
The theoretical main result of this thesis is a full classification of
finite simple semirings, analogous to the Wedderburn-Artin theorem.
The result provides numerous examples which come from monoid
endomorphism semirings of finite lattices. Due to this result it is
possible to construct very large simple semirings using moderate
computational resources, and this leads to new constructions of
interesting semigroup actions for public-key cryptography. It will
require further research to analyze these new systems.
The present thesis deals basically with three matters:
- We discuss semigroup actions and their use in cryptography,
aiming to clarify the requirements needed to construct secure
- We introduce semirings and give the classification of finite
simple semirings up to isomorphism.
- We study the applications of simple semirings to the
construction of semigroup actions for cryptography.
The first chapter introduces encryption schemes and digital
signature schemes, including rigorous definitions of their security.
Some discrete logarithm based cryptosystems and their underlying
security assumptions will be discussed.
The second chapter is about cryptography based on semigroup
actions. We present generalizations of the discrete logarithm based
cryptosystems, and discuss the hardness of the underlying semigroup
action problems. Moreover, we show that many proposals of
cryptosystems in the literature of the last decade can be embedded
into the setting of semigroup actions.
The third chapter deals with semirings and gives a full
classification of finite simple semirings with zero. The result
states that a finite semiring of order >2 with zero which is not a
ring is simple if and only if it is isomorphic to a
"dense" subsemiring of the endomorphism semiring of a
finite idempotent commutative monoid. We also investigate those
subsemirings further, considering e.g. the question of
In the final chapter we discuss the applications of the
classification for cryptography: We present different methods to
construct semigroup actions based on simple semirings.