Date of Degree


Document Type


Degree Name





Vladimir Shpilrain

Committee Members

Vladimir Shpilrain

Delaram Kahrobaei

Melvyn Nathanson

Benjamin Steinberg

Subject Categories

Information Security | Number Theory | Other Applied Mathematics


Cryptography, hash functions, discrete logarithm


In 1994, Tillich and Zemor proposed a scheme for a family of hash functions that uses products of matrices in groups of the form $SL_2(F_{2^n})$. In 2009, Grassl et al. developed an attack to obtain collisions for palindromic bit strings by exploring a connection between the Tillich-Zemor functions and maximal length chains in the Euclidean algorithm for polynomials over $F_2$.

In this work, we present a new proposal for hash functions based on Cayley graphs of semigroups. In our proposed hash function, the noncommutative semigroup of linear functions under composition is considered as platform for the scheme. We will also discuss its efficiency, pseudorandomness and security features.

Furthermore, we generalized the Fit-Florea and Matula's algorithm (2004) that finds the discrete logarithm in the multiplicative group of integers modulo $2^k$ by establishing a connection between semi-primitive roots modulo $2^k$ where $k\geq 3$ and the logarithmic base used in the algorithm.

This work is embargoed and will be available for download on Wednesday, April 25, 2018

Graduate Center users:
To read this work, log in to your GC ILL account and place a thesis request.

Non-GC Users:
See the GC’s lending policies to learn more.