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:2009.13644

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

Sergio Rajsbaum

Published Sep 28, 2020• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2009.13644

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

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

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

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

Secure aggregation of distributed information

David Fernández–Duque, Valentin Goranko

We consider the generic problem of Secure Aggregation of Distributed Information (SADI), where several agents acting as a team have information distributed among them, modeled by means of a publicly known deck of cards distributed among the agents, so that each of them knows only her cards. The agents have to exchange and aggregate the information about how the cards are distributed among them by means of public announcements over insecure communication channels, intercepted by an adversary eavesdropper, in such a way that the adversary does not learn who holds any of the cards. We present a combinatorial construction of protocols that provides a direct solution of a class of SADI problems and develop a technique of iterated reduction of SADI problems to smaller ones which are eventually solvable directly. We show that our methods provide a solution to a large class of SADI problems, including all SADI problems with sufficiently large size and sufficiently balanced card distributions.

arXiv:1407.7582•Jul 28, 2014•3 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
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 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 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 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.
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.
We consider the generic problem of Secure Aggregation of Distributed Information (SADI), where several agents acting as a team have information distributed among them, modeled by means of a publicly known deck of cards distributed among the agents, so that each of them knows only her cards. The agents have to exchange and aggregate the information about how the cards are distributed among them by means of public announcements over insecure communication channels, intercepted by an adversary eavesdropper, in such a way that the adversary does not learn who holds any of the cards. We present a combinatorial construction of protocols that provides a direct solution of a class of SADI problems and develop a technique of iterated reduction of SADI problems to smaller ones which are eventually solvable directly. We show that our methods provide a solution to a large class of SADI problems, including all SADI problems with sufficiently large size and sufficiently balanced card distributions.
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.