3
$\begingroup$

(By items I mean hashable objects.) As an example (with obviously way too short hashes for readability), say I packed my bag and in it I put

  • a shovel (hashed to S)
  • a bucket (hashed to B)
  • a towel (hashed to T)
  • a random number (hashed to R)

Now friends of mine (who packed their bag too) and I agree on a game of multiple rounds, and each round consists of the following steps:

  • someone to be picked at random suggests something that might happen (e.g. going to the swimming pool, hitchhiking, Alien invasion) and what item(s) we might need then
  • everyone who doesn't have a mentioned item in their bag has to pay a small prize equally shared among those with the item in their bag; this is done for each mentioned item
  • additional items may be added to each ones bag

Would the game last only one round, we could simply open our bags and confirm the items' presence, but for multiple rounds the person to pick the next hypothetical event would of course choose something for which they'd probably gain the most due to knowing what everyone had in their bags (and maybe guessing the additions). Therefore, the round actually starts with

  • we'll tell each other something (a hash) and confirm that

and for confirmation, I propose to use a hash H with the following properties:

  1. H can take an arbitrary amount of inputs such as H(shovel) = S, H(shovel, bucket) = E
  2. H is commutative, i.e. H(A,B) = H(B, A)
  3. H is chainable, i.e. H(H(A,B),C) = H(H(A), H(B), C)

(if calling H a hash is still adequate).

With such a hash, we'd simply share the entire bag's hash, and for a given item I we'd have H(bag) = H(I, bag without I), i.e. by providing the remainder's hash there's proof of the item's presence in a bag without requiring to unpack it (that's also why the random number is added, otherwise everyone could figure out when one's bag is fully revealed).

So, long story short, does such a "hash" exist?


Of course, we could simply alphabetically sort our items and use a hash-chain, but for the question's sake let's assume sorting is beyond our capabilities ;)

$\endgroup$
  • $\begingroup$ I'm afraid a hash having such properties would not be cryptographically-secure, and therefore, your question wouldn't be very relevant to this site... $\endgroup$ – cygnusv Jul 2 '15 at 11:45
  • $\begingroup$ @cygnusv Because of "chainable"? I understand it would be insecure if H(H(A))=H(A), but what I (maybe unfortunately) called chainability merely allows splitting the hashes, and come to think of it is not even necessary $\endgroup$ – Tobias Kienzler Jul 2 '15 at 11:49
  • 1
    $\begingroup$ Actually, the commutative property would be problematic. I don't know about the "chainable" property, I have not thought about it, but in general, any kind of property of a hash function that permits to play with the input and outputs can potentially break the cryptographic security $\endgroup$ – cygnusv Jul 2 '15 at 11:55
  • 1
    $\begingroup$ Note that it is often possible to define some ordering of the elements in a set / bag. Even if there is no explicit ordering, it could be possible to create an implict ordering, e.g. using the hash value itself as number and order the hashes accordingly. $\endgroup$ – Maarten Bodewes Jul 2 '15 at 13:16
  • 2
    $\begingroup$ In addition to the excellent answer below based on Merkle hash trees, you can also take a look at crypto.stackexchange.com/q/11420/351 and crypto.stackexchange.com/q/6497/351 and crypto.stackexchange.com/a/489/351 (H(sort(H(x),H(y),..))) and crypto.stackexchange.com/q/17935/351. $\endgroup$ – D.W. Jul 3 '15 at 0:25
7
$\begingroup$

You could use a hash tree for this purpose. It wouldn't have the properties of your "hash", exactly, but it would work for the game.

Use a secret key to derive individual keys for the leaves, e.g. $k_i = H(k, i)$. Have each leaf be a keyed hash of an item in the bag, $h_i = H(k_i, v_i)$.

Then produce a normal hash tree by hashing two leaf values, then pairs of those values, etc. until you get the root, which you publish. You could add any number of dummy leaves (random values) and make the leaves exist at different depths to hide the number of items in the bag.

To show something was in your bag, you'd reveal the leaf key for that item, as well as all the internal sibling hashes up to the root. That would not reveal any other items, since their leaf keys would be secret.

$\endgroup$
  • 1
    $\begingroup$ You mean a Merkle tree? Yes, apart from 3 which on second thought seems irrelevant that does sound like a match, thanks - if one uses addition instead of concatenation $\endgroup$ – Tobias Kienzler Jul 2 '15 at 11:52
  • 1
    $\begingroup$ @TobiasKienzler, correct, a Merkle tree. However, I'm not sure what you mean by "addition instead of concatenation". $\endgroup$ – otus Jul 2 '15 at 13:02
  • $\begingroup$ I wasn't exactly sure what your k and i meant, and what your two-argument hash is, so I interpreted it from this Wikipedia image. But I think I didn't actually grasp your idea, maybe you could add a picture or example at some point - why are keys required? $\endgroup$ – Tobias Kienzler Jul 21 '15 at 11:19
  • 1
    $\begingroup$ @TobiasKienzler, I used two arguments to indicate a keyed hash. In practice with constant width keys you can just use $H(k||i)$. Addition is a no go, because it doesn't prove anything: you can claim your S contains any number X by "revealing" S-X. You need concatenation, just like shown in the Wiki page. $\endgroup$ – otus Jul 22 '15 at 11:53
  • 1
    $\begingroup$ @TobiasKienzler, you can call them keys or salts, but they must differ so not pepper. They must be kept secret at first so that you don't "leak" the contents of the bag (someone who knows them could test if an unrevealed object will be in the bag or not), but must be revealed together with the item in that leaf to allow verification. $\endgroup$ – otus Jul 23 '15 at 12:02
4
$\begingroup$

Another option would be to use a cryptographic accumulator (assuming you need a secure construction, otherwise the question does not fit here).

Basically, a one-way cryptographic accumulator permits to prove the membership of an element $x$ to a set $S$ without revealing the actual members of the set. In this case, the set $S$ represents the content of someone's bag.

In this answer to another question I propose this same solution to a different but related problem. I'm (almost) copying my answer for completeness.

Let's see an example. A well-known one-way accumulator function is the exponential accumulator $exp(y,x) = y^x \mod N$, taking a seed $y_0$ and modulus $N = pq$ for $p$ and $q$ prime, which makes the function as strong as RSA. Suppose $a$, $b$, and $c$ are inputs to the accumulator (i.e., $a,b,c \in S$). Then the accumulator algorithm does 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 contrary, 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.

$\endgroup$
  • $\begingroup$ Interesting method, though the growth means you'd have to add dummy items to not give away the amount of items packed $\endgroup$ – Tobias Kienzler Jul 4 '15 at 19:43

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.