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:1401.1526 · The Electronic Journal of Combinatorics

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

Colleen Marie Swanson, Douglas R. Stinson

Published Aug 21, 2014• 9 citations
arXivHTMLPDF

Abstract

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$.

DOI
10.37236/4019

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

Who holds the best card? Secure communication of optimal secret bits.

Hans van Ditmarsch, David Fernández–Duque, Vaishnavi Sundararajan +1 more

In the Russian cards problem, a group of communicating agents and an eavesdropper, Eve, draw cards from a deck. The agents then wish to inform each other about their hand without Eve learning any 'protected' information, typically in the sense of weak possibilistic security. We consider a weakening of this original problem, whereby the cards are linearly ordered by value. The agents wish to know the value of the best card held between them, without Eve knowing who holds said card. We consider standard solutions to the problem based on combinatorial designs, as well as novel solutions based on secret-bit-exchange protocols. Our results show that this version of the problem can be solved in many instances where the size of each agent's hand is linear on that of the eavesdropper's.

Australas. J Comb.•Jan 1, 2021•0 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

Unconditionally Secure Cryptography: Signature Schemes, User-Private Information Retrieval, and the Generalized Russian Cards Problem

Colleen Marie Swanson

We focus on three different types of multi-party cryptographic protocols. The first is in the area of unconditionally secure signature schemes, the goal of which is to provide users the ability to electronically sign documents without the reliance on computational assumptions needed in traditional digital signatures. The second is on cooperative protocols in which users help each other maintain privacy while querying a database, called user-private information retrieval protocols. The third is concerned with the generalized Russian cards problem, in which two card players wish to communicate their hands to each other via public announcements without the third player learning the card deal. The latter two problems have close ties to the field of combinatorial designs, and properly fit within the field of combinatorial cryptography. All of these problems have a common thread, in that they are grounded in the information-theoretically secure or unconditionally secure setting.

•May 23, 2013•1 citation

A secure additive protocol for card players

Andrés Cordón–Franco, Hans van Ditmarsch, David Fernández–Duque +2 more

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.

arXiv:1111.0156•Australas. J Comb.•Nov 1, 2011•10 citations
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.
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 Russian cards problem, a group of communicating agents and an eavesdropper, Eve, draw cards from a deck. The agents then wish to inform each other about their hand without Eve learning any 'protected' information, typically in the sense of weak possibilistic security. We consider a weakening of this original problem, whereby the cards are linearly ordered by value. The agents wish to know the value of the best card held between them, without Eve knowing who holds said card. We consider standard solutions to the problem based on combinatorial designs, as well as novel solutions based on secret-bit-exchange protocols. Our results show that this version of the problem can be solved in many instances where the size of each agent's hand is linear on that of the eavesdropper's.
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.
We focus on three different types of multi-party cryptographic protocols. The first is in the area of unconditionally secure signature schemes, the goal of which is to provide users the ability to electronically sign documents without the reliance on computational assumptions needed in traditional digital signatures. The second is on cooperative protocols in which users help each other maintain privacy while querying a database, called user-private information retrieval protocols. The third is concerned with the generalized Russian cards problem, in which two card players wish to communicate their hands to each other via public announcements without the third player learning the card deal. The latter two problems have close ties to the field of combinatorial designs, and properly fit within the field of combinatorial cryptography. All of these problems have a common thread, in that they are grounded in the information-theoretically secure or unconditionally secure setting.
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.