Card-based cryptography uses physical playing cards to construct protocols for secure multi-party computation. Existing card-based protocols employ various types of shuffles, some of which are easy to implement in practice while others are considerably more complex. In this paper, we classify shuffle operations into several levels according to their implementation complexity. We motivate this hierarchy from both practical and theoretical perspectives, and prove separation results between several levels by showing that certain shuffles cannot be realized using only operations from lower levels. Finally, we propose a new complexity measure for evaluating card-based protocols based on this hierarchy.
Card-based cryptography uses physical playing cards to construct protocols for secure multi-party computation. Existing card-based protocols employ various types of shuffles, some of which are easy to implement in practice while others are considerably more complex. In this paper, we classify shuffle operations into several levels according to their implementation complexity. We motivate this hierarchy from both practical and theoretical perspectives, and prove separation results between several levels by showing that certain shuffles cannot be realized using only operations from lower levels. Finally, we propose a new complexity measure for evaluating card-based protocols based on this hierarchy.
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.
Card-based cryptographic protocols provide secure multi-party computation using a deck of physical cards. The most important primitive of those protocols is the shuffling operation, and most known protocols rely on uniform shuffles (such as the random cut and random bisection cut) in which each possible outcome is equally likely. However, several protocols with non-uniform shuffles have recently been proposed by Koch et al. Compared to other protocols, their protocols require fewer cards to securely produce a hidden AND value, although implementation of the non-uniform shuffle appearing in their protocols remains an open problem. This paper presents a secure implementation of their non-uniform shuffle. To implement the shuffle, we utilize physical cases that can store piles of cards, such as boxes and envelopes. Therefore, humans are able to perform the non-uniform shuffle using these everyday objects.
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.
Secure computation is a cryptographic primitive that enables mutually distrustful parties to jointly realize a possibly randomized functionality in a secure manner. Card-based secure computation studies the problem of implementing secure computation protocols visually by using physical cards, to help non-experts understand their mechanisms. Although many card-based secure computation protocols have been proposed, most of them focus on deterministic functionalities and only a few protocols for randomized functionalities are tailored to specific applications. In this work, we initiate the study of card-based protocols for generating uniformly random bits, which is the most fundamental randomized functionality in secure computation. We present four constructions of such protocols differing in the types of shuffles they use. We also show a lower-bound result that the number of shuffles required for protocols using complete shuffles must be at least the number of output bits. Furthermore, we demonstrate that our protocols for generating uniformly random bits can be extended to those for generating possibly non-uniform random numbers, when combined with existing card-based protocols for computing deterministic functions.
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.
Cryptographic protocols enable participating parties to compute any function of their inputs without leaking any information beyond the output. A card-based protocol is a cryptographic protocol implemented by physical cards. In this paper, for constructing protocols with small numbers of shuffles, we introduce a new type of cards, regular polygon cards, and a new protocol, oblivious conversion. Using our cards, we construct an addition protocol on non-binary inputs with only one shuffle and two cards. Furthermore, using our oblivious conversion protocol, we construct the first protocol for general functions in which the number of shuffles is linear in the number of inputs.