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

arXiv:1111.0156 · Australas. J Comb.

A secure additive protocol for card players

Andrés Cordón–Franco, Hans van Ditmarsch, David Fernández–Duque, Joost J. Joosten, Fernando Soler Toscano

Published Nov 1, 2011• 10 citations
arXivHTMLPDF

Abstract

Consider three players Alice, Bob and Cath who hold a, b and c cards, respectively, from a deck of d=a+b+c cards. The cards are all different and players only know their own cards. Suppose Alice and Bob wish to communicate their cards to each other without Cath learning whether Alice or Bob holds a specific card. Considering the cards as consecutive natural numbers 0,1,..., we investigate general conditions for when Alice or Bob can safely announce the sum of the cards they hold modulo an appropriately chosen integer. We demonstrate that this holds whenever a,b>2 and c=1. Because Cath holds a single card, this also implies that Alice and Bob will learn the card deal from the other player's announcement.

DOI
10.48550/arxiv.1111.0156

Related papers

Combinatorial Solutions Providing Improved Security for the Generalized Russian Cards Problem

Colleen Marie Swanson, Douglas R. Stinson

We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of $n$ cards, each given $a$, $b$, and $c$ cards, respectively. The goal is for Alice and Bob to learn each other's hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice's cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice's hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of $t-(n, a, 1)$-designs, where $t=a-c$. We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying $c = a-d$ for some $d \geq 2$, where $b \geq d-1$ and the strategy is assumed to satisfy a strong version of security (namely perfect $(d-1)$-security), we show that $a = d+1$ and hence $c=1$. We also give a precise characterization of informative and perfectly $(d-1)$-secure deals of the form $(d+1, b, 1)$ satisfying $b \geq d-1$ involving $d-(n, d+1, 1)$-designs.

arXiv:1207.1336•Jul 5, 2012•0 citations

A case study in almost-perfect security for unconditionally secure communication

Esteban Landerreche, David Fernández–Duque

In the Russian cards problem, Alice, Bob and Cath draw a, b and c cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Alice and Bob’s exchanges do not allow Cath to know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card. We propose an intermediate notion, which we call $$\varepsilon $$ -strong security, where the probabilities perceived by Cath may only change by a factor of $$\varepsilon $$ . We then show that strategies based on affine or projective geometries yield $$\varepsilon $$ -strong safety for arbitrarily small $$\varepsilon $$ and appropriately chosen values of a, b, c.

arXiv:1506.04188•Designs Codes and Cryptography•Apr 23, 2016•4 citations

Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs

Colleen Marie Swanson, Douglas R. Stinson

