3
$\begingroup$

Here is the protocol:

  • Bunch of players connected to server.
  • Server creates nonce and hashes it - send hash to clients as bit commitment.
  • Clients make nonces and send hashes to server as their bit commitment.
  • Unknown to clients one of the clients is the server itself. Server runs through candidate nonces from that client until IT wins game.
  • Server sends hashes of nonces to all clients. (Clients do not know each other's IP.)
  • Game is resolved and desired client wins.
  • Server sends all nonces to clients who verify them, none the wiser.

How do we prevent the server from cheating here, please?

$\endgroup$
  • $\begingroup$ cse.psu.edu/~ads22/pubs/PS-CSAIL/logmpc-EC-2003.ppt.pdf ​ ​ $\endgroup$ – user991 Feb 5 '16 at 1:15
  • $\begingroup$ As Ricky Demer pointed out, the general description of the problem points to the field of multiparty computation. However, the description requires more details. The most important: what do you mean by cheating ? Are the nonces the only variable involved in the game? $\endgroup$ – Sergio Andrés Figueroa Santos Feb 5 '16 at 13:08
2
$\begingroup$

One possibility is the sloth and unicorn approach of this paper.

The idea is essentially to use a slow (but quickly verifiable) hash. If the sever publishes a commitment to all the shares within a few seconds of the start of the hash computation (which will start at a agreed-to time), and the hash can't be done in less than an hour, then the server can't select its own share to tilt the game in its favor.

The downside, of course, is this is relatively expensive; we're willing to assume that the server will be willing to devote an hour of computation. For the point of the paper (trusted Elliptic Curve generation), that's reasonable (as you don't do that all often); for other uses, it might not be quite so realistic.

$\endgroup$
2
$\begingroup$

The specific attack you describe doesn't seem possible, because, at the point where the fake client would need to commit to a nonce, the server doesn't yet know the other clients' nonces, but only their hashes. Provided that the nonces have sufficient entropy to resist brute force attacks, it should not be possible force the server to learn them just from the hashes. This is precisely the point of a commitment scheme.

(Some methods of combining the nonces can be vulnerable to replay attacks, where the misbehaving client simply echoes another client's hash and nonce. But this attack is generic and can be carried out by any client that can see another client's messages before sending their own, and in any case can be prevented either by including a client ID in the hash input, or by aborting the protocol if any two hashes match.)

The critical part here, which is not fully explicit in your description of the protocol, is that no client should reveal its nonce before it has received hashes from all other clients (and from the server, if the server contributes input to the random number generation). This ensures that all participants must commit to their nonces before they learn any other client's nonce.

$\endgroup$
  • 1
    $\begingroup$ The chief way was someone can cheat here is if they're the last person to reveal their commitment. They can't change the value they're committed to; however they might be able to withdraw if they don't like the answer ("oops, my PC decided to update itself and reload, sorry, can we all try again from scratch???") $\endgroup$ – poncho Feb 5 '16 at 20:17

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.