I have thought up a method for generating random numbers between a client and a server which I hope is fair:

  • The client and server decide on a range in advance, $0$ trough $n-1$.

  • The server generates a $256$ bit random number $m$ (in the range $0$ to $\operatorname{floor}(\frac{2^{256} }{ n}) · n$) and hashes it with SHA-256 to give $m'$. $m'$ is then sent to the client.

  • The client generates a $256$ bit random number $o$ (as above) and sends it to the server.

  • The server can now calculate a fair random number $p = m + o \pmod n$.

  • The server sends $m$ and $p$ to the client.

  • The client can now check $\operatorname{SHA256}(m) = m'$ and $p = o + m \pmod n$.

Am I overlooking anything?

  • $\begingroup$ I think technically the server only needs to send $p$ to the client, since $m$ can be derived (although as stated, the protocol could easily be extended to three or more collaborating parties) $\endgroup$ Apr 25 '13 at 20:13
  • $\begingroup$ @StephenTouset, the original poster is correct that you need to send $m$ to the client. $p$ is a number in the range $0\ldots n-1$, so it only reveals the value of $m \bmod n$; it does not reveal the full value of $m$. Thus, you need to send the full $m$ as well. In practice, it is enough to send just $m$ (there is no need to send $p$ too, since the client can re-derive it), but that's probably not a big deal in practice. $\endgroup$
    – D.W.
    Apr 27 '13 at 19:41
  • $\begingroup$ When the client knows $n$, $o$, and $p$ I don't see how the client can't easily reconstruct $m$ when given $p\equiv m + o \pmod{n}$ and $m < n - 1$ $\endgroup$ Apr 28 '13 at 2:42

Yes, your scheme is fine.

Nitpick: I think you mean that your goal is to generate a random number in the range $0\ldots n-1$ (not $0\ldots n$). Also, to avoid bias, you need to generate $m$ as a random number in the range $0 \ldots (\lfloor 2^{256}/n \rfloor \cdot n)-1$ (not $0\ldots \lfloor 2^{256}/n \rfloor \cdot n$).

This problem is known as secure coin flipping, and it has been studied in great depth before. For solutions and analysis, look at the following questions on this site:

  • $\begingroup$ @DavidSchwartz Do you mean $m$? I'm not sure I follow. $\endgroup$ Apr 25 '13 at 20:18
  • $\begingroup$ @DavidSchwartz, I think the original poster took care of this by choosing $m$ uniformly at random from between 0 and one less than a multiple of $n$. $\endgroup$
    – D.W.
    Apr 25 '13 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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