Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs
Colleen Swanson, Douglas Stinson

Citation
Colleen Swanson, Douglas Stinson. "Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs". The Electronic Journal of Combinatorics, 2014.

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 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 examples solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. 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$.

 Citation formats
• HTML
Colleen Swanson, Douglas Stinson. <a
href="http://www.terraswarm.org/pubs/250.html"
>Additional Constructions to Solve the Generalized
Russian Cards Problem using Combinatorial Designs</a>,
<i>The Electronic Journal of Combinatorics</i>,
2014.
• Plain text
Colleen Swanson, Douglas Stinson. "Additional
Constructions to Solve the Generalized Russian Cards Problem
using Combinatorial Designs". <i>The Electronic
Journal of Combinatorics</i>,  2014.
• BibTeX
@article{SwansonStinson14_AdditionalConstructionsToSolveGeneralizedRussianCards,
author = {Colleen Swanson and Douglas Stinson},
title = {Additional Constructions to Solve the Generalized
Russian Cards Problem using Combinatorial Designs},
journal = {The Electronic Journal of Combinatorics},
year = {2014},
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
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 examples
solutions, including a construction that yields
perfect $1$-security against Cathy when $c=2$.
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$.},
URL = {http://terraswarm.org/pubs/250.html}
}


Posted by Mary Reagor on 3 Feb 2014.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.