3
$\begingroup$

I really don't know how to call this simple problem: Two (or more) parties need to establish a common (non-secret) value to be used as a seed for a deterministic RNG. The only requirement is that each party can be sure that the seed is really random.

My idea is as follows:

  1. Each party generates a random value $x_i$,
  2. sends its hash $h(x_i)$ to everyone else,
  3. and waits for hashes from all other parties.
  4. Then each party sends its original value $x_i$ to everyone else,
  5. waits for all the values,
  6. and verifies them.
  7. Finally, each party computes the seed as $\mathop\oplus\limits_i x_i$

I know that inventing protocols should be left to experts, however, I'm curious if this could work and what's needed for the this. I see that the generated values must be long enough to avoid brute-forcing and that $h$ must be collision-resistant.

|improve this question|||||
$\endgroup$
6
$\begingroup$

This is pretty much the schoolbook implementation of a shared random number generation (generate, commit, publish). So yeah, it's secure. But this only works for large random numbers, here's a small adaption that allows for arbitrary size integers:

If you need an $n$-bit random number everyone should generate $n$-bit random numbers - this is independent of the security level of the exchange itself. Then everyone also generates a second random number $m$, which is large (say, 256-bit) to prevent bruteforcing, and publish $H(n || m)$. Then after everyone has commited everyone publishes their $m$ and $n$, but only use $n$ for the XOR-sum.

I'd suggest you to use a 256-bit hash for the commitments.

Beware of all kinds of nastyness with MITM and replay attacks, make sure you do all of this over authenticated channels.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Since collision resistance is required, the security level of 64 bits provided by a 128 bit hash is insufficient. $\endgroup$ – CodesInChaos Nov 10 '13 at 17:40
  • $\begingroup$ @CodesInChaos I think collision resistance is more of an observation on $h$ rather than a protocol requirement, but I might be wrong. $\endgroup$ – rath Nov 10 '13 at 19:17
  • $\begingroup$ What if instead of generating and hashing $m$ the parties publish their signature on $n$? $\endgroup$ – rath Nov 10 '13 at 19:36
  • 3
    $\begingroup$ @rath Without collision resistance a cheater can pick which of them to reveal and the commitment becomes non binding. So collision resistance if an essential part of the protocol. $\endgroup$ – CodesInChaos Nov 10 '13 at 20:44
  • $\begingroup$ @nightcracker: I was thinking about generating large random numbers, as cutting them is trivial and they may be useful when the requirements change. And I was thinking about seeding Salsa20 where 256 bits fit perfectly (as the key). $\endgroup$ – maaartinus Nov 11 '13 at 11:07

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.