Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers 4

up vote 13 down vote accepted

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

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 $r_i$, 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 $a_i$ and then computing your commitment as $\mathcal{H}(r_i||a_i)$. To open, reveal both $r_i$ and $a_i$. To change $r_i$, you'd have to find a different $a_i$ so that the hash is the same: this is hard based on collision resistance. The bitlength of both $r_i$ and $a_i$ must be predetermined so it is clear from $r_i||a_i$ where to split the value into $r_i$ and $a_i$ (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.

share|improve this answer
3  
Actually, there's a subtlety here. Using the XOR of the $r_i$s is not secure. An attack: Suppose there are two participants, Alice and Bob. Alice is honest, picks $r_1$ randomly, and publishes $h_1 = H(r_1)$. Bob is malicious and rather than picking his own random number and hashing it, just copies Alice's hash: i.e., Bob publishes $h_1$. In the second round, Alice reveals $r_1$. Bob reveals the same thing. Now the final random number will be all-zeros. This allows a malicious Bob to force the final "random" number to be all-zeros, so it isn't random after all. –  D.W. Sep 26 '11 at 4:20
2  
P.S. The fix is, instead of XORing the $r_i$s, you can hash them. e.g., the final random number is $H(r_1 || r_2 || ...)$, not $r_1 \oplus r_2 \oplus ...$. –  D.W. Sep 26 '11 at 4:21
1  
Good point! The attack is worst if you use a non-malleable commitment scheme (I had suggested Pedersen commitments; edited out now) because then you can disguise the fact that you copied another commitment (or formed a related one). –  PulpSpy Sep 26 '11 at 14:07
3  
Another fix is to require the number of random bits be higher than (say) 256, and disallow repeated digests. Or better, to force the 2nd publisher of a repeated digest to reveal first (better because it allows you conclusively identify cheaters). –  Fixee Sep 27 '11 at 1:18
    
One minor correction of the middle paragraph for $\mathcal{H}(r_i||a_1)$: You only need to have one of the parts with a fixed size in order to have a unique interpretation of the binary number. In general, you want just any perfectly binding commitment scheme (or computationally binding scheme without a trapdoor, e.g. a hash function) –  tylo Mar 21 at 8:26
add comment

The problem pointed out by JGWeissman on Bitcoin.SE is only an issue if the hash function lacks collision resistance. Admittedly, collision resistance is one of the strongest properties usually demanded of hash functions, and collision attacks have been found for some hash functions commonly used in the past, such as MD5, but still, any secure cryptographic hash function should be collision resistant.

In fact, a simpler scheme should work:

  1. Each player $i$ chooses a random number $x_i \in \{0,\dotsc,n-1\}$ and a random $k$-bit string $s_i$, for some reasonably large $k$ (say, $k=128$).
  2. Each player announces $h_i = H(i \,||\, s_i \,||\, x_i)$, where $H$ is a collision-resistant hash function and $||$ denotes concatenation.
  3. After all players have announced their $h_i$, they now reveal their $s_i$ and $x_i$. Each player checks that the $h_j$ value announced by every other player $j$ in step 2 matches that player's $s_j$ and $x_j$.
  4. The final random number $x$ is calculated as the sum of all the $x_i$ values modulo $n$.

The value $h_i$ announced in step 2 is called a commitment. By publishing $h_i$, player $i$ commits to a specific $x_i$ without actually revealing $x_i$ itself. In this way, each player $i$ can be sure that the other players chose their random numbers without knowing $x_i$.

The purpose of the salt $s_i$ is simply to prevent brute force cracking of $h_i$ by trying each possible value of $x_i$ in turn. The player identifier $i$ is included in the hash to prevent a cheating player from copying another player's commitment. I assume that the identifiers are unique and known to all players in advance, or at least before step 3. (Another way to prevent such replay attacks would be to abort the protocol in step 3 if any two commitments are identical, which, due to the inclusion of the salt, should virtually never occur by chance.)

