Re: Will this scheme work ...

From: wcs@anchor.ho.att.com (Bill Stewart +1-908-949-0705)

Date: Tue, 12 Oct 1993 03:25:43 +0000

In article <MARKT.93Oct11221744@wundt.harlqn.co.uk> markt@harlqn.co.uk (Mark Tillotson) writes:
   > >>>The Problem:
   > >>>A group of people are playing a game over e-mail. They need to throw dice
   > >>>every turn. Unfortunately, they can't find somebody ``trustworthy'' to
   > >>>do it for them. So, how can they throw dice
   > How about this:  Each player generates a large random number, computes
   > the MD5 hash, and then discloses the hash to the other players.
   > Each player is now committed to his number, since no ther number will
   > produce the same hash.  Then each player reveals his number to the others,
   > the result is summed (and optionally hashed again, if you like) and the
   > result mod 6 is the die roll.

But this is relying on no-one guessing the random number algorithms
   used by the other players, and also requires that the random number
   algorithms be such that their sum is truly random---how can each
   player trust the other players' RNGs without knowing how they work,
   and if they know how they work they can predict them, and thus break
   the scheme...

I don't see how the above is any different from just disclosing the
   random numbers themselves without bothering to go through the MD5 hash

The MD5 stage means nobody can cheat by waiting until the other N-1 players
have revealed their random numbers and then picking one to get the
result they want; MD5 is non-invertible, so you can't do it.

As far as predicting the output of other players random numbers, either
1) You're trying to play fair, and make sure the outcome is really random,
	which you can help by using good randomness (like real dice!)
2) You're trying to play fair, and want to make sure the other players
	don't conspire to beat you, which you can help by using good
	randomness (like real dice!) or
3) You'd like to cheat, but can't get away with it because of MD5,
	so you at least want to reduce your chances of getting cheated on,
	which you can help by [reiterate....] or
4) You found a way to invert MD5, unique for inputs shorter than 128 bits,
	which you know your opponents are using,
	and while you're deciding whether to sell out to the Mafia or the NSA,
	you might as well not give it away by cheating at MUD-fighting,
	so you might as well use good randomness (like real dice!)
--
#				Pray for peace;      Bill
# Bill Stewart 1-908-949-0705 wcs@anchor.att.com AT&T Bell Labs 4M312 Holmdel NJ
# I'm moving to NCR in Pleasanton CA around Oct 15, so my mail delivery
# will be pretty unreliable for a few weeks after that.

References

Re: Will this scheme work ...
TSOS@uni-duesseldorf.de (Detlef Lannert)
Thu, 07 Oct 1993 10:01:49 +0000
Re: Will this scheme work ...
payson@dr-hibbert.cs.wisc.edu ( Payson)
Thu, 07 Oct 1993 16:51:59 +0000
Re: Will this scheme work ...
anspring@news.delphi.com (ANSPRING@DELPHI.COM)
Fri, 08 Oct 1993 01:41:50 +0000
Re: Will this scheme work ...
markt@harlqn.co.uk (Mark Tillotson)
Mon, 11 Oct 1993 22:17:43 +0000
Will this scheme work ...
moudgill@cs.cornell.edu ( Mayan Moudgill)
Sat, 25 Sep 1993 05:56:07 +0000