Card-based cryptographic protocols provide secure multi-party computations using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most of the existing protocols rely on uniform cyclic shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely and all possible outcomes constitute a cyclic subgroup. However, a couple of protocols with non-uniform and/or non-cyclic shuffles were proposed by Koch, Walzer, and Härtel at Asiacrypt 2015. Compared to the previous protocols, their protocols require fewer cards to securely produce a hidden AND value, although to implement of such unconventional shuffles appearing in their protocols remains an open problem. This paper introduces “pile-shifting scramble,” which can be a secure implementation of those shuffles. To implement such unconventional shuffles, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the shuffles using these everyday objects. Furthermore, we show that a certain class of non-uniform and/or non-cyclic shuffles having two possible outcomes can be implemented by the pile-shifting scramble. This also implies that we can improve upon the known COPY protocol using three card cases so that the number of cases required can be reduced to two.

Card-based protocols enable us to easily perform cryptographic tasks such as secure multiparty computation using a deck of physical cards. Since the first card-based protocol appeared in 1989, many protocols have been designed. A protocol is usually described with a series of somewhat intuitive and verbal descriptions, such as “turn over this card,” “shuffle these two cards,” “apply a random cut to these five cards,” and so on. On the other hand, a formal computational model of card-based protocols via abstract machine was constructed in 2014. By virtue of the formalization, card-based protocols can be treated more rigorously; for example, it enables one to discuss the lower bounds on the number of cards required for secure computations. In this paper, an overview of the computational model with its applications to designing protocols and a survey of the recent progress in card-based protocols are presented.

Assume that Alice, Bob, and Carol, each of whom privately holds a one-bit input, want to learn the output of some Boolean function, say the majority function, of their inputs without revealing more of their own secret inputs than necessary. In this paper, we show that such a secure three-input function evaluation can be performed with a deck of real cards; specifically, the three players can learn only the output of the function using eight physical cards — four black and four red cards — with identical backs.

Most traditional board and card games, such as Chess, Chinese Chess, Go, Chinese Mahjong, Hearts, Bridge, etc., share the same playing model: Players play around tables using physical objects such as cards and may hold objects in their own private areas, e.g., players hold cards in their own hands in Bridge. In this paper, this model is called the play-on-table (POT) game model and these games following the model are called POT games. The research of this paper is summarized as follows. First, formalize the definition of the POT game model. Second, present some game systems to allow players to design and play new POT games. Third, prove that these game systems are general for all POT games. Finally, in order to demonstrate the theory, practically implement one of the general game systems that allows players to design and play new POT games in a what-you-see-is-what-you-get (WYSIWYG) manner.

We propose the problem of how to transmit an information-theoretically secure bit using random deals of cards among players in hierarchical groups and a computationally unlimited eavesdropper. A player in the highest group wants to send players in lower groups a secret bit which is secure from the eavesdropper and some other players. We formalize this problem and design protocols for constructing secret key exchange spanning trees on hierarchical groups. For each protocol we give sufficient conditions to successfully construct a secret key exchange spanning tree for the hand sizes of the players and the eavesdropper.