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.
Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: an
n-card
n-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.