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?
+4
A:
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.
Menkboy
2008-10-22 00:32:33
Caveat: pick a secure hashing algorithm! I think md5, for example, has been broken, but it might not be broken for such small amounts of data.
Claudiu
2008-10-22 00:34:12
also, will this xored number be as random as the individual ones? instinct tells me yes, probably, but i'm not entirely sure if it will exhibit some unrandomness.
Claudiu
2008-10-22 00:34:59
See http://en.wikipedia.org/wiki/Commitment_scheme
CesarB
2008-10-22 00:43:54
@CesarB: Ah cool, I knew there had to be a better description + name for it
Menkboy
2008-10-22 00:54:15
The commitment scheme pointed out by CesarB, is the basis of the coin-tossing protocol. On that foundation, a good way to combine the random numbers must be found. The problem here is how to guarantee that no participant can influence the result in either direction. Does XOR offer this guarantee?
Alexandros Marinos
2008-10-22 00:57:23
You don't want XOR, but addition mod M. When M is 2, this is just XOR.
wnoise
2008-10-22 01:18:09
@wnoise: (facepalm) Yep, that's lots cleaner than the current idea.
Menkboy
2008-10-22 01:23:37
so we're talking about bit-commiting to a number between 1 and M and then add-MOD M-ing the numbers. Any way to reduce the messages from the 3M^2 that i suspect a broadcast approach would require?
Alexandros Marinos
2008-10-22 01:36:01
If participants had PKI, then messages could be signed, and it would then be possible for the broadcast to be relayed via untrusted participants rather than each pair communicating individually. In practice you'd probably use PKI anyway to prevent MITM attacks on a pair by another participant.
Steve Jessop
2008-10-22 01:45:25
Note that although this reduces the number of messages, total bandwidth (ignoring overhead) is the same. Everyone still needs to receive all the data involved.
Steve Jessop
2008-10-22 01:51:45
Although the question was more on the pre-existence of an algorithm or protocol that acheived this, the work here is excellent so I have to accept it. However, how safe is the hashing+gunk vs. the bit commit protocol?
Alexandros Marinos
2008-10-22 10:46:58
Also, in terms of reducing the amoun of messages, how about the following: participants form a cycle, one of them passes their number to the next one, the next adds their own and passes the stack on and so on until all participants have all the numbers, I suspect 2M-1 messages. is there a flaw?
Alexandros Marinos
2008-10-22 10:49:31
A:
This is probably not what you're looking but just to start this thread how about this -
Select a leader, let the leader choose the number, distribute the number to everyone.
shoosh
2008-10-22 00:34:35
this is effectively a re-centralization of the algorithm. the problem is to get the number without supposing any trust between the participants.
Alexandros Marinos
2008-10-22 00:50:49
+1
A:
I don't know if it is possible for people to agree on the randomness of a single number; it should be in the statistics. If the statistics of many random numbers matched the statistics of numbers taken from here then I would consider your number random, but I don't know about the next guy N+1 on the network.
Alex
2008-10-22 00:50:05
Agreed, one number is never "random." Perhaps the question asker could clarify that he means that the participants agree that everyone selected his OWN number?
Jason Cohen
2008-10-22 00:59:16