Is it possible to construct a collision-resistant function that hashes a set of values but also allows membership testing?

Essentially, I'm looking for a pair of functions, $\text{H} : \{0,1\}^{**} \rightarrow \{0,1\}^*$ and $\text{M} : \{0,1\}^* \times \{0,1\}^* \rightarrow \{0,1\}$, where $\text{H}$ hashes a set of bitstrings into a single bitstring, and $\text{M}$ checks if a given bitstring was in the set of bitstrings that were hashed.

The security requirement: It must be impossible for any (appropriately bounded) adversary to find a set $x_1,...,x_n$ and value $y$ such that $\text{M}(y,\text{H}(x_1,...,x_n)) \neq y \in \{x_1,...,x_n\}$. I believe this requirement also implies that $\text{H}$ is collision resistant.

A simple solution is to define $\text{H}(x_1,...,x_n) = f(x_1) \| ... \| f(x_n)$ where $f$ is a normal collision-resistant hash function (e.g. SHA-2), and let $\text{M}(x,h)$ return $1$ if $f(x)$ is found in $h$. In this scheme, the output of $\text{H}$ grows linearly with the size of the set.

Is it possible to build a more efficient construction?

  • $\begingroup$ Would a Bloom filter using a cryptographic hash function meet your needs? $\endgroup$ – Ilmari Karonen Jun 11 '17 at 20:20
  • $\begingroup$ @IlmariKaronen I hadn't considered that -- is it possible to bound the probability of false positives? Being able to find a $y$ that passes the membership test would be a problem. $\endgroup$ – Tim McLean Jun 11 '17 at 21:15
  • $\begingroup$ Yes you can bound the expected number of false positives. With one setup you might expect 1%, with another you could get .5%. The article discusses how to calculate the expected rate of false positives. $\endgroup$ – user2460798 Jun 12 '17 at 22:36
  • $\begingroup$ @user2460798 0.5% isn't anywhere near the threshold needed for cryptographic security $\endgroup$ – Tim McLean Jun 13 '17 at 0:13
  • $\begingroup$ On second thought, it looks like the numbers do look kind of reasonable even with a lower probability: 148,000 bits with 100 hash functions for p=2^-100 and n=1024. I might accept an answer based on this construction if it includes a reasonable security argument $\endgroup$ – Tim McLean Jun 13 '17 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.