Hash of multiset of values, which lets me compute the hash of the union

Question

Cryptographic hash functions normally take as input a bitstring.

I am looking for a hash function that takes as input a finite multiset of values. In other words, given $S \subset \{0,1\}^*$, I want to compute $H(S)$, a hash of $S$. Also, I would like this function to be chosen so that given the hashes $H(S),H(T)$ of two multisets $S,T$, I can efficiently compute the hash $H(S \cup T)$ of their union. (If you like, you can think of this as a sort of associativity property.)

I would prefer a hash function that behaves essentially like a random oracle on this domain.

Are there any good constructions? Are there any constructions that are based upon a standard hash function and whose security is reducible to the security of the underlying hash?

---

Here is another way to think about it. I want a hash function that accepts a sequence of bit-strings as input. If the input is $x_1,\dots,x_m \in \{0,1\}^*$, I'll let $H(x_1,\dots,x_m)$ denote the output. I want this function to have two properties:

• Commutative: If $y_1,\dots,y_m$ is a re-ordering of $x_1,\dots,x_m$, then $H(x_1,\dots,x_m) = H(y_1,\dots,y_m)$.

• Associative: Given $H(x_1,\dots,x_m)$ and $H(y_1,\dots,y_n)$, there is an efficient way to compute $H(x_1,\dots,x_m,y_1,\dots,y_n)$ (without knowing the underlying entries $x_1,\dots,x_m,y_1,\dots,y_n$).

Answer 1

One solution is a group-based hash function. Choose an abelian group $(G,+)$ and a conventional hash function $h:\{0,1\}^* \to G$. Then, set

$$H(S) = \sum_{x \in S} h(x),$$

or in other words,

$$H(x_1,\dots,x_m) = h(x_1) + h(x_2) + \cdots + h(x_m),$$

where $+$ represents the group operation of $G$. Notice that this is commutative. It is also associative: given $H(S),H(T)$, it is easy to compute $H(S \cup T) = H(S) + H(T)$.

The security of this depends partially upon the choice of $G$. Here are some sample instantiations:

• If you choose $G=(\mathbb{Z}/p\mathbb{Z},+)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name AdHash. I would expect this to provide approximately 80-bit security if you choose $p \approx 2^{1600}$.

• If you choose $G=((\mathbb{Z}/p\mathbb{Z})^*,\times)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name MuHash. I would expect this to provide approximately 80-bit security if you choose $p$ such that the discrete log problem modulo $p$ provides at least $2^{80}$ security.

• If you choose $G=(GF(2^n),+)$ (i.e., the group operation is xor of $n$-bit strings), the resulting scheme is insecure: it can be broken using a simple linear algebra based attack.

See also https://crypto.stackexchange.com/a/5231/351