Secure Trick-Taking Game Protocols How to Play Online Spades with Cheaters

Xavier Bultel, Pascal Lafourcade

Published Feb 18, 2019• 0 citations

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.

Related papers

Actively revealing card attack on card-based protocols

Ken Takashima, Daiki Miyahara, Takaaki Mizuki +1 more

Abstract In 1989, den Boer presented the first card-based protocol, called the “five-card trick,” that securely computes the AND function using a deck of physical cards via a series of actions such as shuffling and turning over cards. This protocol enables a couple to confirm their mutual love without revealing their individual feelings. During such a secure computation protocol, it is important to keep any information about the inputs secret. Almost all existing card-based protocols are secure under the assumption that all players participating in a protocol are semi-honest or covert, i.e., they do not deviate from the protocol if there is a chance that they will be caught when cheating. In this paper, we consider a more malicious attack in which a player as an active adversary can reveal cards illegally without any hesitation. Against such an actively revealing card attack, we define the t-secureness, meaning that no information about the inputs leaks even if at most t cards are revealed illegally. We then actually design t-secure AND protocols. Thus, our contribution is the construction of the first formal framework to handle actively revealing card attacks as well as their countermeasures.

Natural ComputingFeb 13, 20219 citations

Secure Computations Through Checking Suits of Playing Cards

Daiki Miyahara, Takaaki Mizuki

Abstract Card-based cryptography started with the “five-card trick” designed by Den Boer (EUROCRYPT 1989); it enables Alice and Bob to securely evaluate the AND value of their private bits using a physical deck of five cards. It was then shown that the same task can be done with only four cards, i.e., Mizuki et al. proposed a four-card AND protocol (ASIACRYPT 2012). These two AND protocols are simple and easy even for non-experts, such as high school students, to execute. Their only common drawback is the need to prepare a customized deck consisting of red and black cards such that all cards of the same color must be identical. Fortunately, several existing protocols are based on a standard deck of playing cards (commercially available). Among them, the state-of-the-art AND protocol was constructed by Koch et al. (ASIACRYPT 2019); it uses four playing cards (such as ‘A, J, Q, K’) to securely evaluate the AND value. The protocol is elaborate, while its possible drawback is the need to repeat a shuffling operation six times (in expectation), which makes it less practical. This paper aims to provide the first practical protocol working on a standard deck of playing cards. We present an extremely simple AND protocol that terminates after only one shuffle using only four cards; our proposed protocol relies on a new operation, called the “half-open” action, whereby players can check only the suit of a face-down card without revealing the number on it. We believe that this new operation is easy-to-implement, and hence, our four-card AND protocol working on a standard deck is practical. We formalize the half-open action to present a formal description of our proposed protocol. Moreover, we discuss what is theoretically implied by introducing the half-open action and show that it can be applied to efficiently solving Yao’s Millionaires’ problem with a standard deck of cards.

Lecture notes in computer scienceJan 1, 202214 citations

Fair online gambling scheme and TTP-free mental poker protocols

Weiliang Zhao, Vijay Varadharajan

Online gambling allows users to participate in mental games and bet over the Internet. It can open new opportunities for casinos to make more money; however, at the same time, there are a lot of security challenges. In this paper, we describe our scheme for secure online gambling and secure mental poker protocols over the Internet based on our previous researches. Our scheme provides both the fairness of online gambling processes and secure linking of the online gambling with payment. A unique link between payments and gambling outcome is provided so that the winner can be ensured to get the payment. The gambling games are generic in our fair online gambling scheme. Mental poker is one of most popular games of online gambling. In this paper, efficient and secure mental poker protocols are provided. These mental poker protocols are based on multiple encryption and decryption of individual cards. These protocols satisfy all major security requirements of a real mental poker. The card salesman has been got rid of and the minimal effect due to collusion has been guaranteed. These protocols are more efficient compared with other known protocols. The strategies of players can be kept confidential with the introduction of a dealer. These mental poker protocols are suitable for implementation in an online card game.

Information Assurance and SecurityJan 1, 20060 citations

Card-Based Computation in the Virtual Player Simulation Model

Suthee Ruangwises

Player simulation has recently emerged as a new direction in card-based cryptography, with protocols developed for simulating virtual players in physical card games such as Old Maid, UNO, and President. Unlike conventional card-based secure computation, player simulation imposes additional constraints: the cards represent a persistent game state, the remaining cards in a virtual player's hand must be preserved after each action, and it is desirable to represent each card in the game by a single physical card. In this paper, we study generic card-based computation in the virtual player simulation model. We focus on games whose cards admit a publicly known ranking and propose two fundamental protocols. First, we present the Play-Minimum protocol, which securely selects and plays the minimum-value card from a virtual player's hand when all cards in the deck have distinct values. By symmetry, the protocol can also be used to play the maximum-value card. Second, we present the Sorting protocol, which securely arranges a virtual player's hand in nondecreasing order and remains applicable when multiple cards have the same value. These protocols provide generic computational primitives independent of any particular card game and constitute a step toward understanding the computational capabilities of the virtual player simulation model.

arXiv:2609.02716Sep 2, 20260 citations

A Toolbox for Mental Card Games

Christian Schindelhauer

Mental card games are played without a trusted party and without cards. It is well known that the problem of mental card games can be solved in principle. But the schemes known so far are too messy to be used in practice. Only for the mental poker game a suitable solution is known [Cr'ep 87] that achieves security against player coalition and complete confidentiality of a player's strategy. Here, we present a general-purpose scheme that may be used as basic toolbox for straight-forward implementations of card games. We present a data structure for cards and decks that is secure against player coalitions and enables standard operations like picking up a card, opening it, and (re-)mixing stacks. Futhermore, we introduce tools for special operations like inserting a card into the deck, splitting the deck, parting the game. The correctness of all operations is testified by zeroknowledge proofs. Finally, we discuss security problems that are typical for mental card games and suggest solutio...

Jan 1, 19982 citations

Cryptographic cryptid protocols: How to play cryptid with cheaters

Xavier Bultel, Charlène Jojon, Pascal Lafourcade

Cryptid is a board game in which the goal is to be the firstplayer to locate the cryptid, a legendary creature, on a map. Each playerknows a secret clue as to which cell on the map contains the cryptid.Players take it in turns to ask each other if the cryptid could be on agiven cell according to their clue, until one of them guesses the cryptidcell. This game is great fun, but completely loses its interest if one of theplayers cheats by answering the questions incorrectly. For example, if aplayer answers negatively on the cryptid cell, the game continues for along time until all the cells have been tested, and ends without a winner.We provide cryptographic protocols to prevent cheating in Cryptid. Themain idea is to use encryption to commit the players’ clues, enabling themto show that they are answering correctly in accordance with their clueusing zero-knowledge proofs. We give a security model which capturessoundness (a player cannot cheat) and confidentiality (the protocol doesnot leak more information than the players’ answers about their clues),and prove the security of our protocols in this model. We also analyzethe practical efficiency of our protocols, based on an implementation ofthe main algorithms in Rust. Finally, we extend our protocols to ensurethat the game designer has correctly constructed the cryptid games, i.e.,that the clues are well formed and converge on at least one cell.

Sep 24, 20240 citations