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.