Secure Trick-Taking Game Protocols

Abstract

Trick-Taking Games (TTGs) are card games in which each player plays one of his cards in turn according to a given rule. The player with the highest card then wins the trick, i.e., he gets all the cards that have been played during the round. For instance, Spades is a famous TTG proposed by online casinos, where each player must play a card that follows the leading suit when it is possible. Otherwise, he can play any of his cards. In such a game, a dishonest user can play a wrong card even if he has cards of the leading suit. Since his other cards are hidden, there is no way to detect the cheat. Hence, the other players realize the problem later, i.e., when the cheater plays a card that he is not supposed to have. In this case, the game is biased and is canceled. Our goal is to design protocols that prevent such a cheat for TTGs. We give a security model for secure Spades protocols, and we design a scheme called SecureSpades. This scheme is secure under the Decisional Diffie-Hellman assumption in the random oracle model. Our model and our scheme can be extended to several other TTGs, such as Belotte, Whist, Bridge, etc.

1 Introduction

The first card games originate around the 9th century, during the Tang dynasty. Today, they are played all around the world, and a multitude of different games exist. For instance, Poker is probably the most famous gambling card game. Thanks to the Internet, many web sites implement online card game applications, where players meet other players. Cards games websites require some security guarantees, such as secure access for payment, robust software, trusted servers, and cheating detection protocols. These guarantees are crucial for the reputation of the web site in the card game community.

Spades is a famous online gambling card game. It is a trick-taking game: at each round, players take turns playing, then the player that plays the highest card wins the trick, i.e., all cards that have been played this round. Moreover, if it is possible, then players must play a card that follows the suit of the first card played in the round, otherwise they can play any other card. However, if a player cheats by playing a card of another suit while he has some cards of the leading suit, there is no way to detect it immediately. The other players will detect the cheat later, if the cheater plays a card of the leading suit. As a result, the game is biased, because players revealed some of their cards, hence players cannot replay the game, which must be canceled. Cheaters often get a penalty, but Spades is a team game, hence the cheater’s partner is also punished, even if he is not an accomplice. It is even more unfair if the partners do not know each other and/or do not trust each other, which is the case in online games, where teams are chosen by the server.

To avoid this problem, online Spades web sites use a trusted server that manages the game. This server deals the cards, and prevents players from cheating, which means it knows all the cards of each player. However, having a trusted server is a strong security hypothesis, because if some players corrupt the server, then the security properties do not longer hold.

Our motivation is to design a cryptographic scheme, called SecureSpades, that allows the players to check that the other players do not cheat, whithout revealing any information about the cards of each player, and without any trusted server.

Contributions: In this paper, we focus on Trick-Taking Games (TTGs), which are card games where each player plays one of his cards in turn, and where the player with the highest card wins the trick. For the sake of clarity, we focus our work on Spades, because it is the most played online TTG for real money, and its rules are simple. However, our protocol can be extended to other TTGs, such as Whist or Bridge.

We propose a scheme for Spades that has the following security properties:

• The game server is not trusted.

• The players are convinced that nobody cheats. It means that:

  • 1. Theft-resistance: a player cannot play a card that is not in his hand, nor can a player play cards from the hand of his partner.

  • 2. Cheating-resistance: a player cannot play a card that does not follow the rules of the game (in Spades, if a player has a card of the leading suit, he must play it).

• Unpredictability: the cards are dealt at random.

• Hand-privacy: the players do not know the hidden cards of the other players.

• Game-privacy: at each round, the protocol does not leak any information except for the played cards.

We propose a formal definition of a Spades scheme, then we give a formal definition of the security properties described above. We also design SecureSpades, a protocol based on the Decisional Diffie-Hellman (DDH) assumption, and zero-knowledge proofs. Finally, we prove the security of SecureSpades in the random oracle model.

Our protocol not only ensures all the security properties of the real card games, it also provides additional security features. In real card games, it is not possible to detect cheating exactly when the wrong card is played. In fact, our protocol also allows players to detect cheats that are undetectable with real cards, hence it can be used to create new TTGs, for instance a Spades variant where the game is stopped after 5 rounds. In this variant, if the players do not have to reveal the cards they did not play, then there is no way to prevent them from cheating. However, with our approach, such a game can be securely implemented.

Related Work: In 1982, Goldwasser and Micali introduced the Mental Poker problem [10]: it asks whether it is possible to play a fair game of poker without physical cards and without a trusted dealer, i.e., by phone or over the Internet. Since then, several works have focused on this primitive, such as [1, 13, 15]. In [12], the author brings together references to scientific papers related to this problem.

Most of mental poker protocols are based on the following paradigm. The players encrypt the cards together and shuffle them, then ciphertexts are assigned to each player, and each player receives information from the other players in order to decrypt their own cards. At the end of the game, the players reveal their encryption keys, which reveals the hand of all the players. In trick-taking games, each time a player plays a card, he must prove that the card is in his hand and that he has no high-priority card that he should play instead of this card. To achieve this property, we model the deck in a different way: each card is associated to a commitment of the secret key of a player. The player plays a card by proving that the committed secret key matches one of its public keys. This allows the player to prove that he cannot play high-priority cards by proving that none of his public keys match possible high-priority cards.

David et al.  [8] introduced protocols for secure multi-party computation with penalties and secure cash distribution, which can be used for online poker. Bentov et al.  [2] give a poker protocol in a stronger security model, which is more efficient than [8]. More recently, David et al.  [9] proposed Royale, a universally composable protocol for securely playing any card games with financial rewards/penalties enforcement.

All of these works focus on mental card game protocols with secure payment distributions, but they cannot prevent players from cheating by playing illegal cards. Indeed, these protocols allow the users to play cards digitally with the same security level as if they play with real cards. Our goal is not only to implement a secure trick-taking game, but also to increase its security, in comparison with its physical version.

Finally, an other line of research is to detect collusion frauds in online card games, as done for instance in [14]. Players may exchange information about their cards using some side channels. The goal of [14] is to detect such a collusion attack via the users’ behavior. This work is complementary to ours, because these collusion detection processes can also be used with our protocol.

Outline: In Sect. 2, we describe the rules of Spades. In Sect. 3, we give an informal overview of our scheme. In Sect. 4, we present the cryptographic tools used in the paper. In Sect. 5, we model Spades schemes. In Sect. 6, we define the security properties. In Sect. 7, we describe SecureSpades before concluding in the last section.

2 Spades Rules

Spades was created in the United States in the 1930s. Since the mid-1990s it has become very popular thanks to its accessibility in online card gaming rooms on the Internet. This game uses a standard deck of 52 cards and allows between two and five players. The most famous version requires four players, which are splitted in two teams of two. As indicated by the name of the game, spades are always trump. We give the rules of Spades for the four players version:

• 1. All 52 cards are distributed one by one to each player, meaning each player has 13 cards at the beginning of the game.

• 2. There are 13 successive rounds. In the first round, the first player is chosen at random, and subsequently the player that won the previous round begins. Players then each play a card in turn.

• 3. At each round, the player who plays the highest card wins the trick (i.e., he takes the four cards played this round, but he cannot replay these cards). The rank of the cards is the following, form highest to lowest: Ace, King, Queen, Jack, 10, 9, 8, 7, 6, 5, 4, 3, 2. Trumps are higher than cards of the suit of the first card of the round, which are higher than all other cards.

• 4. Each player has to follow the suit of the first card of the round. If a player has no card that follows the suit, then he can play any other cards.

