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

Using Five Cards to Encode Each Integer in Z/6Z.

Suthee Ruangwises

Published Jan 1, 2020• 0 citations
OpenAlex

Abstract

Research in secure multi-party computation using a deck of playing cards, often called card-based cryptography, dates back to 1989 when Den Boer introduced the five-card trick to compute the logical AND function. Since then, many protocols to compute different functions have been developed. In this paper, we propose a new encoding scheme using five cards to encode each integer in $\mathbb{Z}/6\mathbb{Z}$. Using this encoding scheme, we develop protocols that can copy a commitment with 13 cards, add two integers with 10 cards, and multiply two integers with 16 cards. All of our protocols are the currently best known protocols in terms of the required number of cards. Our encoding scheme can also be generalized to encode integers in $\mathbb{Z}/n\mathbb{Z}$ for other values of $n$ as well.

Related papers

New Card-based Copy Protocols Using Only Random Cuts

Hiroto Koyama, Kodai Toyoda, Daiki Miyahara +1 more

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.

ACM ASIA Public-Key Cryptography Workshop (APKC)•May 24, 2021•20 citations

Secure Computations Through Checking Suits of Playing Cards

Daiki Miyahara, Takaaki Mizuki

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.

Lecture notes in computer science•Jan 1, 2022•14 citations

An nnn-Card Threshold Protocol Is Impossible

Shizuru Iino, Yang Li, Kazuo Sakiyama +1 more

Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: an$n$-card$n$-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.

IEEE Annual Computing and Communication Workshop and Conference (CCWC)•Jan 5, 2026•0 citations

Barrington Plays Cards: The Complexity of Card-Based Protocols

Pavel Dvořák, Michal Koucký

