4
$\begingroup$

Imagine the following senario. We have $n$ participants. Participant $i$ has a set of elements $S_i$ with the elements being in a random order, possibly different for each participant.

The participants want some way to get something like a "hash" of the sets. Particularly they want for the hash to be collision resistant, so that it is hard to find two different sets with the same hash.

The hash function should also be pre-image attack resistant, so that given a hash (or a set) it is hard to find a (another) set that hashes to this values.

The catch is that the participants cannot reorder their sets. This means that the hash function must be order independant of the order of the elements but not of their contents.

Is there a secure and solid way to fulfil the requirements?

( I had a simple idea, to compute something like $SetHash(S) = Hash(e_1) \oplus Hash(e_2) \oplus \dots \oplus Hash(e_n)$ which i think satisfies the preimage attack resistance property but i cant formally prove that it is also collision resistant)

Improve this question
$\endgroup$
10
  • $\begingroup$ proving properties of hash combinations does not seem to be an easy task: crypto.stackexchange.com/q/24030/17650 My intuition would be to say that in the Random Oracle Model it gets easy but in this case I'm not even sure: with $n$ calls to the oracle you get $n$ hashes, you can then create something like $\sum_{i=1}^{i=n/2}\binom{i}{n}$ different couples of sets. That's a lot of possibilities for few oracle calls, but testing all them until finding a collusion will take some time and I don't see obvious optimizations. $\endgroup$
    – Cédric Van Rompay
    Commented Jun 2, 2016 at 17:02
  • $\begingroup$ Other comment: A set has no order. $\endgroup$
    – Cédric Van Rompay
    Commented Jun 2, 2016 at 17:03
  • $\begingroup$ @CédricVanRompay I haven't approved your edit. If you want to make substantial changes then you'd better ask the author - even if those changes make more cryptographic sense to you (and me). $\endgroup$
    – Maarten Bodewes ♦
    Commented Jun 2, 2016 at 17:06
  • $\begingroup$ @MaartenBodewes Oh, OK, sorry if I didn't use the "edit" function properly. Then here are my comments: (1) collision resistance in crypto means "it is hard to find two inputs that have the same hash". What you describe instead is only the basic property of a hash function, out of the crypto domain. (2) similar remark for preimage: preimage can just mean you found any input that hashes to the same value. $\endgroup$
    – Cédric Van Rompay
    Commented Jun 2, 2016 at 17:14
  • 2
    $\begingroup$ Yeah i completely misstated what pre-image attack means, sorry about that. A clarification on the order of the sets. What i meant is that each participant can access the element in a particular order, and that order is different for each one. They cant store the elements while they are reading them. A better way to express this would be that the elements are coming in like "messages" and the hash must be calculated using constant space. So they cant store the "messages", order them and then hash them. $\endgroup$
    – mandragore
    Commented Jun 2, 2016 at 17:27

1 Answer 1

Reset to default
2
$\begingroup$

The basic problem seems to be that of canonicalization. If you can't reorder the set, then you will have to choose a commutative, associative, operator to concatenate the values; $a \otimes b = b \otimes a$ and also $a \otimes (b \otimes c) = (a \otimes b) \otimes c$

An immediate candidate for this would be to interpret the elements, $m_i$ as integers and let $\otimes$ be integer multiplication. You could then pass it through a secure hash function $H(\prod m_i)$ to get your final hash.

To improve the collision resistance with this choice of $\otimes$ operation (unfortunately $H(5 \times 4) = H(10 \times 2)$; different sets with the same hash) you might consider associating each message with a unique prime number, and by the fundamental theorem of arithmetic, this product will be unique.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I was thinking something along those lines. maybe let the "hash" be $g^{\prod h(m_i)}$ However i still dont have a formal proof. (g is the generator of a secure group) $\endgroup$
    – mandragore
    Commented Jun 3, 2016 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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