Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM ASIA Public-Key Cryptography Workshop (APKC)

Card-based Single-shuffle Protocols for Secure Multiple-input AND and XOR Computations

Tomoki Kuzuma, Raimu Isuzugawa, Kodai Toyoda, Daiki Miyahara, Takaaki Mizuki

Published May 24, 2022• 18 citations
Publisher

Abstract

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.

DOI
10.1145/3494105.3526236

Related papers

Single-shuffle card-based protocol with eight cards per gate and its extensions

Kazunari Tozawa, Hiraku Morita, Takaaki Mizuki

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 $$2n^2+6n+2$$ 2 n 2 + 6 n + 2 cards.

Natural Computing•Jan 9, 2025•3 citations

Single-Shuffle Card-Based Protocols for Any Boolean Circuit with Six Cards per Gate

Tomoki Ono, Kazumasa Shinagawa, Takeshi Nakai +2 more

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.

New Generation Computing•Oct 14, 2026•0 citations

A single shuffle is enough for secure card-based computation of any Boolean circuit

Kazumasa Shinagawa, Koji Nuida

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.

Discrete Applied Mathematics•Nov 2, 2020•42 citations

Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function

Reo Eriguchi, Kazumasa Shinagawa

A card-based secure computation protocol is a method for $n$ parties to compute a function $f$ on their private inputs $(x_1,\ldots,x_n)$ using physical playing cards, in such a way that the suits of revealed cards leak no information beyond the value of $f(x_1,\ldots,x_n)$. 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.

arXiv:2510.17308•Oct 20, 2025•0 citations

Card-based Cryptography with a Standard Deck of Cards, Revisited: Efficient Protocols in the Private Model

Takeshi Nakai, Keita Iwanari, Tomoki Ono +3 more

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.

New Generation Computing•Jun 21, 2024•6 citations

Six-Card Finite-Runtime XOR Protocol with Only Random Cut

Kodai Toyoda, Daiki Miyahara, Takaaki Mizuki +1 more

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Oct 5, 2020•19 citations
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+24g2n + 24g2n+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+8g2n + 8g2n+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+22n^2+6n+22n2+6n+2 2 n 2 + 6 n + 2 cards.
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.
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.
A card-based secure computation protocol is a method for nnn parties to compute a function fff on their private inputs (x1,…,xn)(x_1,\ldots,x_n)(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)f(x_1,\ldots,x_n)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.
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.
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.