🚀 go-pugleaf

In article <1993Jan3.185628.2976@zip.eecs.umich.edu> positron@quip.eecs.umich.edu (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)?

It's actually fairly simple.  I take 52 messages, each equalling a card
of the deck, and encrypt them each with my public key and then send them
all to you.  You can't decrypt any of the cards, so you choose five at
random, encrypt them with your public key, and send them to me.  I can't
read any of them; I decrypt them with my private key and send them back
to you.  You then decrypt them with your private key, and that's your hand.
Additionally, you choose five more cards at random and send them back to me.
I decrypt them with my private key, and that's my hand.

This protocol assumes that the encryption/operation is communitive, which
RSA is.  Given that property, even a secret-key algorithm will do.

There are also a bunch of other things you have to worry about.  A new
public key/private key pair must be generated by each player for each hand.
Each of the 52 messages should include a different random string, to avoid
various attacks against the protocol.  And finally, it is possible to "mark"
a card to the tune of one bit of information, using quadratic residues.
While there are two-player poker protocols that prohibit that one-bit marking,
I know of no three-or-more-player protocols that do so.

Bruce