I'm looking for a function to compute a hash of a set.

It needs to satisfy two properties:

  1. If someone published a hash hs of a set s and a hash hs' of some subset of it s', I should not be able to compute the hash of s - s' using hs and hs'.

  2. From hashes hs1 and hs2 of two sets that have no elements in common I shall be able to compute the hash hs of their union.

Does such hash function exist?

Let's formalize your encoding of the sets $S$ (assumed to be the subsets of some universal set $$\Omega=\{\omega_1,\ldots,\omega_n\}\leftrightarrow (1,\ldots,1)$$ as the string $$E(S)=(\mathbb{1}\{ w_k \in S\}: 1\leq k \leq n)$$ which has a $1$ in the $k^{th}$ position if and only if $w_k$ is an element of $S.$ So to hash a set you hash its encoding $E(S).$

Note that any good hash function should have the avalanche property; i.e., if a bit is flipped (say an element is added or removed from $S$ to obtain $S'$) the two hashes $h(E(S)),$ and $h(E(S'))$ should not be easy to determine from each other, the property you want should hold provided $n$ is large enough so that it can't be brute forced for a collision, say $n>2^{512}.$

If the universe is not so large, you may need to use some kind of salting to increase the strength of the hash function.

  • Seems like I would not be able to to compute a hash of the union by only knowing the hashes of the two sets? – Ishamael Nov 1 at 18:30
  • Correct, since it would imply a weakness in the original hash $h(\cdot)$ as applied to strings – kodlu Nov 1 at 23:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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