# Hash which can be used to verify one of multiple inputs?

Is there a hash function H1 which, when given inputs a, b, etc., produces output Z, and an H2 which can verify any one of a, b, etc. when given Z like this:

H1(a, b) => Z
H2(Z, a) => true
H2(Z, b) => true
H2(Z, c) => false


And where Z is (currently thought to be) cryptographically secure (i.e., modifying Z in any knowable way makes H2 return false for any of the provided inputs)?

Edit: An additional condition which I forgot to articulate originally. a cannot be derived from b and Z, and b from a and Z. Without this condition, we can just use Shamir's Secret Sharing, with a k value of 1, a randomly generated secret Z and a, b, etc are our n values.

• I'd love to see if this can be done. Jan 15, 2015 at 2:32
• I suspect there is no established way of doing this, but I don't see any theoretical reason it can't be done. All I need is an answer from Adi Shamir! Jan 15, 2015 at 9:31
• If you want to keep your assumption, that $H_1$ and $H_2$ are hash functions, then this is very unlikely to exist. Because in this case, $H_2$ could somehow identify partial-preimages of $Z$... Then either $H_1$ is not a cryptographically secure hash function or $H_2$ is not computationally feasible.
– tylo
Jan 15, 2015 at 14:08
• @tylo While I agree that this is quite unlikely to be a secure hash function in the "standard" meaning of the term, I feel that such a thing is somewhat similar to a hash function: the goal is comparable in that it is very hard to obtain a preimage, but it is easy to check whether a given message is a preimage. In this case, the only difference is that it is also easy to verify that something was part of the preimage (which is a set), but only if you already know that thing. Jan 15, 2015 at 15:59
• That has nothing to do with the term hash function, even without the property cryptographically secure. Because what you need to achieve something like that is a trapdoor one-way function.
– tylo
Jan 16, 2015 at 12:49

What you are looking for reminds me of one-way accumulator functions [1]. Basically, a one-way accumulator permits to prove the membership of an element $x$ to a set $S$ without revealing the actual members of the set. See for example this definition from [2]:

The most common form of one-way accumulator is defined by starting with a “seed” value $y_0$, which signifies the empty set, and then defining the accumulation value incrementally from $y_0$ for a set of elements $S = \{x_1,···,x_n\}$, so that $y_i = f(y_{i−1},x_i)$, where $f$ is a one-way function whose final value does not depend on the order of the $x_i$'s. [...] Because of the commutative nature of $f$ , a source can digitally sign the value of $y_n$ so as to enable a third party to produce a short proof for any element $x_i$ belonging to $S$ [...]. A well-known example of a one-way accumulator function $f$ is the exponential accumulator $exp(y,x) = y^x \mod N$, for suitably-chosen values of the seed $y_0$ and modulus $N$. In particular, choosing $N = pq$ for two strong primes $p$ and $q$ makes the accumulator function $exp$ as difficult to break as RSA cryptography [1].

Update: Let's see an example using the $exp$ function defined above. Suppose $a$, $b$, and $c$ are inputs, and that $y_0$ and $N$ are chosen properly. Then the accumulator algorithm $H_1$ will do the following:

1. Compute $s = a \cdot b \cdot c$ and $y = exp(y,s) = y_0^s = y_0^{abc}$
2. For each element $i$ in the input, compute $y_i = exp(y,1/i) = y^{1/i}$. For example, $y_a = y_0^{bc}$.
3. Output $z = (y,y_a,y_b,y_c)$.

Now, if you want to check if some element $x$ belongs to the original collection, you just have to check if for any of the partial results $y_i$, the equation $y = exp(y_i,x)$ holds. For example, if you try with $a$, then equation $y = exp(y_a,a)$ holds, since $exp(y_a,a) = (y_a)^a = (y_0^{bc})^a = y_0^{abc} = y$. On the contraty, if you try with $d$ different to $a$, $b$ and $c$, then none of the equations hold.

The problem with this solution is that output $z$ grows linearly with the size of the set of members.

References:

• For me it reminds Bloom filters. But have no idea how to provide security in this case.. Jan 15, 2015 at 20:01
• The problem with Bloom filters is that false positives are possible. Jan 15, 2015 at 21:44
• And that you cannot realistically reduce the false positive probability to something thats cryptographically acceptable. Jan 16, 2015 at 9:46

Alternatively, let $H$ be a hash function (in the ordinary sense) from the input space to $[0,2^N)$ for some $N$, and for $0 \leq x < 2^N$ let $f(x)$ be the smallest prime greater than $2^N + x$. (Here $N$ is determined by the security parameter. You can have 'probable prime' instead, where the precise definition of that will also depend on the security parameter.) Then let $H_1(a,b) = f(H(a)) \cdot f(H(b))$, and let $H_2(Z,a)$ be true iff. $f(H(a))$ divides $Z$.

Again, this suffers from the drawback that the image space grows linearly with the number of inputs.

• Very clever, except surely it'd be simple enough to brute-force for false positives - any value which hashes to a value between the smallest prime greater than and the biggest prime less than $2^N + x$. Jan 20, 2015 at 9:23
• Given two hashes $v_{ab} = H_1(a, b), v_{ac} = H_1(a, c)$, attacker can compute $f(H(a)) = gcd(v_{ab}, v_{ac}), f(H(b)) = v_{ab} / f(H(a)), f(H(c)) = v_{ac} / f(H(a))$ and make hashes of any pairs containing $a, b$ or $c$. Jan 20, 2015 at 11:59
• True. Good point! Jan 20, 2015 at 19:28

I can propose this (just invented it on paper): ($h$ is some hash function, like SHA1, $||$ is concatenation, $+$ is usual sum (xor is ok too)):

H1(a, b) = (h(a) + h(b)) || h(h(a)) || h(h(b))


For H2, either from $a$ or from $b$ we can derive the all $h(a), h(h(a)), h(b), h(h(b))$ and check the hash.

Also, if we assume that input pair is not ordered, to avoid trivial forgery by swapping $h(h(a))$ and $h(h(b))$ we may force order on them (e.g. force $h(a) \le h(b)$, so that $H1(a, b) = H1(b, a)$).

Intuition about security: from $h(h(a))$ one can't derive information about $h(a)$ (same for $b$). So attacker can't replace any of $h(a)$ or $h(b)$ in the sum with his hash.

UPDATE: I realized it has a simple flaw. Given $H1(a,b),H1(b,c),H1(a,c)$ we can easily get (from sums) $h(a),h(b),h(c)$ and use them to make hashes.

• Though $a$ can't be derived from $b$ and $H1(a, b)$, the attacker can derive $h(a)$ which allows him to forge $H1(a, x)$ for any $x$. This attack may be undesirable. Jan 15, 2015 at 19:58
• I also considered posting a similar answer to this, but it doesn't stand up to the original requirements. It's trivial for an attacker to modify the output such that one of a or b is validated successfully, but the other is not. Jan 15, 2015 at 20:06
• @StephenTouset how would you do it? if you change $h(h(a))$ then (from first part) $h(b)$ will be corrupted and $h(h(b))$ will not match. Jan 16, 2015 at 18:06
• Ah, actually, you're right. The attack is actually the one you described, where if you know one of a or b, you can forge a verifier for the other. But I don't think that's actually avoidable in the general case: anyone can create H1(x,y) for arbitrary x, y. If an attacker knows one of those values, regardless of algorithm, they can forge a verifier for the other. If you need it to be authenticated, replacing the hashes with an HMAC is probably necessary. Jan 16, 2015 at 21:21