• 5. The game is finished once all players have played all of their cards.

Before playing the cards, each player bids the number of tricks he expects to perform. The sum of all the propositions for all players should be different from the number of cards per player. At the end of the game, each player calculates his score according to his bid and the number of tricks he has won.

3 An Overview of Our Protocol

We now give an informal overview of our Spades protocol. The idea is that the players must prove that each card they play follows the rule of the game. More precisely, the player first proves that he has the played card. If this card does not follow the suit, then he proves that none of his other cards are of the leading suit.

• 1. Dealing cards: We need to model the cards in such a way that these proofs are feasible. Each player i generates 13 pairs of public/private keys $(\mathsf {pk}_{i,j},\mathsf {sk}_{i,j})$ (for $1\le j \le 13$). To deal the cards, the players run a protocol that privately assigns each key to each card with the following steps: (i) each player generates commitments on his 13 secret keys, (ii) the players group all the $13 \cdot 4 =52$ commitments together, (iii) each player shuffles and randomizes the commitments in turn, (iv) the players jointly associate each commitment to each card of the deck at random. The hand of a player is the set of the 13 cards that match the commitments of his secret keys. Figure 1 illustrates our dealing cards protocol, where $c(\mathsf {sk})$ denotes the commitment of a secret key $\mathsf {sk}$, and $c'(\mathsf {sk})$ denotes the randomization of $c(\mathsf {sk})$. In this example, the $1^\text {st}$ card of player 1 is A$\clubsuit$, his $2^{nd}$ card is 2$\heartsuit$, and his $13^\text {th}$ card is A$\spadesuit$. Note that the commitments and the public keys must be unlinkable for anyone who does not know the corresponding secret keys.

• 2. Play a card: To play a card, the player proves that this card matches the commitment of one of his secret keys. If the player does not follow the suit, then he proves that none of his other cards are of the leading suit. To do so, he proves that each commitment that matches a card of a non-leading suit commits one of his (not yet used) keys.

Fig. 1.

Dealing cards in our Spades protocol.

4 Cryptographic Tools

We present the cryptographic tools used throughout this paper.

Definition 1

 [4]). Let $\mathbb {G}$ be a prime order group. The $\textsf {DDH}$ assumption states that given $(g,g^a, g^b, g^z)\in \mathbb {G}^4$, it is hard to decide whether $z=a\cdot b$ or not.

A n-party random generator is a protocol that allows n users to generate a random number, even if $n-1$ users are dishonest.

Definition 2

(Multi-party random generator [3]). A n-party $\mathcal {S}$-random generator $\mathsf {RG}_{P_1,\ldots ,P_n}$ is a protocol where n parties $(P_1,\ldots ,P_n)$ interact, and return $s\in \mathcal {S}$. Such a protocol is said to be secure when for any polynomial time distinguisher $\mathcal {D}$, any polynomial time adversary $\mathcal {A}$, there exists a negligible function $\epsilon$ such that: $| \textsf {Pr}[ 1 \leftarrow {D}(s) : s\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,\mathcal {S} ] - \textsf {Pr}[ 1 \leftarrow {D}(s) : s \leftarrow \mathsf {RG}_{\mathcal {C}, \mathcal {A}}(k) ] | \le \epsilon (k)$ where $s\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,\mathsf {RG}_{\mathcal {C}, \mathcal {A}}$ denotes the output of $\mathcal {C}$ at the end of the protocol $\mathsf {RG}$ where $\mathcal {C}$ plays the role of a honest user, and $\mathcal {A}$ plays the role of the $n-1$ other users.

Inspired by [3], we propose the following multi-party random generator protocol based on the random oracle model (ROM).

Definition 3

Let $\mathcal {S}$ be a set and n be an integer, and let $H:\left\{ 0,1\right\} ^* \rightarrow \left\{ 0,1\right\} ^k$ and $H':\left\{ 0,1\right\} ^* \rightarrow \mathcal {S}$ be two hash functions simulated by random oracles. The protocol $\mathsf {RandGen}^\mathcal {S}_{P_1, \ldots ,P_n}(k)$ is a n-party $\mathcal {S}$-random generator defined as follows. Each player $P_i$ (where $1\le i \le n)$ chooses $r_i\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,\left\{ 0,1\right\} ^k$ at random, computes $H(r_i)$, and broadcasts it, then each player reveals $r_i$. Each player returns $H'(r_0|| \ldots ||r_n)$.

Lemma 1

For any set $\mathcal {S}$ and any integer n, $\mathsf {RandGen}^\mathcal {S}_{P_1, \ldots ,P_n}(k)$ is secure in the random oracle model.

The proof of this lemma is given in the full version of this paper [6]. The idea is that dishonest parties cannot guess the $r_i$ of the honest parties before revealing their commitments, hence they cannot predict $H(r_0|| \ldots ||r_n)$.

A (non-interactive) Zero-Knowledge Proof of Knowledge (ZKP) [11] for a binary relation $\mathcal {R}$ allows a prover knowing a witness w to convince a verifier that a statement s verifies $(s,w)\in \mathcal {R}$ without leaking any information. Throughout this paper, we use the Camenisch and Stadler notation [7], i.e.,  $\mathsf {ZK}\{(w):(w,s)\in \mathcal {R}\}$ denotes the proof of knowledge of w for the statement s and the relation $\mathcal {R}$. Such a proof is said to be extractable when given an algorithm that generates valid proofs with some probability, there exists an algorithm that returns the corresponding witness in a similar running time with at least the same probability. Such a proof is said to be zero-knowledge when there exists a polynomial time simulator that follows the same probability distribution as an honest prover.

5 Formal Definitions

We formalize Spades schemes and the corresponding security requirements. We model a 52 cards deck by a tuple $D = (\mathsf {id}_1, \ldots , \mathsf {id}_{52})$ such that $\forall ~i \in [\![1 , 52 ]\!]$, $\mathsf {id}_i = (\mathsf {id}_i\textsf {.suit},\mathsf {id}_i\textsf {.val})\in \left\{ \heartsuit ,\spadesuit ,\diamondsuit ,\clubsuit \right\} \times \left\{ 1, \ldots ,10,\mathsf {J},\mathsf {Q},\mathsf {K}\right\}$ is called a card, where $\forall ~(i,j) \in [\![1 , 52 ]\!]^2$ such that $i\not = j$, $\mathsf {id}_i \not = \mathsf {id}_j$. The set of all possible decks is denoted by $\mathsf {Decks}$.

We first define Spades schemes, which are tuples that contain all the algorithms that are used by the players. $\mathsf {KeyGen}$ allows each player to generate its public/secret key. $\mathsf {GKeyGen}$ allows the players to generate a public game key. $\mathsf {DeckGen}$ is a protocol that generates a random deck. $\mathsf {GetHand}$ determines the hand of a given player from his secret key and the game key. $\mathsf {Play}$ allows a player to play a card, and to prove that it is a legal play. $\mathsf {Verif}$ allows the other players to check this proof. Finally, $\mathsf {GetSuit}$ returns the leading suit of the current round (in Spades, the suit of the first card played during this round).

Definition 4

A Spade scheme is a tuple of eight algorithms $W=(\mathsf {Init},$ $\mathsf {KeyGen},$ $\mathsf {GKeyGen}, \mathsf {DeckGen}, \mathsf {GetHand},\mathsf {Play},\mathsf {Verif},\mathsf {GetSuit})$ defined as follows:

