In the generalized Russian cards problem, we have a card deck @math of @math cards and three participants, Alice, Bob, and Cathy, dealt @math , @math , and @math 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 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 @math -security) to not gaining any probabilistic advantage in guessing the fate of some set of @math cards (perfect @math -security). As we demonstrate, 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 @math -secure strategies and @math -designs on @math points with block size @math , 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 @math -security against Cathy when @math . We leverage a known combinatorial design to construct a strategy with @math , @math , and @math that is perfectly @math -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 @math -security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of @math cards. Alternatively, the construction yields solutions for arbitrary @math , @math and any @math .
In the generalized Russian cards problem, the three players Alice, Bob and Cath draw @math a , b and @math c cards, respectively, from a deck of @math a + b + c cards. Players only know their own cards and what the deck of cards is. Alice and Bob are then required to communicate their hand of cards to each other by way of public messages. For a natural number @math k , the communication is said to be @math k -safe if Cath does not learn whether or not Alice holds any given set of at most @math k cards that are not Cath's, a notion originally introduced as weak @math k -security by Swanson and Stinson. An elegant solution by Atkinson views the cards as points in a finite projective plane. We propose a general solution in the spirit of Atkinson's, although based on finite vector spaces rather than projective planes, and call it the geometric protocol'. Given arbitrary @math c , k > 0 , this protocol gives an informative and @math k -safe solution to the generalized Russian cards problem for infinitely many values of @math ( a , b , c ) with @math b = O ( a c ) . This improves on the collection of parameters for which solutions are known. In particular, it is the first solution which guarantees @math k -safety when Cath has more than one card.