Dissertations, Theses, and Capstone Projects

Date of Degree

6-2016

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Vladimir Shpilrain

Committee Members

Vladimir Shpilrain

Delaram Kahrobaei

Melvyn Nathanson

Benjamin Steinberg

Subject Categories

Information Security | Number Theory | Other Applied Mathematics

Keywords

Cryptography, hash functions, discrete logarithm

Abstract

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.

Download

Share

COinS