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 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.
Symmetric functions are an important class of functions that includes many interesting functions. Constructing efficient card-based protocols for symmetric functions is an important research topic in card-based cryptography. In 2020, Ruangwises and Itoh designed a protocol for symmetric functions f : {0, 1}n → R using 2n + 2 cards of a two-colored deck. Whether the number of cards in this protocol could be reduced is an open problem. In this paper, we design protocols for symmetric functions using 2n + 1 cards of a two-colored deck, which solve the above problem affirmatively. We also propose protocols for symmetric functions using 2n cards of a three-colored deck, while the existing 2n-card protocol requires a four-colored deck. By further restricting the class of functions to {0}-partially doubly symmetric functions, we can construct even more efficient protocols. In particular, we construct protocols for {0}-partially doubly symmetric functions using 2n cards of a two-colored deck, while the existing protocol requires 2n + 1 cards.
In card-based cryptography, which uses a physical deck of cards to realize secure multiparty computations, a one-bit value is usually encoded by a pair of cards. Thus, when performing a secure computation of an n-input Boolean function, a sequence of 2n cards representing n bits is needed for input, and some helping cards are typically added to form a protocol. In 2020, Ruangwises and Itoh constructed a card-based protocol for a symmetric Boolean function with an arbitrary range using two helping cards. (Note that a symmetric Boolean function depends only on the number of 1s in its input). At the same time, they showed that the helping cards can be eliminated if the target function is limited to “doubly symmetric” Boolean functions (also known as symmetric self-anti-dual functions). A doubly symmetric Boolean function satisfies the following for all k: when inputting exactly a number k of 1s, the output is the same as the output when inputting exactly a number n − k of 1s. In this paper, we loosen the restriction on doubly symmetric Boolean functions by fixing k = 0, and construct new protocols which require less than two helping cards for that wider class of symmetric Boolean functions. Specifically, we design a one-helping-card protocol for any n > 4, and helping-card-free protocols for n = 3 and n = 4.
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 Card-based cryptography allows us to securely compute arbitrary functions using a deck of physical cards. Its performance is mainly measured by the number of used cards and shuffles, and there is a line of work that aims to reduce either of them. One seminal work is the card-based garbled circuit technique by Shinagawa and Nuida (Discret Appl Math 289:248–261, 2021, https://doi.org/10.1016/j.dam.2020.10.013 ), which allows the construction of a card-based protocol for any Boolean function with a single shuffle. Their construction requires 2n+24g 2 n + 24 g cards for an n-input Boolean function that is represented by g logical gates. In this paper, we reduce the number of cards to 2n+8g 2 n + 8 g for arbitrary functions while keeping it working with only one shuffle. In addition, we propose two types of extensions to support numerical encoding and multi-input gates. In the extended scheme, the free-ADD technique, obtained by generalizing the free-XOR technique by Manabe and Shinagawa (Deng J, Kolesnikov V, Schwarzmann AA (eds) CANS 2023, LNCS, vol 14342. Springer, Singapore, pp 232–248, 2023, https://doi.org/10.1007/978-981-99-7563-1-11 ), is available. The free-ADD technique allows our scheme to evaluate any n-input symmetric Boolean function using 2n2+6n+2 2 n 2 + 6 n + 2 cards.
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 card-based cryptography, a commitment to a Boolean value is usually represented by two face-down cards of different colors or numbers, whose order specifies the one-bit value (namely, 0 or 1). One of the most important primitives in card-based cryptography is a "copy protocol," which is supposed to make two identical copies of a given commitment. In the literature, there are several copy protocols, which can be categorized by kinds of shuffles they use; this paper focuses on those using only the so-called random cut, which is the simplest shuffle, and we propose two copy protocols that are more efficient than the existing ones. Specifically, we first work on a standard deck of cards and design a six-card copy protocol using three random cuts (on average). Since the previous protocol needs 5.5 random cuts, our protocol improves upon it. Next, we shift our attention to the case of a two-colored deck of cards, and construct a six-card copy protocol using three random cuts (on average). Because the previous protocol requires eight cards, our protocol uses two cards fewer than the previous one (although it uses one more shuffle). In addition, going back to the standard-deck setting, we provide a four-card XOR protocol using only one random cut for the first time.