Several people are playing a game with random events and require a way to produc

Question

Several people are playing a game with random events and require a way to produce a random number. (Such as dice rolls or a lottery.)

Can this be done such that each player has the power to be reasonably sure that the random number was fairly selected, without having to trust anyone else?

This question stems from a discussion in comments to my answer on the Bitcoin SE. I came up with a protocol but someone else spotted a flaw. This site seems more appropriate.
Please feel free to make use of my answer to that question.

Explanation / Answer

The answer you posted is actually correct (more or less, see below): have each participant commit to their random number ri by publishing, e.g., H(ri) in the first round. And then in the second round, each participant opens the commitment by publishing ri and everyone checks that it matches the committed value by hashing it. The final random number is the XOR of each ri.

The commenter there suggested an attack if there is a collision. However the definition of a secure hash function is that its collision-resistant. For a good modern hash function like SHA256, that is the case.

There are two subtleties.

The first is that your scheme only works for large random number, large enough that an attacker couldn't try every possible value for ri, hash it, and see if it matches. For committing to small values, you need a randomized commitment function. Good randomized commitments are based on discrete logarithms but you could construct one (with reasonable safeness) using a hash function by generating a large random value ai and then computing your commitment as H(ri||ai). To open, reveal both ri and ai. To change ri, you'd have to find a different ai so that the hash is the same: this is hard based on collision resistance. The bitlength of both ri and ai must be predetermined so it is clear from ri||ai where to split the value into ri and ai (otherwise you could open it to different values by simply splitting in a different spot).

The second subtlety is that the last participant to reveal his value will learn the accumulated random number before he reveals his number (he can see everyone else's number and he knows his own). This may cause him to abort if he doesn't like the result. You can do more complicated things to provide fairness, but generally if any participant refuses to open their commitment, the protocol should be restarted from the beginning with that participant excluded.

Also read this answer from @D.W. on a different question where (s)he explains the same protocol.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.