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

Theoretical Computer Science

Computations with a deck of cards

Anton Štiglić

Published May 1, 2001• 78 citations
Publisher
DOI
10.1016/s0304-3975(00)00409-6

Related papers

Multiparty Computations with a Deck of Cards.

Valtteri Niemi, Ari Renvall

Developments in Language Theory•Jan 1, 1997•2 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•9 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

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations

Classical computation

A. Kitaev, Alexander Khanievich Shen', M. Vyalyi

Graduate studies in mathematics•May 31, 2002•1 citation

Efficient Card-Based Protocols for Symmetric and Partially Doubly Symmetric Functions

S. Ikeda, Yoshihiro Takahashi, Kazumasa Shinagawa +1 more

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.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Mar 9, 2026•0 citations
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.
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.
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.