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.
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.
This paper shows new card-based cryptographic protocols with the minimum number of rounds, using private operations under the semi-honest model. Physical cards are used in card-based cryptographic protocols instead of computers to achieve secure multiparty computation. Operations that a player executes in a place where the other players cannot see are called private operations. Using three private operations—private random bisection cuts, private reverse cuts, and private reveals—the calculations of two variable Boolean functions and copy operations were realized with the minimum number of cards. Though the number of cards has been discussed, the efficiency of these protocols has not been discussed. This paper defines the number of rounds to evaluate the efficiency of the protocols, using private operations. Most of the meaningful calculations using private operations need at least two rounds. This paper presents a new two-round committed-input, committed-output logical XOR protocol, using four cards. Then, we show new two-round committed-input, committed-output logical AND and copy protocols, using six cards. Even if private reveal operations are not used, logical XOR, logical AND, and copy operations can be executed with the minimum number of rounds. Protocols for general n-variable Boolean functions and protocols that preserve an input are also shown. Lastly, protocols with asymmetric cards are shown.
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 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.
Abstract This paper proposes new card-based cryptographic protocols to calculate logic functions with the minimum number of cards using private operations under the semi-honest model. Though various card-based cryptographic protocols were shown, the minimum number of cards used in the protocol has not been achieved yet for many problems. Operations executed by a player where the other players cannot see are called private operations. Private operations have been introduced in some protocols to solve a particular problem or to input private values. However, the effectiveness of introducing private operations to the calculation of general logic functions has not been considered. This paper introduces three new private operations: private random bisection cuts, private reverse cuts, and private reveals. With these three new operations, we show that all of AND, XOR, and copy protocols are achieved with the minimum number of cards by simple three-round protocols. This paper then shows a protocol to calculate any logical functions using these private operations. Next, we consider protocols with malicious players.
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.
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.