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$.


2 Answers 2


Here is a partial answer:

Sometimes $H'$ is almost universal, but not always.

For an example of an $H$ that makes $H'$ almost universal, let $D$ be a field and consider $H_R = \{ h_x(a,b) = a + bx : x \in D\}$. $H_R$ is universal: Consider $(a,b) \neq (c,d)$. If $b \neq d$, then $(\Pr_x h_x(a,b) = h_x(c,d)) = (\Pr_x a + bx = c + dx) = (\Pr_x (b-d)x = c-a) = (\Pr_x x = (c-a)/(b-d)) = |D|^{-1}$. Otherwise, $b=d$, and thus $a \neq c$, and by a similar calculation $h_x(a,b) \neq h_x(c,d)$.

In this case, $\langle f,g \rangle(a,b,c,d)$ is a polynomial of degree $3$, with four terms with different coefficients. If $(a',b',c',d') \neq (a,b,c,d)$, $\langle f,g \rangle(a,b,c,d) - \langle f,g \rangle(a',b',c',d')$ is a polynomial of degree at most $3$ with at least one non-zero coefficient. By Schwartz-Zippel, $H'$ is almost universal.

If $H = \{h_x(a,b) = ax + b : x \in D\}$, then $\langle h_x, h_y \rangle(a,b,c,d) = ax + by + cx + d$, and $(c,b,a,d) \neq (a,b,c,d)$ is guaranteed to have the same hash value. Thus, $H'$ is not almost universal.


Another case where the constant-time composition in the question produces an almost-universal result is when using Horner's method. In that case $f = g$, and also, if $a = 0$, the function is not the identity function. That's different than the example in the answer I wrote in December 2015, above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.