SL2 homomorphic hash functions: Worst case to average case reduction and short collision search

Ciaran Mullan, Boaz Tsaban

We study homomorphic hash functions into SL(2,q), the 2x2 matrices with determinant 1 over the field with $q$ elements. Modulo a well supported number theoretic hypothesis, which h…