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.