# How can two (or more) parties share and agree upon a common random seed?

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.

-

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.

-
Since collision resistance is required, the security level of 64 bits provided by a 128 bit hash is insufficient. –  CodesInChaos Nov 10 '13 at 17:40
@CodesInChaos I think collision resistance is more of an observation on $h$ rather than a protocol requirement, but I might be wrong. –  rath Nov 10 '13 at 19:17
What if instead of generating and hashing $m$ the parties publish their signature on $n$? –  rath Nov 10 '13 at 19:36
@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. –  CodesInChaos Nov 10 '13 at 20:44
@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). –  maaartinus Nov 11 '13 at 11:07