• $\mathsf {Init}(k)$: It returns a setup $\textsf {setup}$.

• $\mathsf {KeyGen}(\textsf {setup})$: It returns a key pair $(\mathsf {pk},\mathsf {sk})$.

• $\mathsf {GKeyGen}$: It is a 4-party protocol, where for all $j\in [\![1,4]\!]$ the $j^{\text {th}}$ party is denoted $\mathsf {P}_j$ and takes as input $(\mathsf {sk}_j,\{\mathsf {pk}_i\}_{1\le i \le 4})$. This protocol returns a game public key $\mathsf {PK}$, or the bottom symbol $\perp$.

• $\mathsf {DeckGen}$: It is a 4-party $\mathsf {Decks}$-random generator.

• $\mathsf {GetHand}(\mathsf {sk},\mathsf {pk},\mathsf {PK},D)$: It returns a set of 13 different cards H called a hand (where $D\in \mathsf {Decks}$).

• $\mathsf {Play}(n,\mathsf {id},\mathsf {sk},\mathsf {pk},\mathrm {st},\mathsf {PK},D)$: It takes as input a player index $n\in [\![1,4]\!]$, a card $\mathsf {id}$, a pair of secret/public key, a global state $\mathrm {st}$ that stores the relevent information about the previous plays, the game public key $\mathsf {PK}$ and the deck D, and returns a proof $\varPi$, and the updated global state $\mathrm {st}'$.

