Card-based cryptography studies the problem of representing the functionality and security of cryptographic primitives visually by using physical cards, to demonstrate their security properties for those who are unfamiliar with cryptography. In this study, we propose efficient card-based protocols for secure computation of the four basic arithmetic operations (addition, subtraction, multiplication, and division). Existing protocols for securely performing these operations on ℓ-bit integers either require an exponential number of card manipulations in ℓ or need Ω (ℓ) additional cards. The proposed protocols simultaneously resolves these drawbacks for the first time by achieving a polynomial number of card manipulations in ℓ while requiring only a constant number of additional cards. The construction of our protocols is based on the long-hand algorithms for each of the four arithmetic operations. The technical novelty lies in demonstrating that the number of additional cards can be kept constant by freeing the cards representing intermediate values that are no longer needed during the process.
Card-based cryptography studies the problem of representing the functionality and security of cryptographic primitives visually by using physical cards, to demonstrate their security properties for those who are unfamiliar with cryptography. In this study, we propose efficient card-based protocols for secure computation of the four basic arithmetic operations (addition, subtraction, multiplication, and division). Existing protocols for securely performing these operations on ℓ-bit integers either require an exponential number of card manipulations in ℓ or need Ω (ℓ) additional cards. The proposed protocols simultaneously resolves these drawbacks for the first time by achieving a polynomial number of card manipulations in ℓ while requiring only a constant number of additional cards. The construction of our protocols is based on the long-hand algorithms for each of the four arithmetic operations. The technical novelty lies in demonstrating that the number of additional cards can be kept constant by freeing the cards representing intermediate values that are no longer needed during the process.
Card-based cryptography enables players to compute logical and arithmetic operations securely, such as bitwise AND and addition of integers. Several multiparty computation protocols and zero-knowledge proof protocols utilizing these secure computations have been developed as its applications. However, the realization of an efficient protocol for an arithmetic operation other than addition and subtraction remains an open problem. This paper proposes card-based protocols, based on integer commitment, for multiplication, division, and square root. Compared to general constructions for protocols for these operations based on binary integer commitment, the proposed protocols exhibit superior simplicity and efficiency. Furthermore, these protocols introduce novel applications for card-based cryptography to secure statistical data aggregation.
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.
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 cryptography is an area involving cryptographic techniques that use a deck of physical cards to implement secure computation. In this paper, we study card-based cryptographic protocols for symmetric functions f: {0, 1}n → R, where R is an arbitrary finite set. Any symmetric Boolean function has the property that its output value is determined only by the sum of input bits, and the class of them includes many interesting functions such as the AND and equality functions. In 2020, Ruangwises and Itoh proposed a protocol which uses 2n + 2 cards to securely compute any symmetric function f: {0, 1}n → R; reducing the number of cards to less than 2n + 2 was left as an open problem. While the Ruangwises–Itoh protocol uses a two-colored deck of cards, this paper considers using three-colored and four-colored decks: to give a partial answer to the open problem, we propose three protocols for symmetric functions using 2n + 1 cards or less. Specifically, we first propose a protocol using 2n + 1 cards from a three-colored deck. We then propose two protocols using 2n cards from a four-colored deck; one is a simpler protocol and the other is a more shuffle-efficient protocol.
Card-based cryptography enables the execution of cryptographic protocols such as secure multiparty computation, by using a deck of physical cards. To facilitate statistical analysis with card-based cryptography, we have previously presented protocols for integer-based arithmetic operations. These protocols utilize integer commitments, which are face-down card sequences encoding integers, and consist of simple operations. However, in statistical applications, they suffer from poor scalability, as the required number of cards increases significantly as the number of data points increases. To address this issue, this paper introduces a new representation of commitments, named floating-point number (FPN) commitments, which are face-down card sequences encoding floating-point numbers. These FPN commitments allow us to represent a wide range of numbers, including negative and arbitrary-precision values, with fewer cards. We then propose protocols for converting a conventional integer commitment to an FPN commitment and for performing arithmetic operations using FPN commitments. We also demonstrate that our new representation and protocols enhance the applicability of card-based cryptography to statistical processing.
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.