Combinatorial Solutions for the Generalized Russian Cards Problem

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 card deal. A special case of this problem, where (A,B,C) = (3,3,1), first appeared in the 2000 Moscow Mathematics Olympiad.

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 provide new formal security definitions and give a complete characterization of strategies for Alice that are simultaneously informative (i.e., Bob is able to determine Alice's hand after her announcement) and secure against Cathy in a strong sense.
Colleen Swanson received her master's degree in Combinatorics and Optimization at the University of Waterloo (Canada) and recently defended her Ph.D. in Computer Science, also at University of Waterloo. Her research to date has focused on information-theoretic and combinatorial cryptography, and her current research interests span a wide range of problems in computer security and privacy.