Re: Will this scheme work ...

From: TSOS@uni-duesseldorf.de (Detlef Lannert)

Date: Thu, 07 Oct 1993 10:01:49 +0000

In article <1993Sep25.055607.4810@cs.cornell.edu> moudgill@cs.cornell.edu ( Mayan Moudgill) 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
>
>A Solution?:
>Set up a mail server that accepts a message of the form ``throw N dice,
>and send the results to all the players.''
>
>The server will reply with N random numbers between 1 & 6 inclusive to
>all players. It will also mark it with an ID number which includes
>the number of dice it has thrown previous to this request.

This is not the first nor the best reply to your question ;-) -- but I'd
like to suggest a *very* simple solution that doesn't require much overhead.
What it does require is an independent server that regularly broadcasts
some information which

(a) is sufficiently unpredictable
(b) does not reach any party *before* a certain date and time
(c) cannot be forged by any party (without an undue amount of resources)

Sounds complicated. But think, for instance, of a (quality) newspaper:
Take always a certain article (e.g. the first complete article on page 3
or the first three headlines on the first page), and it will be
unpredictable (bitwise), not known to anybody earlier than the evening
before the publication date, and you'll have a hard time making the editor
publish some garbage that you generated.

Perhaps some regular posting on usenet or elsewhere could serve the same
purpose.

Once you've identified a suitable source of information, you hash the first
n characters (ascii-encoded) through an algorithm like MD5. The result is
then used to generate the dice numbers (e.g. use a suitable number of bits
as the seed for a pseudo-random number generator).

If the players have to make (and mail) their decisions before the paper is
out, they cannot cheat as nobody will have advance information. Once the
paper is published, the contents and thereby the dice rolls can be verified
by each party. (The rare cases when articles are changed after printing
has started should be easy to resolve.)

Ok, there are safer and more elaborate schemes around, but they need, as
far as I know, a lot more communication and some advanced mathematical
programming. MD5 (and similar hash algorithms), however, are available in
source form on the net, and the rest of my proposal is very simple and
straightforward to implement. The most difficult part is probably to agree
on a source of information (and to type it in without actually buying the
paper!).

Although this solution is not perfect, it might be sufficient for the
intended purpose (if the stakes are not too high ...), and that's why I
hope it helps.

--
Detlef Lannert      DC3EK      E-Mail: tsos@rz.uni-duesseldorf.de
PGP 2.x key available (finger lannert@clio.rz.uni-duesseldorf.de)
Die Mathematiker sind eine Art Franzosen:  Redet man zu ihnen, so
uebersetzen sie es in ihre Sprache, und dann ist es alsobald ganz
etwas anderes.                         Johann Wolfgang von Goethe

References

Will this scheme work ...
moudgill@cs.cornell.edu ( Mayan Moudgill)
Sat, 25 Sep 1993 05:56:07 +0000

Referenced By

Will this scheme work ...
moudgill@cs.cornell.edu ( Mayan Moudgill)
Sat, 25 Sep 1993 05:56:07 +0000