Let $H$ be an almost universal hash family of functions from $D^2$ to $D$. For any functions $f,g \in H$ define the function $\langle f,g \rangle : D^4 \to D$ by $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$. Is the family $H' \triangleq \{\langle f,g \rangle : f,g \in H\}$ almost universal?  If not, what conditions on $H$ would make $H'$ almost universal?Note that if we instead defined $\langle f,g \rangle(a,b,c,d) \triangleq g(f(a,b),f(c,d))$, $H'$ would be almost universal. This was defined in Wegman and Carter's New hash functions and their use in authentication and set equality, and it is sometimes called tree hash.The scheme in which $\langle f,g \rangle(a,b,c,d) \triangleq f(a,g(b,f(c,d)))$ is a variation on one in Shoup's A composition theorem for universal one-way hash functions. Shoup proves that $H'$ is a family of Universal One-Way Hash Functions if $H$ is a family of Universal One-Way Hash Functions. However, I do not believe the proof works to show that $H'$ is almost universal if $H$ also is.One advantage of Shoup's scheme over Carter and Wegman's is that Shoup's functions can be evaluated with room for only one temporary value from $D$.
Shoup-style hashing without one-wayness
ds.data structures;randomness;hash function