<p>Here is a partial answer:</p>

<p>Sometimes $H'$ is almost universal, but not always.</p>

<p>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)$.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-12-18T03:18:41.657Z
2015-12-18T14:12:03.423Z
2015-12-18T14:12:03.423Z
jbapple
<p>Another case where the constant-time composition in the question produces an almost-universal result is when using Horner's method. In that case <span class="math-container">$f = g$</span>, and also, if <span class="math-container">$a = 0$</span>, the function is <em>not</em> the identity function. That's different than the example in the answer I wrote in December 2015, above.</p>

CC BY-SA 4.0
2020-11-21T15:34:33.353Z
2021-06-20T18:48:02.667Z
2021-06-20T18:48:02.667Z
jbapple
<p>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)))$. </p>

<blockquote>
  <p>Is the family $H' \triangleq \{\langle f,g \rangle : f,g \in H\}$ almost universal?<br>
  If not, what conditions on $H$ would make $H'$ almost universal?</p>
</blockquote>

<p>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".</p>

<p>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.</p>

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

<ds.data-structures><randomness><hash-function>
Shoup-style hashing without one-wayness
jbapple
# Shoup-style hashing without one-wayness

(Asked by: username_0 on 2015-12-16)

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

**Tags:** ds.data-structures, randomness, hash-function

---

## 2 answers

### Answer by username_0 on 2015-12-18. Score: 1

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.


---

### Answer by username_0 on 2020-11-21. Score: 0

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.


---

