Re: [crypto] crypto-protocols for trading card games

[Mike Fletcher <fletch@ain.bls.com>]

> In the not too distant past there was a fad for collectible trading card 
> games, the most famous of which was Magic, The Gathering (tm). These 

	Oy, don't mention that name.  I spent waaay too much money
on cards (Ah, my foolish youth.  Anyone want to buy a slightly used
Chaos Orb? :).

> games combined the collecting and trading of baseball cards with traditional
> aspects of card playing. Cards were issued by a central 
> authority/publisher (Wizards of the Coast in the case of MtG). Each 
> player uses his or her own deck; cards that are not played remain secret; 
> however the same deck mut be used in each round of a match. tournament 
> games are adjudicated by an umpire.
> 
> Design a set of crypto protocols to support the issuing, trading, and 
> playing of such card games in real time (100ms compute time per move)

	Well, here goes nothing for the playing part:

	Each player should submit a signed copy of their deck (i.e. a
listing of all the cards therin) to the umpire (if you don't want the
even umpire seeing the deck contents until afterwards, make them
submit a bit-committed symetric key and encrypt the deck manifest with
it).  Each individual card in the deck should have a unique identifier
which should be noted on the manifest.  Identifiers wouldn't need to
be sequential (in fact they might leak info to the opponent if they
were), but duplicates of the same card should each have its own id.
Depending on how you want to run things, you could allow (and probably
should require) players to submit new a ID->card list before each
round begins.

	So my deck might look like:

ID	Card
--------------------
309487	Prodigal Sorcerer
008461	Land (Plains)
663542	Land (Forrest)
....

	Before each round, opponents would exchange lists of card IDs.
Whenever a player needs to "draw", the other player takes an ID at
random off the list of IDs (and marks is as "used").  At the end of
each round the players submit a transcript of the game to the umpire
who then checks that all the cards played were in the decks, that no
duplicates of the same id/card were used, or changes of cards (i.e. ID
440315 was supposed to be a "Zombie" but the owning player said it was
a "Yawgmoth's Daemon").

	If you want to do away with the umpire (for casual play
between two people), have opponents swap the encrypted deck manifest
and bit commit to key used.  Afterwards they can double check for
cheating themselves.  Something you might want to allow is letting a
player include extra IDs which map to "no card, pick again".  This
would allow players to disguise the exact size of their deck (although
this would only allow for puffing up a deck, not making it appear
smaller).

	As for issuing and trading cards, maybe store cards as signed
certificates (something along the lines of "card name & serial number"
signed by the owner, then by the issuer).  This would make trading a
bit of a problem as you couldn't give the card away without the issuer
(Online clearing for Magic cards? :).  And there's the problem of how
do you tell who actually owns the card (if the issuer keeps a list of
serial number->owners that might work, but again that needs online
clearing).  I missed all the discussion on digital bearer bonds a
while back, but something like that might could be applied here.

	Don't know if that's what you were looking fore, but it's all
I can think of at this late hour and I'm sure someone will shoot holes
all through it anyhow. :) What do you think, sirs?

---
Fletch                                                     __`'/|
fletch@ain.bls.com  "Lisa, in this house we obey the       \ o.O'    ______
404 713-0414(w)      Laws of Thermodynamics!" H. Simpson   =(___)= -| Ack. |
404 315-7264(h) PGP Print: 8D8736A8FC59B2E6 8E675B341E378E43  U      ------