home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / crypt / 6357 < prev    next >
Encoding:
Text File  |  1993-01-04  |  2.2 KB  |  44 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!usc!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!mcdchg!chinet!schneier
  3. From: schneier@chinet.chi.il.us (Bruce Schneier)
  4. Subject: Re: Telephonic Poker?
  5. Message-ID: <C0C73F.1v9@chinet.chi.il.us>
  6. Organization: Chinet - Public Access UNIX
  7. References: <1993Jan3.185628.2976@zip.eecs.umich.edu>
  8. Date: Mon, 4 Jan 1993 15:59:39 GMT
  9. Lines: 33
  10.  
  11. In article <1993Jan3.185628.2976@zip.eecs.umich.edu> positron@quip.eecs.umich.edu (Jonathan Haas) writes:
  12. >I was reading a paper that explained the RSA algorithm
  13. >in layman's terms, and among other things it said, "An
  14. >interesting side benefit of this algorithm is that it
  15. >makes it possible for two people who do not trust each
  16. >other to play poker by telephone." I've thought about
  17. >it, and I can't for the life of me figure out HOW. The
  18. >paper did not elaborate. Can someone explain to me the
  19. >algorithm with which two mutually distrusting players can
  20. >play poker by phone (or, more simply, have a fair coin
  21. >toss)?
  22.  
  23. It's actually fairly simple.  I take 52 messages, each equalling a card
  24. of the deck, and encrypt them each with my public key and then send them
  25. all to you.  You can't decrypt any of the cards, so you choose five at
  26. random, encrypt them with your public key, and send them to me.  I can't
  27. read any of them; I decrypt them with my private key and send them back
  28. to you.  You then decrypt them with your private key, and that's your hand.
  29. Additionally, you choose five more cards at random and send them back to me.
  30. I decrypt them with my private key, and that's my hand.
  31.  
  32. This protocol assumes that the encryption/operation is communitive, which
  33. RSA is.  Given that property, even a secret-key algorithm will do.
  34.  
  35. There are also a bunch of other things you have to worry about.  A new
  36. public key/private key pair must be generated by each player for each hand.
  37. Each of the 52 messages should include a different random string, to avoid
  38. various attacks against the protocol.  And finally, it is possible to "mark"
  39. a card to the tune of one bit of information, using quadratic residues.
  40. While there are two-player poker protocols that prohibit that one-bit marking,
  41. I know of no three-or-more-player protocols that do so.
  42.  
  43. Bruce
  44.