Skip to main content

Tove Gertonsson: An Introduction to Cayley Hash Functions

Time: Thu 2021-06-03 12.30 - 13.30

Location: Meeting ID: 697 4204 2109

Respondent: Tove Gertonsson

Export to calendar

Abstract

This paper will explore a type of hash function based on Cayley graphs, called Cayley hash functions. The main idea of such hash functions is to use a pair of generators of a monoid to hash the 0 and 1 bit respectively, and a bit string is then hashed by applying the monoid operation to the elements. We will be focusing on Zémor's first proposal of such a function from 1991, in which the generators are 2 by 2 matrices from the special linear group with entries over the integers. The operation is matrix multiplication, and the entries of the resulting matrix product are reduced modulo a large prime, so that we obtain entries over a finite field. We shall see, however, how this first hashing scheme became subject to a lifting attack produced by Zémor and Tillich in 1993. In response, Bromberg introduced different pairs of generators that are safe from the lifting attack. We will familiar ourselves also with these generators, and provide an intuitive understanding of why Bromberg's suggestion of matrix choice is immune from the lifting attack. Further, we will calculate a lower bound on the length of collisions for one pair of generators suggested by Bromberg.

Zoom notes: Password required, contact arias@math.su.se