Abstract Card-based protocols perform secure computation using physical playing cards, and their efficiency is primarily evaluated by two metrics: the number of cards and the number of shuffles. In this paper, we present three new card-based protocols that reduce the number of cards. The first protocol supports any Boolean circuit and decreases the number of cards. The second protocol extends the first to a committed-format version, while the third is specialized for Boolean circuits without a branched input, achieving an even smaller number of cards. All the proposed protocols are based on Yao’s garbled-circuit framework, similar to previous single-shuffle card-based protocols. Our main contribution is a novel encoding method that represents the truth table of each Boolean gate with fewer cards than existing schemes. Consequently, our protocols require only six cards per gate in a single-shuffle execution, providing a significant improvement in efficiency over prior work. Furthermore, by incorporating the card-based free-XOR introduced by Manabe–Shinagawa, we can further reduce the number of cards in certain configurations.
Abstract Card-based protocols perform secure computation using physical playing cards, and their efficiency is primarily evaluated by two metrics: the number of cards and the number of shuffles. In this paper, we present three new card-based protocols that reduce the number of cards. The first protocol supports any Boolean circuit and decreases the number of cards. The second protocol extends the first to a committed-format version, while the third is specialized for Boolean circuits without a branched input, achieving an even smaller number of cards. All the proposed protocols are based on Yao’s garbled-circuit framework, similar to previous single-shuffle card-based protocols. Our main contribution is a novel encoding method that represents the truth table of each Boolean gate with fewer cards than existing schemes. Consequently, our protocols require only six cards per gate in a single-shuffle execution, providing a significant improvement in efficiency over prior work. Furthermore, by incorporating the card-based free-XOR introduced by Manabe–Shinagawa, we can further reduce the number of cards in certain configurations.
In card-based cryptography, the numbers of cards and shuffles are the complexity measures of protocols for secure computations, and the smaller these values are, the better. As the state-of-the-art study to minimize the latter measure, Shinagawa and Nuida showed a surprising result that any n-input logical function can be securely computed with only one shuffle, based on the idea of Yao's garbled circuit. When executing their protocol, the number of required cards is 2n+24q, where the n-input logical function to be computed is represented by q gates. For example, when applied to the n-input AND and XOR functions, the number of gates is n-1, and hence, 26n-24 cards are required. In this paper, we show that the number of required cards can be reduced by focusing on these two specific functions. Specifically, we construct a single-shuffle protocol for the n-input AND function using 4n-2 cards, and construct a single-shuffle protocol for the n-input XOR function using 2n cards.
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.
Secure computation enables a number of players each holding a secret input value to compute a function of the inputs without revealing the inputs. It is known that secure computation is possible physically when the inputs are given as a sequence of physical cards. This research area is called card-based cryptography. One of the important problems in card-based cryptography is to minimize the number of cards and shuffles, where a shuffle is the most important (and somewhat heavy) operation in card-based protocols. In this paper, we determine the minimum number of shuffles for achieving general secure computation. Somewhat surprisingly, the answer is just one, i.e., we design a protocol which securely computes any Boolean circuit with only a single shuffle. The number of cards required for our protocol is proportional to the size of the circuit to be computed.
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.
Executing a card-based cryptographic protocol is an attractive way to perform secure multiparty computation (MPC) with a deck of physical cards. Crèpeau and Kilian at CRYPTO 1993 proposed card-based AND and XOR protocols that can deal with a logical conjunction and exclusive-or of variables. Their protocols use a familiar shuffling action called a random cut that can be easily implemented by humans, while the numbers of required cards and shuffles are not small enough to be efficient and the protocols are Las Vegas algorithms, i.e., they are not finite-runtime. Several researchers have improved upon the protocols for a quarter of a century. Eventually, there are many AND protocols in the literature, some of which are quite efficient and practical to execute. By contrast, there are only three XOR protocols including the Crèpeau--Kilian protocol mentioned above. In this paper, we design an efficient XOR protocol using only random cuts; the numbers of required cards and shuffles are six and two (which is fixed), respectively. Our proposed XOR protocol is the first construction of a finite-runtime XOR protocol if we restrict ourselves to use only random cuts.
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.