From: "David F. Ogren" <ogren@cris.com>
Date: Thu, 30 May 1996 09:47:20 +0800
To: cypherpunks@toad.com
Subject: Re: [crypto] crypto-protocols for trading card games
Message-ID: <199605292058.QAA24885@darius.cris.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

> 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. 
> 
I've had similar ideas, but there are snags.  Card playing via 
encryption techniques is a great idea in theory, but in reality the
technical requirements often prevent implementation.

Think of the requirements of this system:

1. Cards must be transferrable.
2. Cards must not be duplicated by anyone other than the game 
company.
3. Cards must be able to be randomly shuffled.  (Since most trading
card games are two-player games our task is simplified greatly.)

Here is one possible algorithm, and some of its weaknesses.

The game company generates a master public key pair with which it will
sign all game cards.  Each player generates a public key pair to
verify his identity.

Each card is composed of the following fields:
A serial number, so that each card is unique.
A public key generated by that the owner as a proof of indentity.  
  (Each card owned by a player will have the same public key.)
The name of the card and (optionally) a desception of its effects.

Each card is then signed using the game company's secret key.

For each game both partners generate a public key pair.  Alice then
signs each card in her deck with the public key she generated for this
game and then transmits the cards (in a random order) to Bob. Bob does
the same thing for his deck. Each time Alice needs a card, Bob selects
one of Alice's encrypted cards and Alice decrypts it. 

As an additional measure to determine that Bob's cards are genuine,
Alice sends Bob a random string and asks that he sign it with the
secret key that matches the indentity-verifying public key on his
cards.  If Bob can return a signed version of that string, the
ownership of his cards is verified.  This indentity verifying routine
can be conducted as soon as Bob's first card is revealed. Bob of
course, conducts the same procedure for Alice after she plays her
first card.

After the game is over (or Alice's deck needs to be reshuffled), she
reveals her secret key and Bob verifies that her cards are genuine and
that she played fairly.

Advantages:

This system prevents anyone other than the game company from
duplicating cards (each card has a unique serial number), and from
copying other people's cards (each card has an indentifying public
key).

Any cheating can be discovered at the end of the game.  Bob knows the
order in which he selected Alice's encrypted cards.  After the game,
when Alice hands over her game-session secret key, he can check to
make sure that Alice revealed her cards in the order he selected them.

Only a reasonably amount of encryption/decryption is required.  Most
importantly only one key per player needs to be generated for each
shuffle.  During play only decryption is required.  In other words, a
modicum of set up is required, but once play begins the decryption
shouldn't slow the program down appreciably.

Disadvantages:

The entire integrity of the system relies on the security of the
game company's key pair.  If the secret key is comprimised, either by
a disloyal employee or by crytographic techniques, all cards in
existence must be recreated.

Cards are not transferrable.  In order to make cards transferrable the
game company must be able to invalidate cards which have been traded
to others.  In other words if Alice wants to give a cards to Bob she
must:

1. Contact the game company and tell them she wants to give the card
to Bob. 2. The game company must issue a new card to Bob with a new
serial number and with Bob's public key rather than Alice's. 3. The
game company must invalidate Alice's old card.  Since there is no way
that the game company can make sure all copies of the card have been
destroyed it must create a "invalid serial number list" and have the
players dial into that list everytime the game is played.

Since step 3 is so costly to implement, I think it is unlikely that a
cryptography-based trading card game will have tradable cards.




-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBMay5ZvBB6nnGJuMRAQHYFAQAl/PwCB0U/rQfjNgdoeLNpo9TyPAdebhT
FWjE44zjTmr6Cbl6S5D9QsqLub6eDI5DsXhD+w4Tipjn9/GZwQtFpEORx9MeAUWh
9TCtcDY4Tn5d8aNwtVikHt971uW6ROU7qWikIDipxotWtTscl8NESZbgmZqGOBWW
4VzGRMuIr1E=
=bXqs
-----END PGP SIGNATURE-----
--
David F. Ogren
ogren@concentric.net (alternate address: dfogren@msn.com)
PGP Key ID: 0xC626E311
PGP Key Fingerprint: 24 23 CD 15 BF 8D D1 DE  81 71 84 C8 2C E0 4B 01
(public key available via server or by sending a message to
ogren@concentric.net with a subject of GETPGPKEY)