In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy, for her part, should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $\delta$ cards (perfect $\delta$-security). As we demonstrate in this work, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $\delta$-secure strategies and $(c+\delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. Drawing on our equivalence results, we are able to use a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $\delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = \lfloor \frac{a-\delta}{2} \rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $\delta$, $c$ and any $a \geq \delta + 2c$.

arXiv:1401.1526•The Electronic Journal of Combinatorics•Aug 21, 2014•9 citations

The case of the hidden hand

Hans van Ditmarsch

In unconditionally secure protocols, a sender and receiver are able to communicate their secrets to each other without the eavesdropper(s) being able to learn the secret, even when the eavesdropper intercepts the entire communication. We investigate such protocols for the special case of deals of cards over players, where two players aim to communicate to each other their hand of cards without the remaining player(s) learning a single card from either hand. In this contribution we show that a particular protocol of length strictly larger than two (i.e., consisting of more than just one announcement by one player, and one other announcement by the other player) is after all not acceptable, and therefore does not constitute a new solution. The demonstration requires a detailed case-based analysis. The result may bring a general approach to arbitrary finite-length protocols closer.

Journal of Applied Non-Classical Logics•Jan 1, 2005•8 citations

Securely Computing Three-Input Functions with Eight Cards

Takuya Nishida, Yu‐ichi Hayashi, Takaaki Mizuki +1 more

Assume that Alice, Bob, and Carol, each of whom privately holds a one-bit input, want to learn the output of some Boolean function, say the majority function, of their inputs without revealing more of their own secret inputs than necessary. In this paper, we show that such a secure three-input function evaluation can be performed with a deck of real cards; specifically, the three players can learn only the output of the function using eight physical cards — four black and four red cards — with identical backs.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2015•23 citations

A Distributed Computing Perspective of Unconditionally Secure Information Transmission in Russian Cards Problems

Sergio Rajsbaum

The problem of $A$ privately transmitting information to $B$ by a public announcement overheard by an eavesdropper $C$ is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature $(a,b,c)$, where $n = a + b + c + r$, and $A$ gets $a$ cards, $B$ gets $b$ cards, and $C$ gets $c$ cards, out of the deck of $n$ cards. Using a deterministic protocol, $A$ decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that $A$ needs to send, while preventing $C$ from learning a single card of her hand. In one extreme, the generalized Russian cards problem, $B$ wants to learn all of $A$'s cards, and in the other, $B$ wishes to learn something about $A$'s hand.

arXiv:2009.13644•Sep 28, 2020•0 citations
Consider three players Alice, Bob and Cath who hold a, b and c cards, respectively, from a deck of d=a+b+c cards. The cards are all different and players only know their own cards. Suppose Alice and Bob wish to communicate their cards to each other without Cath learning whether Alice or Bob holds a specific card. Considering the cards as consecutive natural numbers 0,1,..., we investigate general conditions for when Alice or Bob can safely announce the sum of the cards they hold modulo an appropriately chosen integer. We demonstrate that this holds whenever a,b>2 and c=1. Because Cath holds a single card, this also implies that Alice and Bob will learn the card deal from the other player's announcement.
We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extended versions of weak and perfect security notions. In the generalized Russian cards problem, three players, Alice, Bob, and Cathy, are dealt a deck of nnn cards, each given aaa, bbb, and ccc cards, respectively. The goal is for Alice and Bob to learn each other's hands via public communication, without Cathy learning the fate of any particular card. The basic idea is that Alice announces a set of possible hands she might hold, and Bob, using knowledge of his own hand, should be able to learn Alice's cards from this announcement, but Cathy should not. Using a combinatorial approach, we are able to give a nice characterization of informative strategies (i.e., strategies allowing Bob to learn Alice's hand), having optimal communication complexity, namely the set of possible hands Alice announces must be equivalent to a large set of t−(n,a,1)t-(n, a, 1)t−(n,a,1)-designs, where t=a−ct=a-ct=a−c. We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying c=a−dc = a-dc=a−d for some d≥2d \geq 2d≥2, where b≥d−1b \geq d-1b≥d−1 and the strategy is assumed to satisfy a strong version of security (namely perfect (d−1)(d-1)(d−1)-security), we show that a=d+1a = d+1a=d+1 and hence c=1c=1c=1. We also give a precise characterization of informative and perfectly (d−1)(d-1)(d−1)-secure deals of the form (d+1,b,1)(d+1, b, 1)(d+1,b,1) satisfying b≥d−1b \geq d-1b≥d−1 involving d−(n,d+1,1)d-(n, d+1, 1)d−(n,d+1,1)-designs.
In the Russian cards problem, Alice, Bob and Cath draw a, b and c cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Alice and Bob’s exchanges do not allow Cath to know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card. We propose an intermediate notion, which we call ε\varepsilon ε -strong security, where the probabilities perceived by Cath may only change by a factor of ε\varepsilon ε . We then show that strategies based on affine or projective geometries yield ε\varepsilon ε -strong safety for arbitrarily small ε\varepsilon ε and appropriately chosen values of a, b, c.
In the generalized Russian cards problem, we have a card deck XXX of nnn cards and three participants, Alice, Bob, and Cathy, dealt aaa, bbb, and ccc cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy, for her part, should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathy's ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak 111-security) to not gaining any probabilistic advantage in guessing the fate of some set of δ\deltaδ cards (perfect δ\deltaδ-security). As we demonstrate in this work, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly δ\deltaδ-secure strategies and (c+δ)(c+\delta)(c+δ)-designs on nnn points with block size aaa, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect 111-security against Cathy when c=2c=2c=2. Drawing on our equivalence results, we are able to use a known combinatorial design to construct a strategy with a=8a=8a=8, b=13b=13b=13, and c=3c=3c=3 that is perfectly 222-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak δ\deltaδ-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of c=⌊a−δ2⌋c = \lfloor \frac{a-\delta}{2} \rfloorc=⌊2a−δ​⌋ cards. Alternatively, the construction yields solutions for arbitrary δ\deltaδ, ccc and any a≥δ+2ca \geq \delta + 2ca≥δ+2c.
In unconditionally secure protocols, a sender and receiver are able to communicate their secrets to each other without the eavesdropper(s) being able to learn the secret, even when the eavesdropper intercepts the entire communication. We investigate such protocols for the special case of deals of cards over players, where two players aim to communicate to each other their hand of cards without the remaining player(s) learning a single card from either hand. In this contribution we show that a particular protocol of length strictly larger than two (i.e., consisting of more than just one announcement by one player, and one other announcement by the other player) is after all not acceptable, and therefore does not constitute a new solution. The demonstration requires a detailed case-based analysis. The result may bring a general approach to arbitrary finite-length protocols closer.
Assume that Alice, Bob, and Carol, each of whom privately holds a one-bit input, want to learn the output of some Boolean function, say the majority function, of their inputs without revealing more of their own secret inputs than necessary. In this paper, we show that such a secure three-input function evaluation can be performed with a deck of real cards; specifically, the three players can learn only the output of the function using eight physical cards — four black and four red cards — with identical backs.
The problem of AAA privately transmitting information to BBB by a public announcement overheard by an eavesdropper CCC is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature (a,b,c)(a,b,c)(a,b,c), where n=a+b+c+rn = a + b + c + rn=a+b+c+r, and AAA gets aaa cards, BBB gets bbb cards, and CCC gets ccc cards, out of the deck of nnn cards. Using a deterministic protocol, AAA decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that AAA needs to send, while preventing CCC from learning a single card of her hand. In one extreme, the generalized Russian cards problem, BBB wants to learn all of AAA's cards, and in the other, BBB wishes to learn something about AAA's hand.