Secure distributed deck of cards (2003-Jul-22-Tue)
Adam M. Costello
http://www.nicemice.net/amc/

Goals:

Several players should be able to use a virtual deck of cards in the
same ways they would use a physical deck of cards: shuffle the deck,
deal cards, draw cards (from the pack or from other players' hands or
from various piles), reveal cards (to everyone or to selected players),
pass cards to other players, play cards, discard cards (face-up or
face-down), reshuffle subsets of cards (for example, reshuffle one's own
hand after receiving a passed card so that it cannot be tracked by the
player who passed it, or reshuffle the discard pile so that it can be
recycled as the draw pile), and leave cards unrevealed at the end of the
game.

At all times each player should be independently confident that no cards
have been added, removed, altered, or moved surreptitiously (between
the hands and/or the various piles), even if all the other players are
colluding.

There should be no need for additional participants besides the players
themselves.

Assumptions:

We assume that there exists a secure broadcast communication channel, so
that whenever one player says something (like "I play such-and-such a
card"), every player can be confident of what was said and who said it
and that all players heard the same thing and that the statement cannot
be disavowed.

We assume that there exists a fully opaque commutative cipher; that is,
functions E() and D() such that for all key, msg

    D(key,E(key,msg)) = msg

    E(key,E(key2,msg)) = E(key2,E(key,msg))

    It is infeasible to deduce anything about key or msg given
    E(key,msg) and access to a black box that performs E(key,*).

Protocol overview:

A card is always encrypted by N keys, where N is the number of players.
For conceptual convenience, we imagine that there is a degenerate key
for which E(key,*) is the identity function, so that in the beginning we
can start with plaintext cards and imagine that they are encrypted with
degenerate keys.

A card always belongs to exactly one group.  A group could be a
singleton (a group of one card), or could contain multiple cards (for
example, a player's hand, the undealt pack, the entire deck, etc).  All
cards in a group are revealed and/or moved as a unit ("moved" means
dealt, played, drawn, discarded, etc).  A group is moved simplying by
saying so (for example, "I play group g").  Each player keeps track of
the size and location of each group, and therefore knows whether the
movement is legal in the game.  A group is revealed to a particular
player using a procedure that depends on the cooperation of all players
(see "Protocol procedures" below).  Obviously a player will participate
in that procedure only if they agree that the revelation is supposed to
happen.

There is a procedure for splitting a group into singletons, so that an
individual card can be revealed and/or moved.

There is a procedure for shuffling a group.  Since only a group can
be shuffled, there is a procedure for merging several groups into one
group.

A group consists of a group tag and a set of encrypted messages, one for
each card in the group.  Each group has a distinct tag, which is used to
refer to the group whenever it is revealed or moved.  The messages are
the encryptions of the faces of the cards using N keys, one chosen by
each player.  The key chosen by player i for group g is denoted key_g_i.

Initially all the cards belong to a single group, and all the keys are
the degenerate key.  The messages are distinct plaintext card faces.

Protocol procedures:

To reveal a group g to a particular player p, some other player i
decrypts each message of the group using key_g_i and announces the
result.  Then another player does the same (decrypting the previous
result), and so on, in any order, until only player p has not decrypted.
Finally player p decrypts each message with key_g_p (keeping the result
secret if the other players are not meant to see the faces of the
cards) and verifies that the results are valid card faces containing no
duplicates.  If the verification fails then someone is not following
the protocol.  If a group is to be revealed to multiple players, this
procedure needs to be done for each of them, so that they each get a
chance to be last, so that they are each confident of the faces of the
cards.

To shuffle a group g, the players change their keys as follows.  Some
player i secretly decrypts each message of the group using key_g_i,
generates a new key_g_i, encrypts each message with it, shuffles the
messages, and announces the result.  Then another player does the same
(re-keying the previous result), and so on, in any order, until all the
players have changed their keys.  The final result is the new set of
messages for group g.  The old messages and old keys can be forgotten.

To merge several groups (g1, g2, g3, ...) into one group, the players
change their keys as follows.  The players agree on an arbitrary unused
group tag g.  Some player i secretly decrypts each message using the
appropriate key (key_g1_i, key_g2_i, etc), generates a new key_g_i,
encrypts each message with it, and announces the result (unshuffled,
so that the other players will still know which messages came from g1,
g2, etc).  Then another player does the same (re-keying the previous
result), and so on, in any order, until all the players have changed
their keys.  The final result is the new set of messages for group g.
The old messages and old keys can be forgotten.

To split a group g into singletons, the players agree on a list of
arbitrary unused group tags (g1, g2, g3, ...) to associate with the new
singleton groups and agree on an arbitrary order for the messages of
the group.  Some player i secretly decrypts each message using key_g_i,
generates new keys key_g1_i, key_g2_i, etc, encrypts each message with
the corresponding key (key_g1_i for the first message, key_g2_i for the
second, and so on), and announces the result (unshuffled, so that the
other players will know which message is destined for g1, which for
g2, etc).  Then another player does the same (re-keying the previous
result), and so on, in any order, until all the players have changed
their keys.  The final result is the new set of messages for group g.
The old messages and old keys can be forgotten.  But there is more to be
done...

As was alluded to in the group-reveal procedure, the cards in a group
can be trashed or replaced by duplicates of other cards in the same
group (but not by cards outside the group).  This does not enable any
deception, because the group is moved as a unit and revealed as a
unit.  But after the group-split precedure, these garbage or duplicate
cards will be in separate groups, where they could indeed be used for
deception.  Therefore, after a group-split is performed, the entire
deck is verified as follows.  Copies are made of all the groups, and
the copies are then merged into a single group, which is then shuffled
and revealed to all players, who verify that it contains exactly one
instance of each card face.  All the copies and keys created during the
verification can then be forgotten.

Proof of correctness:

I am completely lacking in sufficient background to prove that this
protocol achieves its goals.  I welcome arguments for or against.  Here
is a potentially useful observation:

If a group g contains k cards, then key_g_i is only ever used to encrypt
k messages, and they are all encrypted at once (not at separate times).
This invariant greatly limits the usefulness of tricking players into
encrypting bogus messages, and eliminates the ability to gain advance
knowledge of the result of a future encryption.

Known limitations:

Any player can prevent the game from continuing by deliberately using
the wrong keys, and I see no way to tell who is not cooperating.