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

Electronic downloads

• Swanson_RussianCards.pdf · application/pdf · 857 kbytes
• http://arxiv.org/pdf/1401.1526v2

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