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

Natural Computing

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

Kazunari Tozawa, Hiraku Morita, Takaaki Mizuki

Published Jan 9, 2025• 3 citations
Publisher

Abstract

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.

DOI
10.1007/s11047-024-10006-5

Related papers

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

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

Tomoki Kuzuma, Raimu Isuzugawa, Kodai Toyoda +2 more

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 24, 2022•18 citations

Efficient Card-Based Protocols for Symmetric Functions Using Four-Colored Decks

Yoshihiro Takahashi, Kazumasa Shinagawa, Hayato Shikata +1 more

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 28, 2024•8 citations

Few-helping-card Protocols for Some Wider Class of Symmetric Boolean Functions with Arbitrary Ranges

Hayato Shikata, Daiki Miyahara, Takaaki Mizuki

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•Jun 20, 2023•9 citations

Batching Techniques Using Generalized Pile-Scramble Shuffles and Branching Shuffles

Yuto ISHIZAKI, Kazumasa Shinagawa, Koji Nuida

Card-based cryptography is a research field for realizing secure computation using physical cards. In card-based protocols, the efficiency of a protocol is mainly measured by the number of cards and the number of shuffles. Shinagawa and Nuida proposed a batching technique, which is a technique for reducing the number of pile-scramble shuffles (PSS) by combining multiple PSSs into a single PSS. In this paper, we propose three new methods for the batching technique. The first method uses a new shuffle called a generalized PSS; unlike a PSS, this allows the number of cards in each pile to be uneven. The second method uses a shuffle called a branching PSS, which is a PSS for a sequence including face-up cards. The third method uses a shuffle called a branching generalized PSS, which is a generalized PSS for a sequence including face-up cards. Our methods are efficient in terms of the number of cards and shuffles compared to the existing batching technique. As applications, we use our methods to reduce the number of shuffles for AND protocols and XOR protocols.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 31, 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
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.
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.
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.
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.
Card-based cryptography is a research field for realizing secure computation using physical cards. In card-based protocols, the efficiency of a protocol is mainly measured by the number of cards and the number of shuffles. Shinagawa and Nuida proposed a batching technique, which is a technique for reducing the number of pile-scramble shuffles (PSS) by combining multiple PSSs into a single PSS. In this paper, we propose three new methods for the batching technique. The first method uses a new shuffle called a generalized PSS; unlike a PSS, this allows the number of cards in each pile to be uneven. The second method uses a shuffle called a branching PSS, which is a PSS for a sequence including face-up cards. The third method uses a shuffle called a branching generalized PSS, which is a generalized PSS for a sequence including face-up cards. Our methods are efficient in terms of the number of cards and shuffles compared to the existing batching technique. As applications, we use our methods to reduce the number of shuffles for AND protocols and XOR protocols.
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.