Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
1  
it sounds that you need a homomorphic hash function if exists –  curious Nov 1 '13 at 0:43

1 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 MulHash. 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 http://crypto.stackexchange.com/a/5231/351

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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