<p>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 <a href="http://everything2.com/title/Coin%2520tossing%2520protocol" rel="noreferrer">coin tossing protocol</a>. Does anyone know of any solutions that can work for arbitrary values of N and M?</p>

Edit
Better algorithm (thanks wnoise):
Everyone picks a secret number from 0 to M-1
Everyone appends a load of random gunk to their number and hashes the result with a secure hash
Everyone tells everyone else this hash
Everyone tells everyone else their secret number, plus the random gunk they appended to it
Everyone verifies that the numbers and hashes+gunk match
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:
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.
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.
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
Use a trusted, unbroken hashing algorithm.
Use a cryptographically secure random number generator that has a big seed / state, and try to seed it from a good source of entropy.