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 this paper, we build extensively on results by Swanson and Stinson @cite_25 . In particular, we greatly simplify the proofs for results connecting certain types of perfectly @math -secure deals and Steiner systems, originally shown in Swanson and Stinson @cite_25 . The construction technique using a starting design'', given in Theorem is a generalization of the technique given by Swanson and Stinson @cite_25 . This generalized construction technique allows us to answer in the affirmative the question on the existence of perfectly secure and informative strategies for deals in which Cathy holds more than one card.
@cite_25
2141368734
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 @math cards, each given @math , @math , and @math 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 @math -designs, where @math . We also provide some interesting necessary conditions for certain types of deals to be simultaneously informative and secure. That is, for deals satisfying @math for some @math , where @math and the strategy is assumed to satisfy a strong version of security (namely perfect @math -security), we show that @math and hence @math . We also give a precise characterization of informative and perfectly @math -secure deals of the form @math satisfying @math involving @math -designs.