[crypto] crypto-protocols for trading card games

Here's an interesting problem:

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 
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)

Simon

On Wed, 29 May 1996, Simon Spero wrote:

> 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)

I'd been thinking about it from the opposite point of view: make up a card
game (possibly electronic, like what you're proposing) that acts as intro
to crypto for the untamed hordes of game players. 

As you noticed, Simon, cardgames are a good analogue for cryptography.
They operate on the principle of secrecy/discovery (turning over the
cards), there are analogues for all sorts of algorithms (rules of the
game), we have randomness (shuffling), concepts of authentication (to beat
cheaters, no cards up the sleaves, no color-laser-photocopied Magic
cards...), tokens and smartcards (the cards themselves), integer numbers,
and a whole host of special characters a la Alice, Bob, Trent, etc.
(Kings, Queens, Jacks, Jokers). In short, all the building blocks for
working crypto protocols and their interfaces, needing no introduction for
most people. I can sort of even see a representation of a public card scheme
with signatures and certs (I'll have to go grab a deck and try).

Presumably, given a careful choice rules one could do for crypto what
Solitaire did for Windows 3.1 . I see no reason why a card game could not
be an interface for pgp or remailers, or an easier demonstration for
DC-nets, blinding or complicated market protocols. One might even build a
programming language out of such building blocks (probably for scripting).
Poker for Java--Do not Export! (If the CJR for the RSA-Perl T-shirt was
absurd wait till the authorities get stuck with this one.) (Mind you, I 
probably wouldn't use an imperative language like Java for the scripting, 
but that's just me.)

This is of course all idle speculation, 'cause I'm lazy and have neither 
the time nor the expertise. It's all yours folks.

What _did_   Solitaire do for Windows 3.1?   Distract the attention of 
the unwashed masses away from the actual merits of the beast?

Alan Horowitz <alanh@infi.net> writes:

> What _did_   Solitaire do for Windows 3.1?   Distract the attention of
> the unwashed masses away from the actual merits of the beast?

It's interesting to note that
a) All previous versions of MS Windows starting I think with the beta .9
which I first saw included Reversi (Othello), a much more intellectual game.
b) IBM OS/2 comes with a pile of games, including a much nicer solitaire,
chess, a game where you have to catch a cat with your mouse, etc.
Ostensibly, they're there to train users to use the mouse interface.
E.g., Solitaire teaches users to drag and drop.

---

Dr. Dimitri Vulis
Brighton Beach Boardwalk BBS, Forest Hills, N.Y.: +1-718-261-2013, 14.4Kbps

On Wed, 29 May 1996, Alan Horowitz wrote:

> What _did_   Solitaire do for Windows 3.1?   Distract the attention of 
> the unwashed masses away from the actual merits of the beast?

	What "merits"?

Petro, Christopher C.
petro@suba.com <prefered for any non-list stuff>
snow@crash.suba.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      ------