An Improvement of the Ajtai-GGH Hash Function

Abstract: A desirable goal in cryptography is the construction of cryptographic functions that are provably hard to break (on the average), under some standard (worst-case) computational complexity assumption. Recently, lattices have attracted considerable interest for their potential cryptographic applications because of a remarkable connection between their worst-case and average-case complexity. In 1996, Ajtai showed that if there is no algorithm that approximately solves the (decisional) shortest vector approximation problem for any lattice within some polynomial factor, then the shortest vector (search) problem is hard to solve exactly when the lattice is chosen at random according to a certain easily samplable distribution.

Building on this result, Ajtai, Goldreich, Goldwasser and Halevi constructed a hash function at least as hard to invert on the average as the worst case complexity of approximating certain lattice problems within a polynomial factor. We will describe a hash function family which generalizes and improves the Ajtai-GGH hash functions.