• $\mathsf {Verif}(n,\mathsf {id},\varPi ,\mathsf {pk}, \mathrm {st}, \mathrm {st}', \mathsf {PK},D)$: It takes as input a player index $n\in [\![1,4]\!]$, a card identity $\mathsf {id}$, a proof $\varPi$ generated by the algorithm $\mathsf {Verif}$, the global state $\mathrm {st}$ and the updated global state $\mathrm {st}'$, the game public key $\mathsf {PK}$ and the deck D, and returns a bit b. If $b=1$, we say that $\varPi$ is valid.

• $\mathsf {GetSuit}(\mathrm {st})$: It returns a suit $\mathsf {suit} \in \left\{ \heartsuit ,\spadesuit ,\diamondsuit ,\clubsuit \right\}$ from the current global state of the game $\mathrm {st}$, where $\mathsf {suit}$ is the leading suit for the current turn.

We then define the Spades protocol, which allows four players to play Spades using the algorithms of the Spades scheme. It is divided in four phases:

• Initialisation phase: One player generates and broadcasts the public setup.

• Keys generation phase: After they have generated their public/private keys, the players run $\mathsf {GKeyGen}$ to generate the game key together.

• Shuffle phase: The players choose a deck using $\mathsf {DeckGen}$, then they compute their own hand using $\mathsf {GetHand}$.

• Game phase: Finally, they play in turn using the algorithms $\mathsf {Play}$ and $\mathsf {Verif}$ to prove the validity of the cards they play. If some verification fails, the player has to cancel only the last card he has played, and to simply play another card.

Definition 5

Let $W=(\mathsf {Init},\mathsf {KeyGen},\mathsf {GKeyGen}, \mathsf {DeckGen}, \mathsf {GetHand},\mathsf {Play},\mathsf {Verif},$ $\mathsf {GetSuit})$ be a Spades scheme and $k\in \mathbb {N}$ be a security parameter. Let $\mathsf {Player}_1,$ $\mathsf {Player}_2$, $\mathsf {Player}_3$, $\mathsf {Player}_4$ be four polynomial time algorithms. The Spades protocol instantiated by W and the setup $\textsf {setup}$ between $\mathsf {Player}_1, \mathsf {Player}_2$, $\mathsf {Player}_3$ and $\mathsf {Player}_4$ is the following protocol:

• Initialisation phase: $\mathsf {Player}_1$ runs $\textsf {setup}\leftarrow \mathsf {Init}(k)$ and broadcasts $\textsf {setup}$.

• Keys generation phase: The players set $\mathrm {st}\,=\,\perp$. Each player $\mathsf {Player}_i$ runs $(\mathsf {pk}_i,\mathsf {sk}_i) \leftarrow \mathsf {KeyGen}(\textsf {setup})$ and broadcasts $\mathsf {pk}_i$, then the players generate $\mathsf {PK}$ by running the protocol $\mathsf {GKeyGen}$ together.

• Shuffle phase: The players generate a deck $D\in \mathsf {Decks}$ by running $\mathsf {DeckGen}$ together. For all $i\in [\![1,4]\!],$ $\mathsf {Player}_i$ runs $H_i\leftarrow \mathsf {GetHand}(\mathsf {sk}_i,\mathsf {pk}_i,$ $\mathsf {PK}, D)$.

• Game phase: This phase is composed of 52 (sequential) steps (corresponding to the 52 cards played in a game). The players initialize the current player index $p=1$. At each turn, $\mathsf {Player}_p$ designates the player who plays. Each step proceeds as follows:

  • $\mathsf {Player}_p$ chooses $\mathsf {id}\in H_p$, then runs $(\varPi ,\mathrm {st}') \leftarrow \mathsf {Play}(p,\mathsf {id},\mathsf {sk}_p,\mathsf {pk}_p,\mathrm {st},$ $\mathsf {PK},D)$.

  • For all $i\in [\![1,4]\!]\backslash \left\{ p\right\}$, $\mathsf {Player}_p$ sends $(\mathsf {id},\varPi ,\mathrm {st}')$ to $\mathsf {Player}_i$.

  • Each $\mathsf {Player}_i$ then checks that $\mathsf {Verif}(p,\mathsf {id},\varPi , \mathsf {pk}_p,\mathrm {st}, \mathrm {st}', \mathsf {PK},D)=1$, otherwise, $\mathsf {Player}_i$ sends $\mathtt {error}$ to $\mathsf {Player}_p$, who repeats this step and plays a valid card.

  • If $\mathsf {Verif}(p,\mathsf {id},\varPi ,\mathsf {pk}_p, \mathrm {st}, \mathrm {st}', \mathsf {PK},D)=1$, all players update the state $\mathrm {st}:= \mathrm {st}'$, and update the index p that points the next player according to the rule of the game.

6 Security Properties

We first define Spades strategies. In a card game, each player chooses what card he wants to play depending on his hand and the previously played cards of the other players. In order to formalize the security of our protocol, we need to model honest players who choose the cards they play themselves. A Spades strategy is an algorithm that decides which card to play using all known information by a given player. We define security experiments where the choices of each honest player is simulated by a Spades strategy. The idea is that a Spades scheme is secure if for any polynomial time adversary, the probability of winning the experiment is negligible, whatever the Spades strategies used by the experiment.

Definition 6

A Spades strategy is a polynomial time algorithm $\mathsf {Strat}$ that takes as input a tuple of cards $\mathsf {played}$ (which represents all cards played at some point in a Spades game) and a set of cards $\mathsf {hand}$ (which represents all cards of a player at the same point), a first player index $p_*$, a player index p, and that returns a card $\mathsf {id}\in \mathsf {Hand}$ which is valid according to the rules of Spades (i.e., that follows the suit of the first card of the current round).

We define an experiment where a challenger simulates the Spades protocol to an adversary. We use this experiment to define Spades’ security properties. The adversary first chooses the index of the player he wants to corrupt. The challenger generates the public/secret keys of the three other users, then the adversary sends his public key together with the index of an accomplice. The accomplice allows the experiment to capture the attacks where a dishonest player and his game partner collude. The adversary has access to the private key of all players. The adversary and the challenger then run the game key and the deck generation protocol, such that the adversary plays the role of the corrupted player and the accomplice. The challenger generates the hand of each player. Note that the challenger cannot use the hand generation algorithm for the corrupted player, because he does not know his secret key; however, the challenger can deduce this hand because it contains the 13 cards that are not in the hand of the three other users. Finally, the challenger and the adversary run the game phase, such that the adversary plays the role of the corrupted user and his accomplice.

Definition 7

Let $W=(\mathsf {Init}, \mathsf {KeyGen}, \mathsf {GKeyGen}, \mathsf {DeckGen}, \mathsf {GetHand},$ $\mathsf {Play},$ $\mathsf {Verif},$ $\mathsf {GetSuit})$ be a Spades scheme, $S=(\mathsf {Strat}_1,\mathsf {Strat}_2,\mathsf {Strat}_3,\mathsf {Strat}_4)$ be a tuple of strategies, and $k\in \mathbb {N}$ be a security parameter. Let $\mathcal {A}$ and $\mathcal {C}$ be two polynomial time algorithms. The Spades experiment $\textsf {Exp}_{W,S,\mathcal {A}}^{\mathsf {Spades}}(k)$ instantiated by W and S between the adversary $\mathcal {A}$ and the challenger $\mathcal {C}$ is defined as follows:

• Keys generation phase: $\mathcal {C}$ runs $\textsf {setup}\leftarrow \mathsf {Init}(k)$, sets $\mathrm {st}= \perp$, and sends the pair $(\textsf {setup},\mathrm {st})$ to $\mathcal {A}$, who returns a corrupted user index ${i_c}\in [\![1,4 ]\!]$. For all $i\in [\![1,4 ]\!]\backslash \left\{ {i_c}\right\}$, $\mathcal {C}$ runs $(\mathsf {pk}_i,\mathsf {sk}_i) \leftarrow \mathsf {KeyGen}(\textsf {setup})$ and sends $(\mathsf {pk}_i,\mathsf {sk}_i)$ to $\mathcal {A}$, who returns the public key $\mathsf {pk}_{i_c}$ and an accomplice index $i_a$.

• Game key generation phase: $\mathcal {C}$ and $\mathcal {A}$ generate $\mathsf {PK}$ by running the algorithm $\mathsf {GKeyGen}$ together, such that $\mathcal {A}$ plays the role of the players $P_{i_c}$ and $P_{i_a}$, and $\mathcal {C}$ plays the role of the other players. If $\mathsf {PK}= \perp$, then $\mathcal {C}$ aborts and returns 0.

• Shuffle phase: $\mathcal {C}$ and $\mathcal {A}$ generate D by running the algorithm $\mathsf {DeckGen}$ together, such that $\mathcal {A}$ plays the role of the players $P_{i_c}$ and $P_{i_a}$, and $\mathcal {C}$ plays the role of the two other players. $\mathcal {C}$ sets $p=1$ and parses D as $(\mathsf {id}_1, \ldots ,\mathsf {id}_{52})$. For all $i\in [\![1,4 ]\!]\backslash \left\{ {i_c}\right\}$, $\mathcal {C}$ runs $H_i \leftarrow \mathsf {GetHand}(\mathsf {sk}_i,\mathsf {pk}_i,\mathsf {PK},D)$, and sets $H_{i_c} = \left\{ \mathsf {id}_i \right\} _{1\le i \le 52} \backslash (\cup _{i=1;i\not = {i_c}}^{4} H_i)$.

• Game phase: $\mathcal {C}$ initializes the current player index $p=1$ and the corrupted play index $\gamma = 0$, and $\mathsf {played} = \perp$. For $i\in [\![1 , 52 ]\!]$:

  • If $p \not = {i_c}$and $p \not = {i_a}$: $\mathcal {C}$ runs $\mathsf {id}\leftarrow \mathsf {Strat}_p(\mathsf {played},H_p,p_*,p)$, then $\mathcal {C}$ runs $(\varPi ,\mathrm {st}') \leftarrow \mathsf {Play}(p,\mathsf {id},\mathsf {sk}_p,\mathsf {pk}_p,\mathrm {st},\mathsf {PK},D).$ $\mathcal {C}$ sends $(\mathsf {id},\varPi ,\mathrm {st}')$ to $\mathcal {A}$ and updates $\mathrm {st}:= \mathrm {st}'$.

  • If $p = {i_a}$: $\mathcal {C}$ receives $(\mathsf {id},\varPi ,\mathrm {st}')$ from $\mathcal {A}$. If $\mathsf {Verif}(i_a,\mathsf {id},\varPi , \mathsf {pk}_{i_a}, \mathrm {st}, \mathrm {st}', \mathsf {PK},D)$ $=0$, then $\mathcal {C}$ aborts and the experiment returns 0. Else, $\mathcal {C}$ updates $\mathrm {st}:= \mathrm {st}'$.

  • If $p = {i_c}$: $\mathcal {C}$ increments $\gamma := \gamma + 1$, then receives $(\mathsf {id},\varPi ,\mathrm {st}')$ from $\mathcal {A}$ and sets $(\mathsf {id}_{{i_c},\gamma },\varPi _{{i_c},\gamma })=(\mathsf {id},\varPi )$. $\mathcal {C}$ sets $\mathrm {st}_\gamma = \mathrm {st}$ and $\mathrm {st}'_\gamma =\mathrm {st}'$. $\mathcal {C}$ sets $\mathsf {suit}_{{i_c},\gamma } = \mathsf {GetSuit}(\mathrm {st})$. If $\mathsf {Verif}(i_c,\mathsf {id}_{{i_c},\gamma },\varPi _{{i_c},\gamma }, \mathsf {pk}_{i_c}, \mathrm {st}_\gamma , \mathrm {st}_\gamma ', \mathsf {PK},D)=0$, then $\mathcal {C}$ aborts and the experiment returns 0. Else, $\mathcal {C}$ updates $\mathrm {st}:= \mathrm {st}'$.

  $\mathcal {C}$ then updates the index p that points to the next player according to the rule of Spades, parses $\mathsf {played}$ as $(\mathsf {pl}_1, \ldots , \mathsf {pl}_n)$ (where $n=|\mathsf {played}|$) and updates $\mathsf {played}:=(\mathsf {pl}_1, \ldots , \mathsf {pl}_n,\mathsf {id})$.

• Final phase: The experiment returns 1.

The first security property of a Spades scheme is the theft-resistance, which ensures that no adversary is able to play a card that is not in his hand, even if the card is in the hand of his accomplice. On the other words, two partners are not able to exchange their cards.

Definition 8

A Spades scheme W is said to be theft-resistant if for any tuple of strategies $S=(\mathsf {Strat}_1,\mathsf {Strat}_2,\mathsf {Strat}_3,\mathsf {Strat}_4)$ and any polynomial time adversary $\mathcal {A}$ who plays the Spade experiment instantiated by W and S, the probability that there exists $\gamma \in [\![1, 13 ]\!]$ such that:

• $\mathsf {Verif}(i_c,\mathsf {id}_{{i_c},\gamma },\varPi _{{i_c},\gamma }, \mathsf {pk}_{i_c}, \mathrm {st}_\gamma , \mathrm {st}'_\gamma , \mathsf {PK},D)=1$, i.e., the $\gamma ^\text {th}$ play of the adversary is accepted for the card $\mathsf {id}_{{i_c},\gamma }$; and

• $\forall ~\mathsf {id}\in H_{i_c}, \mathsf {id}_{{i_c},\gamma } \not = \mathsf {id}$, i.e., the card $\mathsf {id}_{{i_c},\gamma }$ is not in the adversary hand;

is negligible.

We then define the cheating-resistance property, which ensures that no adversary is able to play a card if he should play another valid one.

Definition 9

A Spades scheme W is said to be cheating-resistant if for any tuple of strategies $S=(\mathsf {Strat}_1,\mathsf {Strat}_2,\mathsf {Strat}_3,\mathsf {Strat}_4)$ and any polynomial time adversary $\mathcal {A}$ who plays the Spade experiment instantiated by W and S, the probability that there exists $\gamma \in [\![1, 13 ]\!]$ such that:

• $\mathsf {Verif}(i_c\mathsf {id}_{{i_c},\gamma },\varPi _{{i_c},\gamma }, \mathsf {pk}_{i_c}, \mathrm {st}_\gamma , \mathrm {st}'_\gamma , \mathsf {PK},D)=1$, i.e., the $\gamma ^\text {th}$ play of the adversary is accepted for the card $\mathsf {id}_{{i_c},\gamma }$; and

• $\mathsf {id}_{{i_c},\gamma }\textsf {.}\mathsf {suit} \not = \mathsf {suit}_{{i_c},\gamma }$ and $\mathsf {suit}_{i_c,\gamma } \not = \perp$ i.e., the suit of the card $\mathsf {id}_{{i_c},\gamma }$ is not the leading suit; and

• $\exists ~\bar{\mathsf {id}} \in H_{i_c}$ such that: $\forall ~l\le \gamma , \mathsf {id}_{{i_c},l} \not = \bar{\mathsf {id}}$ and $\bar{\mathsf {id}}\textsf {.}\mathsf {suit} = \mathsf {suit}_{{i_c},\gamma }$. i.e., the adversary has a card of the leading suit in his hand that was not already played before the $\gamma ^\text {th}$ play;

is negligible.

We define the unpredictability, which ensures that no adversary can influence the card dealing, i.e.,  $\mathcal {A}$ cannot predict which card will be in which hand.

Definition 10

A Spades scheme W is said to be unpredictable if for any tuple of strategies $S=(\mathsf {Strat}_1,\mathsf {Strat}_2,\mathsf {Strat}_3,\mathsf {Strat}_4)$, any polynomial time adversary $\mathcal {A}$ who plays the Spades experiment instantiated by W and S, for all $i\in [\![1,52 ]\!]$ the probability that $\mathsf {id}_i \in H_{i_c}$ is negligibly close to 1/4.

We introduce a new experiment that is called the hand Spades experiment, where the challenger simulates the key generation phase of the Spades protocol (but not the game phase). In this experiment the adversary does not know the private keys of the other players and has no accomplice. This experiment will be used to model the attacks where an adversary tries to guess the cards of the other players, including his partner.

Definition 11

Let $W=(\mathsf {Init},\mathsf {KeyGen},\mathsf {GKeyGen}, \mathsf {DeckGen}, \mathsf {GetHand},\mathsf {Play},\mathsf {Verif},$ $\mathsf {GetSuit})$ be a Spades scheme and $k\in \mathbb {N}$ be a security parameter. Let $\mathcal {A}$ and $\mathcal {C}$ be two polynomial time algorithms. The hand Spades experiment $\textsf {Exp}_{W,\mathcal {A}}^{\mathsf {HSpades}}(k)$ instantiated by W between the adversary $\mathcal {A}$ and the challenger $\mathcal {C}$ is defined by:

• Key generation phase: $\mathcal {C}$ runs $\textsf {setup}\leftarrow \mathsf {Init}(k)$. It sets $\mathrm {st}\,=\,\perp$. It sends the pair $(\textsf {setup},\mathrm {st})$ to $\mathcal {A}$, who returns ${i_c}\in [\![1,4 ]\!]$. For all $i\in [\![1,4 ]\!]\backslash \left\{ {i_c}\right\}$, $\mathcal {C}$ runs $(\mathsf {pk}_i,\mathsf {sk}_i) \leftarrow \mathsf {KeyGen}(\textsf {setup})$ and sends $\mathsf {pk}_i$ to $\mathcal {A}$, who returns $\mathsf {pk}_{i_c}$.

• Game key generation phase: $\mathcal {C}$ and $\mathcal {A}$ generate $\mathsf {PK}$ by running the algorithm $\mathsf {GKeyGen}$ together, such that $\mathcal {A}$ plays the role of $P_{i_c}$, and $\mathcal {C}$ plays the role of the three other players. If $\mathsf {PK}\,=\,\perp$, then $\mathcal {C}$ aborts and returns 0.

• Shuffle phase: $\mathcal {A}$ sends a deck $D\in \mathsf {Decks}$ to $\mathcal {C}$. $\mathcal {C}$ parses D as $(\mathsf {id}_1, \ldots ,\mathsf {id}_{52})$. For all $i\in [\![1,4 ]\!]\backslash \left\{ {i_c}\right\}$, $\mathcal {C}$ runs $H_i \leftarrow \mathsf {GetHand}(\mathsf {sk}_i,\mathsf {pk}_i,\mathsf {PK},D)$, and sets $H_{i_c} = \left\{ \mathsf {id}_i \right\} _{1\le i \le 52} \backslash (\cup _{i=1;i\not = {i_c}}^{4} H_i)$.

• Challenge phase: $\mathcal {C}$ picks $(\theta _0,\theta _1)$ in $([\![1,4 ]\!]\backslash \left\{ {i_c}\right\} )^2$ such that $\theta _0\not = \theta _1$. $\mathcal {C}$ picks $b\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,\left\{ 0,1\right\}$ and $\bar{\mathsf {id}}\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,H_{\theta _{b}}$, and sends $(\bar{id},\theta _0,\theta _1)$ to $\mathcal {A}$, who returns $b_*$.

• Final phase: If $b=b_*$, then $\mathcal {C}$ returns 1, else it returns 0.

We then define the hand-privacy. This property ensures that an adversary has no information about the hand of the other players before the game phase is run.

Definition 12

A Spades scheme W is said to be hand-private if for any tuple of strategies $S=(\mathsf {Strat}_1,\mathsf {Strat}_2,\mathsf {Strat}_3,\mathsf {Strat}_4)$ and any polynomial time adversary $\mathcal {A}$ who plays the hand-Spades experiment instantiated by W and S, the probability that the experiment returns 1 is negligibly closed to 1/2.

The last property is the game-privacy. The idea is that, at each step of the game phase, the players learn nothing else than the cards that have been previously played. We show that, after the game key is generated, each player is able to simulate all the protocol interactions knowing the players’ strategies. More formally, there exists a simulator that takes as input values known by the player such that the player cannot distinguish whether he plays the real game experiment or he interacts with the simulator.

Definition 13

For any $k\in \mathbb {N}$, any Spades scheme W, any quadruplet of strategies S, any adversary $\mathcal {D}$ and any $K=(\textsf {setup},\mathsf {pk}_{i_c},\left\{ (\mathsf {pk}_i,\mathsf {sk}_i)\right\} _{1\le i \le 4; i \not = {i_c}},\mathsf {PK})$, $Exp_{W,S,K,\mathcal {D}}^{\mathsf {Spades}}(k)$ denotes the same experiment as $Exp_{W,S,\mathcal {D}}^{\mathsf {Spades}}(k)$ except:

• 1. The challenger and the adversary use the setup and the keys in K instead of generating fresh setup and keys during the experiment.

• 2. The challenger does not send $\mathsf {sk}_i$ for all $1\le i \le 4$ such that $i\not = i_c$ to $\mathcal {A}$, and $\mathcal {A}$ has no accomplice.

A Spades scheme W is said to be game-private if there exists a polynomial time simulator $\mathsf {Sim}$ such that for any tuple of strategies S and any polynomial time 5-party algorithm $\mathcal {D}=(\mathcal {D}_1,\mathcal {D}_2,\mathcal {D}_3,\mathcal {D}_4,\mathcal {D}_5)$, $|P_{\mathsf {real}}(\mathcal {D},k) - P_{\mathsf {sim}}(\mathcal {D},k)|$ is negligible, where

and where $\mathsf {vw}$ denotes the view of $\mathcal {D}$, i.e., all the values sent and received by each algorithm of $\mathcal {D}$ during his interaction with the experiment.

Note that if a scheme is both hand-private and private-game, then players have no information about the other players’ hands except for all the cards they have already played.

7 Schemes

We first informally show how our protocol, SecureSpades, works, then we give its formal definition.

• Keys generation. Each player i generates 13 key pairs $(\mathsf {pk}_{i,j},\mathsf {sk}_{i,j})$ for $1\le j\le 13$ such that $\mathsf {pk}_{i,j} = g^{\mathsf {sk}_{i,j}}$. The players then generate a game key $\mathsf {PK}$ together, which is made of 52 pairs $(h_l,\mathsf {PK}_l)$ such that ${h_l}^{\mathsf {sk}_{i,j}}=\mathsf {PK}_l$. The keys $\mathsf {PK}_l$ are shuffled, meaning each player does not know which $\mathsf {PK}_l$ corresponds to which $\mathsf {pk}_{i,j}$, except for his own public keys. To build $\mathsf {PK}$, for all $l\in [\![1,52 ]\!]$ the players set $h_{0,l} = g$ and $\mathsf {PK}_{0,l}=\mathsf {pk}_{i,j}$ such that (i, j) is in $[\![1,4]\!]\times [\![1,13]\!]$ and is different for each l. Note that it holds that ${h_{0,l}}^{\mathsf {sk}_{i,j}} =\mathsf {PK}_{0,l}$. The first player then randomizes and shuffles all pairs $(h_{0,l},\mathsf {PK}_{0,l})$, i.e., he chooses a random vector r and a random permutation $\delta$ and computes $h_{{1},l} = (h_{0,\delta (i)})^{r_{i}}$ and $\mathsf {PK}_{{1},l} = (\mathsf {PK}_{0,\delta (i)})^{r_{i}}$. The three other players randomize and shuffle the pairs $(h_{n,l},\mathsf {PK}_{n,l})$ in order to obtain the pairs $(h_{n+1,l},\mathsf {PK}_{n+1,l})$ for $1\le n \le 3$ in turn in the same way, then they set $(h_{l},\mathsf {PK}_{l})=(h_{4,l},\mathsf {PK}_{4,l})$ for all l. If the shuffles are correctly built, then it holds that for each l there exists a different pair (i, j) such that ${h_{l}}^{\mathsf {sk}_{i,j}} =\mathsf {PK}_{l}$. After each shuffle, the player proves that each $(h_{i,l},\mathsf {PK}_{i,l})$ is a correct randomization of one $(h_{i-1,l'},\mathsf {PK}_{i-1,l'})$ where $1\le l' \le 52$. Each player then checks that each of his secret keys match one $\mathsf {PK}_l$, otherwise he aborts the protocol. Since each player shuffles the keys using a secret permutation, they do not know which $\mathsf {PK}_l$ matches which $\mathsf {pk}_{i,j}$, except for their own public keys.

• Hand generation. Players generate a random deck $D=(\mathsf {id}_1, \ldots , \mathsf {id}_{52})$ using the $\mathsf {RandGen}^{\mathsf {Deck}}$ protocol, then for all $1\le l \le 52$, the key $\mathsf {PK}_l$ corresponds to the card $\mathsf {id}_l$. The hand of the player i is the set of all cards $\mathsf {id}_l$ such that there exists $1\le j\le 13$ such that ${h_{l}}^{\mathsf {sk}_{i,j}} =\mathsf {PK}_{l}$. Since the player does not know the keys $\mathsf {sk}_{i',j}$ for $i' \not = i$, he does not know the cards of the other players.

• Play a card. To play the card $\mathsf {id}_l$, the player i proves that the card $\mathsf {id}_l$ matches one of his key $\mathsf {pk}_{i,j}$ by showing that ${h_{l}}^{\mathsf {sk}_{i,j}} =\mathsf {PK}_{l}$. Note that since the player does not reveal $sk_ {i, j}$, he can use the same set of public keys for different games. To prove that he cannot play any card of the leading suit, the player i sets L such that $l\in L$ if and only if $\mathsf {id}_l$ is not of the leading suit, then the player i proves in a zero-knowledge way that for all $\mathsf {pk}_{i,j}$ that correspond to cards that are not already played, there exists an (unrevealed) $l\in L$ such that $\log _{h_l}(\mathsf {PK}_l)=\log _{g}(\mathsf {pk}_{i,j})$. This implies that the player has no card of the leading suit, hence he is not cheating.

Definition 14

SecureSpades is a Spades scheme defined as follows:

• $\mathsf {Init}(k)$: It generates a group $\mathbb {G}$ of prime order q, a generator $g\in \mathbb {G}$ and returns $(\mathbb {G},p,g)$.

• $\mathsf {KeyGen}(\textsf {setup})$: For all $i\in [\![1,13 ]\!]$, it picks $\mathsf {sk}_i\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,\mathbb {Z}^*_q$ and computes $\mathsf {pk}_i=g^{\mathsf {sk}_i}$. It returns $\mathsf {pk}=(\mathsf {pk}_1, \ldots , \mathsf {pk}_{13})$ and $\mathsf {sk}=(\mathsf {sk}_1, \ldots , \mathsf {sk}_{13})$.

• $\mathsf {GKeyGen}$: It is a 4-party protocol, where for all $i\in [\![1,4]\!]$ the $i^{\text {th}}$ party is denoted $\mathsf {P}_i$, and takes as input $(\mathsf {sk}_i,\{\mathsf {pk}_j\}_{1\le j \le 4})$. This protocol returns a game public key $\mathsf {PK}$, or the bottom symbol $\perp$. If there exist $(i_1,j_1)$ and $(i_2,j_2)$ such that $(i_1,j_1)\not =(i_2,j_2)$ and $\mathsf {pk}_{i_1,j_1}=\mathsf {pk}_{i_2,j_2}$, then the players abort and return $\perp$.

  • For all $i\in [\![1,4 ]\!]$, each player parses $\mathsf {pk}_i$ as $(\mathsf {pk}_{i,1}, \ldots ,\mathsf {pk}_{i,13})$. For all $j\in [\![1, 13 ]\!]$, each player sets $h_{0,(i-1)\cdot 13 + j}=g$ and $\mathsf {PK}_{0,(i-1)\cdot 13 + j}=\mathsf {pk}_{i,j}$.

  • Each player $P_i$ (for ${i} \in [\![1, 4 ]\!]$) does the following step in turn: $\mathsf {P}_{i}$ picks $r = (r_{1}, \ldots ,$ $r_{52})\,{\mathop {\leftarrow }\limits ^{{}_\$}}\,(\mathbb {Z}^*_q)^{52}$, and a permutation $\delta$ on the set $[\![1, 52 ]\!]$. $P_i$ computes $h_{{i},l}=h_{{i}-1,\delta (l)}^{r_{l}}$ and $\mathsf {PK}_{{i},l} = (\mathsf {PK}_{{i}-1,\delta (l)})^{r_{l}}$ for all ${l} \in [\![1 , 52 ]\!]$, then runs $\varPi _{i}=$ $\mathsf {ZK}\left\{ (r,\delta ) : \bigwedge _{l=1}^{52} \left( h_{{i},l}=h_{{i}-1,\delta (l)}^{r_{l}} \wedge \mathsf {PK}_{{i},l} = \mathsf {PK}_{{i}-1,\delta (l)} ^ {r_{l}} \right) \right\}$. This proof ensures that each $(h_{{i},l},\mathsf {PK}_{{i},l})$ is the randomization of one pair $(h_{{i-1},l'},\mathsf {PK}_{{i-1},l'})$ for $l'\in [\![1,52]\!]$. $\mathsf {P}_{i}$ broadcasts $\{(h_{{i},l},\mathsf {PK}_{{i},l})\}_{1\le l \le 52}$ and $\varPi _{i}$, then each player verifies the proof $\varPi _{i}$. If the verification fails, then the player aborts and returns $\perp$.

  • If there exists j such that for all l, $h_{4,l}^{\mathsf {sk}_{i,j}} \not = \mathsf {PK}_{4,l}$, then $\mathsf {P}_{i}$ aborts the protocol and returns $\perp$. For each ${i} \in [\![1 , 4 ]\!]$, $\mathsf {P}_{i}$ sets $\mathsf {PK}'_i=((h_{4,1},\mathsf {PK}_{4,1}), \ldots ,$ $(h_{4,52},\mathsf {PK}_{4,52}))$ and broadcasts it. If there exists $i_1$ and $i_2$ such that $\mathsf {PK}'_{i_1} \not = \mathsf {PK}'_{i_2}$, then $\mathsf {P}_{i}$ aborts and returns $\perp$, else $P_i$ returns $\mathsf {PK}=\mathsf {PK}'_i$.

• $\mathsf {DeckGen}$: It is the 4-party $\mathsf {Deck}$-random generator $\mathsf {RandGen}^{\mathsf {Deck}}$ protocol.

• $\mathsf {GetHand}(\mathsf {sk},\mathsf {pk},\mathsf {PK},D)$: It parses $\mathsf {sk}$ as $(\mathsf {sk}_{1}, \ldots ,$ $\mathsf {sk}_{13})$, $\mathsf {PK}$ as $((h_1,\mathsf {PK}_1), \ldots ,$ $(h_{52},\mathsf {PK}_{52}))$ and D as $(\mathsf {id}_1, \ldots , \mathsf {id}_{52})$. It returns the set H such that $\mathsf {id}_i \in H$ iff there exists $j \in [\![1,13 ]\!]$ such that $\mathsf {PK}_i = h_i^{\mathsf {sk}_j}$.

• $\mathsf {Play}(n,\mathsf {id},\mathsf {sk},\mathsf {pk},\mathrm {st},\mathsf {PK},D)$: It parses D as $(\mathsf {id}_1, \ldots , \mathsf {id}_{52})$, $\mathsf {sk}$ as $(\mathsf {sk}_1, \ldots , \mathsf {sk}_{13})$, $\mathsf {pk}$ as $(\mathsf {pk}_1, \ldots ,\mathsf {pk}_{13}))$, $\mathsf {PK}$ as $((h_1,\mathsf {PK}_1), \ldots , (h_{52},\mathsf {PK}_{52}))$, and $\mathrm {st}$ as $(\alpha , \mathsf {suit},U_1,$ $U_2,U_3,U_4)$. If $\mathrm {st}= \perp$ it sets four empty sets $U_1$, $U_2$, $U_3$ and $U_4$. Let $v\in [\![1,52 ]\!]$ be the integer such that $\mathsf {id}=\mathsf {id}_v$ (i.e.,  v is the index of the played card $\mathsf {id}$) and $t\in [\![1, 13 ]\!]$ be the integer such that $\log _g(\mathsf {pk}_t) = \log _{h_v}(\mathsf {PK}_v)$ (i.e.,  t is the index of the public key that corresponds to the played card $\mathsf {id}$). It sets $U'_n= U_n \cup \{t\}$. Note that at each step of the game, the set $U_n$ contains the indexes of all the public keys of the user n that have already been used to play a card. For all $i\in [\![1, 4 ]\!]\backslash \left\{ n \right\}$, it sets $U'_i = U_i$.

  If $\alpha = 4$ or $\mathrm {st}= \perp$ then it sets $\alpha ' = 1$ and $\mathsf {suit}' = \mathsf {id}\textsf {.}\mathsf {suit}$. Else it sets $\alpha ' = \alpha + 1$ and $\mathsf {suit}' =\mathsf {suit}$. The index $\alpha$ states how many players have already played this round, so if $\alpha =4$, players start a new round. Moreover, $\mathsf {suit}$ states which suit is the leading suit of the round, given by the first card played in the round. This algorithm sets $\mathrm {st}'= (\alpha ', \mathsf {suit}', U'_1, U'_2 ,U'_3 ,U'_4)$. It generates $\varPi _0 = \mathsf {ZK}\{(\mathsf {sk}_t) : \mathsf {pk}_t=g^{\mathsf {sk}_t} \wedge \mathsf {PK}_v = h_v ^ {\mathsf {sk}_t} \}$, which proves that the played card $\mathsf {id}_v$ matches one of the secret keys of the player. Let $L\in [\![1, 52 ]\!]$ be a set such that for all $l\in L$, $\mathsf {suit}'\not = \mathsf {id}_l\textsf {.}\mathsf {suit}$, i.e.,  L is the set of the indexes of the cards that are not of the leading suit this round. For all $j \in [\![1, 13 ]\!]$

  • If $\mathsf {suit}' = \mathsf {id}\textsf {.}\mathsf {suit}$, it sets $\varPi _j\,=\,\perp$ (if the card $\mathsf {id}$ is of the leading suit, then the player can play it in any case, so no additional proof is required).

  • If $j\in U_n$, it sets $\varPi _j\,=\,\perp$ (We omit the keys that have already been used in the previous rounds).

  • If $j\not \in U_n$ it generates $\varPi _j =\mathsf {ZK}\left\{ (\mathsf {sk}_j) : \bigvee _{l\in L} (\mathsf {pk}_j=g^{\mathsf {sk}_j} \wedge \mathsf {PK}_l = h_l ^ {\mathsf {sk}_j}) \right\}$. This proof ensures that the card that corresponds to each public key $\mathsf {pk}_j$ is not of the leading suit, which proves that the player n cannot play a card of the leading suit.

  Finally, it returns the proof $\varPi =(t,\varPi _0, \ldots ,\varPi _{13})$, and the updated value $\mathrm {st}'$.

• $\mathsf {Verif}(n,\mathsf {id},\varPi ,\mathsf {pk}, \mathrm {st}, \mathrm {st}', \mathsf {PK},D)$: It parses $\mathrm {st}$ as $(\alpha , \mathsf {suit},U_1,U_2,U_3,U_4)$, $\mathrm {st}'$ as $(\alpha ',$ $\mathsf {suit}',$ $U'_1,U'_2,U'_3,U'_4)$, $\mathsf {pk}$ as $(\mathsf {pk}_1, \ldots ,$ $\mathsf {pk}_{13})$, the key $\mathsf {PK}$ as $((h_1,\mathsf {PK}_1),$ $\ldots ,$ $(h_{52},\mathsf {PK}_{52}))$, D as $(\mathsf {id}_1, \ldots , \mathsf {id}_{52})$ and $\varPi$ as $(t, \varPi _0, \ldots , \varPi _{13})$. If $\mathrm {st}\,=\,\perp$, it sets four empty sets $U_1$, $U_2$, $U_3$ and $U_4$. Let v be the integer such that $\mathsf {id}_v=\mathsf {id}$ (i.e.,  v is the index of the played card $\mathsf {id}$). Let $L\in [\![1, 52 ]\!]$ be a set such that for all $l\in L$, $\mathsf {suit}'\not = \mathsf {id}_l\textsf {.}\mathsf {suit}$, i.e.,  L is the set of the indexes of the cards that are not of the leading suit. This algorithm first verifies that the state $\mathrm {st}$ is correctly updated in $\mathrm {st}'$ according to the $\mathsf {Play}$ algorithm:

  • If there exists $i \in [\![1,4 ]\!]\backslash \left\{ n\right\}$ such that $U'_i \not = U_i$, then it returns 0.

  • If $t \in U_n$ or $U_n\cup \{t\} \not =U'_n$, then it returns 0.

  • If $\alpha =4$ or $\mathrm {st}= \perp$, and $\alpha ' \not = 1$ or $\mathsf {suit}' \not = \mathsf {id}\textsf {.}\mathsf {suit}$, then it returns 0.

  • If $\alpha \not =4$ and $\mathsf {suit} \not = \perp$, and $\alpha ' \not = \alpha + 1$ or $\mathsf {suit}' \not =\mathsf {suit}$, then it returns 0.

  This algorithm then verifies the zero-knowledge proofs in order to check that the player does not cheat by playing a card he has not, or by playing a card that is not of the leading suit even though he could play a card of the leading suit.

  • If ${\varPi _0}$ is not valid then it returns 0.

  • If $\mathsf {suit}'\not = \mathsf {id}\textsf {.}\mathsf {suit}$ and there exists an integer $j \in [\![1 , n ]\!]$ such that $j\not \in U_n$ and ${\varPi _j}$ is not valid then it returns 0.

  If none of the previous checks fails, then this algorithm returns 1.

• $\mathsf {GetSuit}(\mathrm {st})$: It parses $\mathrm {st}$ as $( \alpha , \mathsf {suit}, U_1, U_2, U_3, U_4)$ and returns $\mathsf {suit}$.

Instantiation. We show how to instantiate the two zero-knowledge proofs of knowledge used in our protocol. The first one is a zero-knowledge OR-proof of the equality of two discrete logarithms denoted $\mathsf {ZK}\left\{ (w) : \bigvee _{i=1}^{n} {a_i}^w =c_i \wedge {b_i}^w=d_i \right\}$. An efficient instantiation of such ZKPs in the random oracle model is given in [5]. Our protocol also uses a proof of correctness of a randomization of a set of shuffled commitments. This proof is denoted $\mathsf {ZK}\{ ((r_1, \ldots ,r_n),\delta ) : \bigwedge _{i=1}^{n} c_{i}=a_{\delta (i)}^{r_{{i}}} \wedge d_{{i}} = b_{\delta (i)} ^ {r_{{i}}} \}$, and can be instantiated using the previous one, since it consists in proving the equality of two discrete logarithms for the statement $\left\{ (a_i,b_i,c_j,d_j)\right\} _{1\le j \le n}$ for each j in $[\![1,52 ]\!]$.

Security. We prove the security of our scheme in Theorem 1, then we give the intuition of the proof. The full proof is given in the full version of this paper [6].

Theorem 1

If the two proofs of knowledge are sound, extractable and zero-knowledge, then SecureSpades is theft-resistant, cheating-resistant, hand-private, unpredictable, and game-private under the DDH assumption in the ROM.

• Theft-resistant. To play a card, the player i must prove that the discrete logarithm of one of his public keys $\mathsf {pk}_{i,j}$ is equal to the discrete logarithm of the key $\mathsf {PK}_l$ that corresponds to the card. If the card is not in his hand, then none of the discrete logarithms of the public keys $\mathsf {pk}_{i,j}$ is equal to the discrete logarithm of the key $\mathsf {PK}_l$. Hence, to play a card that is not in his hand, the player should forge a proof of a false statement, which is not possible, since the proof system is sound.

• Cheating-resistant. To play a card that is not of the leading suit, the player i must prove that the discrete logarithm of each public key $\mathsf {pk}_{i,j}$ is equal to the discrete logarithm of one key $\mathsf {PK}_l$ that corresponds to a card that is not of the leading suit. Hence, assuming that the player has some cards of the leading suit, in order to play another card, he should forge a proof of a false statement. This is not possible, since the proof system is sound.

• Unpredictable. Since the deck D is chosen at random thanks to the protocol $\mathsf {RandGen}$, players have no way of guessing which card matches which public key during the keys generation phase.

• Hand-private. Each player shuffles the keys $\mathsf {PK}_l$ using a secret permutation when he runs the $\mathsf {GKeyRound}$ algorithm. Moreover, the zero-knowledge proofs ensure that for each $\mathsf {PK}_l$ there exists a key $\mathsf {pk}_{i,j}$ such that $\log _{h_l}(\mathsf {PK}_l) = \log _{g}(\mathsf {pk}_{i,j})$. Guessing the hand of a player i is equivalent to guessing pairs (j, l) such that the key $\mathsf {PK}_l$ has the same discrete logarithm in basis $h_l$ as the key $\mathsf {pk}_{i,j}$, which is equivalent to guessing whether $\mathsf {PK}_l$ is the Diffie-Hellman of $h_l$ and $\mathsf {pk}_{i,j}$.

• Game-private. During the game, the players use nothing other than zero-knowledge proofs, which leak nothing about the secret values of the players.

Other TTGs. Our Spades security model and scheme can be generalized to several trick-taking games. It works for any number of cards, of players, and for any team configuration. Moreover, it can be generalized to any game where players must play some kinds of cards according to a priority order, as long as the players can establish the set of all the cards that should be played (when it is possible) instead of the played one. This includes (but is not restricted to) all variants of Spades, Whist, Bridge, Belotte, Napoleon or Boston. Moreover, physical cards limit trick-taking games to games where players reveal all their cards, because if they do not, cheating could not be detected, even later. Our protocol allows the creation of new fair TTGs where players do not play all the cards of their hand.

8 Conclusion

In this paper, we have designed a secure protocol for trick-taking games. We used Spades, a famous online gambling card game, to illustrate our approach. Until now, such games required a trusted sever that ensures that players are not cheating. Our protocol allows the players to manage the game and detect cheating by themselves, without leaking any information about the hidden cards. Hence, a player cannot play a card that he does not have or that does not follow the rule of the game. Our construction is based on the discrete logarithm assumption and zero knowledge proofs. We proposed a security model and prove the security of our protocol.

In the future, we would like to implement a prototype, in order to evaluate the practical efficiency of our solution. Moreover, we would like to add secure payment distributions mechanism to our protocol. Another perspective is to try to generalize this approach to other games.