NetNews Usenet Archive 1993 #1/NN_1993_1.iso/spool/sci/crypt/6378

Internet Message Format | 1993-01-04 | 2.7 KB

Path: sparky!uunet!gatech!concert!rutgers!sgigate!sgi!wdl1!wdl39!mab
From: [e-mail] (Mark A Biggar)
Newsgroups: sci.crypt
Subject: Re: Telephonic Poker?
Message-ID: <[e-mail]>
Date: 4 Jan 93 22:34:58 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: Loral Western Development Labs
Lines: 45

In article <[e-mail]> [e-mail] (Jonathan Haas) writes:
>I was reading a paper that explained the RSA algorithm
>in layman's terms, and among other things it said, "An
>interesting side benefit of this algorithm is that it
>makes it possible for two people who do not trust each
>other to play poker by telephone." I've thought about
>it, and I can't for the life of me figure out HOW. The
>paper did not elaborate. Can someone explain to me the
>algorithm with which two mutually distrusting players can
>play poker by phone (or, more simply, have a fair coin
>toss)?

Method for fair coin toss over the phone (or a computer network):

1. both parties agree upon a Pseudo-random number algorithm and
    a method for computing a coin toss from the output of the PRNG.
2. party A selects a seed for the PRNG, excrypts it using ANY excryption
    function, and sends the encrypted seed to party B.
3. B then selects an interger N and sends it to A.
4. A iterates the PRNG N times and uses the result to determine the coin flip
    using the pre-agreeded upon method.
5. A now sends the result of the coin flip and the encryption key to B.
6. B can now decrypt the seed and verify that A did iterate the PRNG
    N times and correctly determined the result of the coin toss.

This can easily be extended to generating die rolls, card draws etc.
Also a sequence of random values can be fairly produced by having B
specify a monotonic increasing sequence of integers {N1, N2, N3, N4,...}.
A then uses the ith integer in the sequence to produce the ith random value
with B being able to verify the fairness of the sequence after the fact.
Note that B can generate the integer sequence incrementaly so that values
are only generated as needed, like for a game (Poker for example!)

Note: that RSA is not needed for this algorithm and any encryption algorithm
that is strong enough to be unbreakable during the time it takes to generate
the random values is good enough (even an encryption algorithm that both
parties know how to break is good enough, if the time to break it is larger
than the time needed to produce the random sequence.)

P.S. Does this question come up often enough to be in the FAQ?  If so, please
feel free to use the above write up for that purpose.

--
Mark Biggar
[e-mail]