Hash function constructions from expander graphs are described. In one aspect, an expander graph is walked to compute a hash function. The expander graph is walked using respective subsets of an input message. A label of a last vertex walked is an output of the hash function.