# A hash function for sets that from a hash of a set and a subset of it doesn't reveal the hash of the remaining elements in the set

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}.$$
• Correct, since it would imply a weakness in the original hash $h(\cdot)$ as applied to strings – kodlu Nov 1 at 23:09