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.
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.
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.
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.
In this paper, we provide a probabilistic analysis of the confidentiality in a card-based protocol. We focus on Bert den Boer's original Five Card Trick to develop our approach. Five Card Trick was formulated as a secure two-party computation method, where two players use colored cards with identical backs to calculate the logical AND operation on the bits that they choose. In this method, the players first arrange the cards privately, and then shuffle them through a random cut. Finally, they reveal the shuffled arrangement to determine the result of the operation. An unbiased random cut is essential to prevent players from exposing their chosen bits to each other. However, players typically choose to move cards within the deck even though not moving any cards should be equally likely. This unconscious behavior results in a biased, nonuniform shuffling-distribution in the sense that some arrangements of cards are slightly more probable after the cut. Such a nonuniform distribution creates an opportunity for a malicious player to gain advantage in guessing the other player's choice. We provide the conditional probabilities of such guesses as a way to quantify the information leakage. Furthermore, we utilize the eigenstructure of a Markov chain to derive tight bounds on the number of times the biased random cuts must be repeated to reduce the leakage to an acceptable level. We also discuss the generalization of our approach to the setting where shuffling is conducted by a malicious player.
Abstract This paper shows new card-based cryptographic protocols using private operations that are secure against malicious players. Physical cards are used in card-based cryptographic protocols instead of computers. Operations that a player executes in a place where the other players cannot see are called private operations. Using several private operations, calculations of two variable Boolean functions and copy operations were realized with the minimum number of cards. Though private operations are very powerful in card-based cryptographic protocols, there is a problem that it is very hard to prevent malicious actions during private operations. Though most card-based protocols are discussed in the semi-honest model, there might be cases when the semi-honest model is not enough. Thus, this paper shows new protocols that are secure against malicious players. We show logical XOR, logical AND, n-variable Boolean function, and copy protocols. We can execute any logical computations with a combination of these protocols. We use envelopes as an additional tool that can be easily prepared and used by people.
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.
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.