5
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ I'd love to see if this can be done. $\endgroup$ – Stephen Touset Jan 15 '15 at 2:32
  • $\begingroup$ 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! $\endgroup$ – Nathan MacInnes Jan 15 '15 at 9:31
  • 1
    $\begingroup$ 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. $\endgroup$ – tylo Jan 15 '15 at 14:08
  • $\begingroup$ @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. $\endgroup$ – yyyyyyy Jan 15 '15 at 15:59
  • $\begingroup$ 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. $\endgroup$ – tylo Jan 16 '15 at 12:49
5
$\begingroup$

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:

[1] Benaloh, J., & De Mare, M. (1994, January). One-way accumulators: A decentralized alternative to digital signatures. In Advances in Cryptology—EUROCRYPT’93 (pp. 274-285)

[2] Goodrich, M. T., Tamassia, R., & Hasić, J. (2002). An Efficient Dynamic and Distributed Cryptographic Accumulator*. In Information Security (pp. 372-388).

$\endgroup$
3
  • $\begingroup$ For me it reminds Bloom filters. But have no idea how to provide security in this case.. $\endgroup$ – Fractalice Jan 15 '15 at 20:01
  • $\begingroup$ The problem with Bloom filters is that false positives are possible. $\endgroup$ – cygnusv Jan 15 '15 at 21:44
  • 1
    $\begingroup$ And that you cannot realistically reduce the false positive probability to something thats cryptographically acceptable. $\endgroup$ – DrLecter Jan 16 '15 at 9:46
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$ – Nathan MacInnes Jan 20 '15 at 9:23
  • $\begingroup$ 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$. $\endgroup$ – Fractalice Jan 20 '15 at 11:59
  • $\begingroup$ True. Good point! $\endgroup$ – Alec Edgington Jan 20 '15 at 19:28
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Fractalice Jan 15 '15 at 19:58
  • $\begingroup$ 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. $\endgroup$ – Stephen Touset Jan 15 '15 at 20:06
  • $\begingroup$ @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. $\endgroup$ – Fractalice Jan 16 '15 at 18:06
  • $\begingroup$ 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. $\endgroup$ – Stephen Touset Jan 16 '15 at 21:21

Your Answer

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

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