International Association for Cryptologic Research

# Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

## Details

Jens Zumbrägel (#805)
Name Jens Zumbrägel
Personal Homepage http://shannoninstitute.ucd.ie/~jzumbr
Institution University of Zurich
Topic of his/her doctorate. Public-key cryptography based on simple semirings
Category public-key cryptography
Keywords discrete logarithm problem, semigroup actions, public-key cryptography, foundations
Ph.D. Supervisor(s) Joachim Rosenthal
Year of completion 2008
Abstract

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 hA=gˆa and hB=gˆb. Finally they compute ha=gˆba and hb=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 ?: AxX?X, (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 h=a.g.
• There is a way to generate pairs of commuting elements of A.

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 cryptosystems.
• 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 isomorphism.

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.