Alternative Generators of the Zémor-Tillich Hash Function: A Quest for Freedom in Projective Linear Groups

Abstract

Introduced in 1994, the celebrated Zémor-Tillich hash function over SL_2(F_{2^n}) is mathematically elegant, efficient, and now finally broken (Grassl et. al, 2011). Yet, with a new choice of generators Tillich and Zémor's construction over SL_2(F_{2^n}) still remains of interest; looking for generators in GL_2(F_{p^n}) seems almost untouched. Here, we present a large class of generators to choose from, using a novel theorem that outlines conditions under which a set of matrices in PGL_2(F_p((x))) generates a free group, and whose proof is an interesting application of Tits' ``Ping-Pong Lemma" (1972). The hash functions we form from this theorem are secure against known attacks, and simultaneously preserve many of the desired features of the Zémor-Tillich hash function. In particular, our hash functions retain the small modifications property that Zémor-Tillich was known for: for some δ, alterations of less than δ bits will necessarily change the hash value.