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.
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.
Abstract Card-based cryptography is a secure computation protocol realized by using physical cards. There are two models on card-based cryptography: public and private models. We adopt private one that allows players to handle cards privately. While much of the existing works for card-based cryptography use two-colored cards, it is also a vital task to construct an efficient protocol with playing cards. In the public model, 2n cards are necessary for any n-bit input protocol since at least two cards are required to express a Boolean value. It holds true for both two-colored and playing-card settings. On the other hand, the private model enables us to construct a protocol with fewer than 2n cards. However, all existing protocols that achieve such properties are only in the two-colored setting. This paper shows that the private model enables us to construct a protocol with fewer than 2n cards using the playing cards. We first show two-bit input protocols with fewer than four cards for logical operations, AND, OR, and XOR. Furthermore, we show a three-input majority voting protocol using only three cards, which is constructed by combining our AND and OR protocols. Notably, our proposed protocols require no randomness. All operations are deterministic and depend only on players’ private inputs.
Card-based cryptography, as first proposed by den Boer [den Boer, 1989], enables secure multiparty computation using only a deck of playing cards. Many protocols as of yet come with an “honest-but-curious” disclaimer. However, modern cryptography aims to provide security also in the presence of active attackers that deviate from the protocol description. In the few places where authors argue for the active security of their protocols, this is done ad-hoc and restricted to the concrete operations needed, often using additional physical tools, such as envelopes or sliding cover boxes. This paper provides the first systematic approach to active security in card-based protocols. The main technical contribution concerns shuffling operations. A shuffle randomly permutes the cards according to a well-defined distribution but hides the chosen permutation from the players. We show how the large and natural class of uniform closed shuffles, which are shuffles that select a permutation uniformly at random from a permutation group, can be implemented using only a linear number of helping cards. This ensures that any protocol in the model of Mizuki and Shizuya [Mizuki and Shizuya, 2014] can be realized in an actively secure fashion, as long as it is secure in this abstract model and restricted to uniform closed shuffles. Uniform closed shuffles are already sufficient for securely computing any circuit [Mizuki and Sone, 2009]. In the process, we develop a more concrete model for card-based cryptographic protocols with two players, which we believe to be of independent interest.
Consider a group of people who want to know the “rich list” among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a “secure ranking computation,” which was first considered by Jiang and Gong (2006) [2]; they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute the protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range. To be precise, whereas our protocols make all players know the rich list, the Jiang–Gong scheme makes each player know his/her rank only; to achieve the same task (as the Jiang–Gong scheme) using a deck of cards is an intriguing open problem.
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.
Abstract Old Maid is a popular card game. While typically played with three or more players, it is less enjoyable with only two people. To address this, we propose a protocol to create a virtual player, Carol, by making use of card-based cryptography when only two people, Alice and Bob, are available to play Old Maid. Specifically, we design a card-based protocol to remove any pair of cards having the same number in Carol’s hand (namely, the virtual player’s hand) without leaking any information about Carol’s hand (more than necessary); our protocol uses additional cards aside from playing cards that are used in Old Maid. Using our protocol, without any third human player, Alice and Bob can have fun with Old Maid!
A card-based secure computation protocol is a method for n parties to compute a function f on their private inputs (x1,…,xn) using physical playing cards, in such a way that the suits of revealed cards leak no information beyond the value of f(x1,…,xn). A \textit{single-shuffle full-open} protocol is a minimal model of card-based secure computation in which, after the parties place face-down cards representing their inputs, a single shuffle operation is performed and then all cards are opened to derive the output. Despite the simplicity of this model, the class of functions known to admit single-shuffle full-open protocols has been limited to a few small examples. In this work, we prove for the first time that every function admits a single-shuffle full-open protocol. We present two constructions that offer a trade-off between the number of cards and the complexity of the shuffle operation. These feasibility results are derived from a novel connection between single-shuffle full-open protocols and a cryptographic primitive known as \textit{Private Simultaneous Messages} protocols, which has rarely been studied in the context of card-based cryptography. We also present variants of single-shuffle protocols in which only a subset of cards are revealed. These protocols reduce the complexity of the shuffle operation compared to existing protocols in the same setting.