Actually, if the length of $h_i$ is substantially greater than $k\;\log_2(n^2 - n)$, this protocol may be secure even if $H$ is not collision-resistant, simply because there may be no exploitable collisions to be found. In particular, assuming that the outputs of $H$ are uniformly distributed over the set of $m$-bit strings, with $2^m \gg 2^k$ (and $2^m \gg n^2$), the probability of there being at least one exploitable collision is approximately

$$1-\left(1-\frac{1}{2^m}\right)^{2^k\tfrac{n^2-n}{2}} \approx 1-\exp \left(-2^{k-m}\frac{n^2-n}{2}\right) \approx 2^{k-m}\frac{n^2-n}{2}.$$

However, keep in mind that you also don't want to make $k$ too small, since then the salt becomes ineffective. Increasing $m$ should always be safe, though.

share|improve this answer
    
Actually, there's a subtlety here. Using the sum of the $r_i$s is not secure. Using a variant of the attack I described on @PulpSpy's protocol, a malicious participant Bob can force the sum to be even, which means that the final "random" number is not actually random. The fix is the same as I described in my comment on Pulpspy's answer: you should hash all of the $x_i$ values (rather than summing them). –  D.W. Sep 26 '11 at 4:23
1  
@D.W.: Very good point. I should note, though, that there are at least two other ways to fix the protocol: either abort/restart the protocol if $h_i = h_j$ for any $i \ne j$ (which should be astronomically unlikely if nobody cheats), or include some kind of player identifier in the input to $H$ (so that anyone replaying another player's commitment will be caught in step 3). I'll edit the answer to implement the latter option, since it's good practice anyway. –  Ilmari Karonen Sep 26 '11 at 17:39
add comment

Say $m$ persons meet physically and want to draw a positive integer $x$ less than $n$.

Each person $j$ secretly selects a positive integer $x_j$ less than $n$, writes it down on a piece of paper, and fold it to hide her choice. The $m$ folded pieces of paper are brought together then publicly unfolded, revealing the $x_j$. The outcome of the protocol is $x = (\sum x_j)\mod n$. To illustrate with $n=10$, the $m$ digits $x_j$ are added and the rightmost digit of the sum is $x$.

If any of the person participating has chosen her $x_j$ at random, then $x$ is random. Hence, no participant can complain that $x$ is not random.

It is possible to replace the pieces of papers with electronic exchanges of messages: in addition of $x_j$, each person draws a random $r_j$, and sends $H_j = Hash(x_j \| r_j)$ to all the others, which constitutes her commitment on the choice of $x_j$. When everyone has all the commitments, everyone reveals her $x_j$ and $r_j$. The outcome is computed as above, and the $H_j$ can be verified by anyone from $x_j$ and $r_j$. If the exchange of messages is reliable, no one can complain.

share|improve this answer
1  
The protocol with pieces of paper is secure, but the protocol with electronic exchanges of messages is not. There's a subtle attack here, which I've described in my comments on PulpSpy and Ilmari's answers: the attacker can copy someone else's commitments and thereby influence/bias the final random number. If you want to use electronic messages, you need to hash everyone's $x_j$ values, rather than summing them. –  D.W. Sep 26 '11 at 4:25
    
@D.W.: You are of course right! As pointed out in other answers, this can be fixed by defining $H_j=Hash(x_j∥r_j∥j)$. –  fgrieu Sep 27 '11 at 6:15
add comment

Two variations.

If one of the "players" is going to generate the number for others to guess (lottery) then you could do it this way:

  1. Collect a token from each participant (a nonce, a random number, a favorite color, etc.)
  2. Generate or select the secret number.
  3. Hash the generated number with the tokens.
  4. Publish the hash and the tokens.
  5. Allow each other player to guess. After the guesses are complete and published you publish the secret number.
  6. Everyone can verify it is the actual number by repeating the hash.

If you have multiple "players" who are each equal in the guessing then do it this way:

  1. Collect a token from each players (a nonce, a random number, a favorite color, etc.)
  2. Publish the tokens to all players.
  3. Hash the tokens.
  4. Use the hash to see a PRNG or RNG to generate the random numbers.
  5. Everyone can repeat the process to generate the same random numbers. Of course as soon as you publish the tokens then all future random numbers are known.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.