In this paper we study the computational complexity of functions that have efficient card-based protocols. Card-based protocols were proposed by den Boer [EUROCRYPT '89] as a means for secure two-party computation. Our contribution is two-fold: We classify a large class of protocols with respect to the computational complexity of functions they compute, and we propose other encodings of inputs which require fewer cards than the usual 2-card representation.

arXiv:2010.08445•Leibniz international proceedings in informatics•Oct 16, 2020•6 citations

Secure Computation Protocols Using Polarizing Cards

Kazumasa Shinagawa, Takaaki Mizuki, Jacob C. N. Schuldt +5 more

It is known that, using just a deck of cards, an arbitrary number of parties with private inputs can securely compute the output of any function of their inputs. In 2009, Mizuki and Sone constructed a six-card COPY protocol, a four-card XOR protocol, and a six-card AND protocol, based on a commonly used encoding scheme in which each input bit is encoded using two cards. However, up until now, there are no known results to construct a set of COPY, XOR, and AND protocols based on a two-card-per-bit encoding scheme, which all can be implemented using only four cards. In this paper, we show that it is possible to construct four-card COPY, XOR, and AND protocols using polarizing plates as cards and a corresponding two-card-per-bit encoding scheme. Our protocols use a minimum number of cards in the setting of two-card-per-bit encoding schemes since four cards are always required to encode the inputs. Moreover, we show that it is possible to construct two-card COPY, two-card XOR, and three-card AND protocols based on a one-card-per-bit encoding scheme using a common reference polarizer which is a polarizing material accessible to all parties.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2016•10 citations

The Asymmetric five-card trick: working with variable encoding in card-based protocols

Luis Guillen

Abstract Recently, card-based protocols have been extensively explored to illustrate relatively complex cryptographic concepts, such as Secure Multiparty Computations, so that even non-specialists can understand them. These protocols rely on three elements: a given alphabet with a set number of physical cards, encoding those cards, and shuffling operations. However, the execution is becoming over-complicated, as most follow the same encoding: fixed uniform disclosed encoding, which constrains other elements and decreases their expressiveness. This paper introduces the asymmetric five-card trick, a generalization of the five-card trick (a seminal work in the field of card-based cryptography) with the added feature of allowing variable encoding. To do so, we propose a pre-process called “handshake” that allows protocols to adapt operations based on players’ encoding. The protocol handshake is included as part of the protocol’s production phase in the proposed general framework, which is negotiated before its execution. Finally, this paper also introduces the notion of time and space complexity in card-based protocols to assess their production and execution’s lower bounds.

Journal of Cryptographic Engineering•Aug 31, 2023•0 citations
Research in secure multi-party computation using a deck of playing cards, often called card-based cryptography, dates back to 1989 when Den Boer introduced the five-card trick to compute the logical AND function. Since then, many protocols to compute different functions have been developed. In this paper, we propose a new encoding scheme using five cards to encode each integer in Z/6Z\mathbb{Z}/6\mathbb{Z}Z/6Z. Using this encoding scheme, we develop protocols that can copy a commitment with 13 cards, add two integers with 10 cards, and multiply two integers with 16 cards. All of our protocols are the currently best known protocols in terms of the required number of cards. Our encoding scheme can also be generalized to encode integers in Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ for other values of nnn as well.
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.
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.
Card-based cryptography uses a physical deck of playing cards to achieve secure computations. The first card-based protocol, called the five-card trick, allows Alice and Bob to decide whether to have a date without revealing their actual minds, i.e., it performs a secure computation of the logical two-input AND function. It uses a two-color deck of red and black cards, and the Boolean values are encoded based on the arrangement order of two distinct cards. The five-card trick was later optimized into a four-card AND protocol, achieving the minimal number of cards, because each input bit is encoded using two cards. Afterward, an alternative encoding, where each bit is represented by a single card, enabled a three-card AND protocol with a minor modification to the five-card trick. However, the construction of a two-card AND protocol remains an open problem. In this study, we provide a negative result for the problem: a two-card AND protocol is impossible. We extend this result to a more general class of functions, and consequently, derive the main impossibility theorem: annnn-cardnnn-input threshold protocol is impossible. Our result implies that the three-card AND protocol uses the minimal number of cards. A unique aspect of our proof is its simplicity; we show that it suffices to consider the initial and its subsequent states, unlike previous impossibility proofs that enumerate all possible states.
It is known that, using just a deck of cards, an arbitrary number of parties with private inputs can securely compute the output of any function of their inputs. In 2009, Mizuki and Sone constructed a six-card COPY protocol, a four-card XOR protocol, and a six-card AND protocol, based on a commonly used encoding scheme in which each input bit is encoded using two cards. However, up until now, there are no known results to construct a set of COPY, XOR, and AND protocols based on a two-card-per-bit encoding scheme, which all can be implemented using only four cards. In this paper, we show that it is possible to construct four-card COPY, XOR, and AND protocols using polarizing plates as cards and a corresponding two-card-per-bit encoding scheme. Our protocols use a minimum number of cards in the setting of two-card-per-bit encoding schemes since four cards are always required to encode the inputs. Moreover, we show that it is possible to construct two-card COPY, two-card XOR, and three-card AND protocols based on a one-card-per-bit encoding scheme using a common reference polarizer which is a polarizing material accessible to all parties.
Abstract Recently, card-based protocols have been extensively explored to illustrate relatively complex cryptographic concepts, such as Secure Multiparty Computations, so that even non-specialists can understand them. These protocols rely on three elements: a given alphabet with a set number of physical cards, encoding those cards, and shuffling operations. However, the execution is becoming over-complicated, as most follow the same encoding: fixed uniform disclosed encoding, which constrains other elements and decreases their expressiveness. This paper introduces the asymmetric five-card trick, a generalization of the five-card trick (a seminal work in the field of card-based cryptography) with the added feature of allowing variable encoding. To do so, we propose a pre-process called “handshake” that allows protocols to adapt operations based on players’ encoding. The protocol handshake is included as part of the protocol’s production phase in the proposed general framework, which is negotiated before its execution. Finally, this paper also introduces the notion of time and space complexity in card-based protocols to assess their production and execution’s lower bounds.