Distributed Random Number Generation

Question

I was wondering if there is a way for a network of N participants to agree that a number from 1 to M was chosen at random. (e.g. not influenced by any of the participants) This has been solved for values of n=2 and m=2 by the coin tossing protocol. Does anyone know of any solutions that can work for arbitrary values of N and M?

Answer 1

Edit

Better algorithm (thanks wnoise):

1. Everyone picks a secret number from 0 to M-1
2. Everyone appends a load of random gunk to their number and hashes the result with a secure hash
3. Everyone tells everyone else this hash
4. Everyone tells everyone else their secret number, plus the random gunk they appended to it
5. Everyone verifies that the numbers and hashes+gunk match
6. Add all the secret numbers together modulo M, then adds 1 to get the final result

As a participant, I should be satisfied with this because I know that I had full influence over the final result - the final number could have been anything at all, depending on my choice of secret number. So since no-one else could predict my number, they couldn't have predicted the final result either.

Any way to reduce the messages from the 3M^2 that i suspect a broadcast approach would require?

I reckon that only the hash publication has to be a broadcast, but it's still O(M^2). I guess the only way around that would be to pre-exchange digital signature keys, or to have a trusted communication hub.

Edit2 - How safe is the hashing thing?

Possible attacks include:

1. If I can generate a hash collision then I have two secret numbers with the same hash. So once I know everyone else's secret numbers I can choose which of my secret numbers to reveal, thus selecting one of two possible results.
2. If I generate my secret number and random gunk using a PRNG, then an attacker trying to brute-force my hash doesn't have to try every possible number+gunk, only every possible seed for the PRNG.
3. I use the number+gunk that everyone reveals to determine information about their PRNGs - I could try to guess or brute-force the seeds, or calculate the internal state from the output. This helps me predict what numbers they will generate next time around, which narrows the search space for a brute-force attack.

Therefore, you should

1. Use a trusted, unbroken hashing algorithm.
2. Use a cryptographically secure random number generator that has a big seed / state, and try to seed it from a good source of entropy.