Abstract Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”
Abstract Card-based cryptography, introduced by den Boer aims to realize multiparty computation (MPC) by using physical cards. We propose several efficient card-based protocols for the millionaires’ problem by introducing a new operation called Private Permutation (PP) instead of the shuffle used in most of existing card-based cryptography. Shuffle is a useful randomization technique by exploiting the property of card shuffling, but it requires a strong assumption from the viewpoint of arithmetic MPC because shuffle assumes that public randomization is possible. On the other hand, private randomness can be used in PPs, which enables us to design card-based protocols taking ideas of arithmetic MPCs into account. Actually, we show that Yao’s millionaires’ protocol can be easily transformed into a card-based protocol by using PPs, which is not straightforward by using shuffles because Yao’s protocol uses private randomness. Furthermore, we propose entirely novel and efficient card-based millionaire protocols based on PPs by securely updating bitwise comparisons between two numbers, which unveil a power of PPs. As another interest of these protocols, we point out they have a deep connection to the well-known logical puzzle known as “The fork in the road.”
This paper proposes new efficient card-based cryptographic protocols for the millionaires' problem using private input operations. The millionaires' problem is one of the fundamental problems in cryptography. Two players, Alice and Bob, want to know which of them is richer without revealing their actual amount of asset. Many cryptographic protocols were proposed to solve the problem. Card-based cryptographic protocols were proposed to execute cryptographic protocols using physical cards instead of computers. Though some card-based cryptographic protocols for the millionaires' problem were proposed, most of them use many cards whose number depends on the size of the amount of asset. Though Nakai et al. implicitly proposed a new protocol that uses a constant number of cards using private input operations, their protocol is not efficient since the number of rounds is 2n+1, where n is the maximum number of bits of the asset. This paper shows new card-based protocols whose number of rounds is n+1. Another important feature of the proposed protocols is no-open property. No cards are opened until the end of the protocol.
Abstract Card-based cryptography is a variety of secure multiparty computation (MPC). Recently, a new technique called private operations was introduced because the protocol can be implemented with fewer cards than that by using the conventional technique called the shuffle. For example, Nakai et al. showed that if the private operations are available, secure computations of AND and OR operations for two inputs can be realized simultaneously by using four cards, and the protocol is applied to a four-card majority voting protocol with three inputs. This paper shows that only three cards are sufficient to construct a majority voting protocol with three inputs. Specifically, we propose two constructions of three-input majority voting protocols. One is a protocol assuming that players can announce their output, and the other is not allowed. Compared to Nakai et al.’s protocol, the protocol with the announcement is realized without any additional private operations and communications. On the other hand, the second construction requires two more private operations and communications because it removes the assumption on the announcement from the first construction. More importantly, the idea of the second protocol can be extended to an n-input majority voting protocol with n cards, which is the main result of this paper.
Abstract Card-based cryptography is a variant of multi-party computation using physical cards like playing cards. There are two models on card-based cryptography, called public and private models. The public model assumes that all operations are executed publicly, while the private model allows the players private operations called private permutations (PP, for short). Much of the existing card-based protocols were developed under the public model. Under the public model, 2ncards are necessary for every protocol withn-bit input since at least two cards are required to express a bit. In this paper, we proposen-bit input protocols with fewer than 2ncards by utilizing PP, which shows the power of PP. In particular, we show that a protocol for (n-bit input) threshold function can be realized with only n+1 n+1 cards by reducing the threshold function to the majority voting. Toward this end, we first offer that two-bit input protocols for logic gates can be realized with fewer than four cards. Furthermore, we construct a new protocol for three-input majority voting with only four cards by observing the relationship between AND/OR operations. This protocol can be easily extended to more participants, and to the protocol for threshold functions.
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.
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 aims to realize secure multiparty computation with physical cards. This paper is the first to address Private Set Intersection (PSI) and Private Set Union (PSU) in card-based cryptography. PSI and PSU are well-studied secure computation protocols to compute the set intersection and the set union, respectively. We show two-party PSI and PSU protocols in each of the two operation models: one is the shuffle-based model in which parties perform all operations publicly, and the other is the private-permutation-based model that allows parties to perform some operations privately. In the shuffle-based model, we show PSI and PSU protocols can be realized with existing secure AND and OR protocols, respectively. However, these protocols have an issue of increasing the number of shuffles depending on the size of the universal set. To resolve the issue, we further propose PSI and PSU protocols with only one shuffle at the cost of increasing the number of cards. In the private-permutation-based model, we show PSI and PSU protocols can be achieved with existing secure AND and OR protocols, respectively, as in the shuffle-based protocols. These protocols have an advantage of requiring only one private permutation and one communication. We further show that the number of cards of these protocols can be reduced at the cost of increasing the number of private permutations and communications.