# Is this scheme a provably fair random number generation?

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?

-
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) –  Stephen Touset Apr 25 '13 at 20:13
@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. –  D.W. Apr 27 '13 at 19:41
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$ –  Stephen Touset Apr 28 '13 at 2:42

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$).
@DavidSchwartz Do you mean $m$? I'm not sure I follow. –  Stephen Touset Apr 25 '13 at 20:18
@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$. –  D.W. Apr 25 '13 at 20:52