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 .
The Russian cards problem and variants of it has received a fair amount of attention in the literature, with focus ranging from possible applications to key generation @cite_19 @cite_1 @cite_7 @cite_10 @cite_0 @cite_8 @cite_2 @cite_9 @cite_15 , to analyses based on epistemic logic @cite_14 @cite_18 @cite_20 @cite_4 , to card deals with more than three players @cite_13 @cite_17 . Of more relevance to our work is the recent research that takes a combinatorial approach @cite_24 @cite_16 @cite_15 @cite_9 @cite_5 @cite_25 , on which we now focus.
@cite_2 @cite_5 @cite_15 @cite_10 @cite_20 @cite_18 @cite_4 @cite_8 @cite_17 @cite_7 @cite_19 @cite_16 @cite_25 @cite_14 @cite_9 @cite_1 @cite_0 @cite_24 @cite_13
1608583290 2061333098 2153157844 1594719402 50630933 1694772419 1569180537 285496042 1643493712 2141368734 230082676 1516788100 2041435496 165070137 2027785398
Consider three players Alice, Bob and Cath who hold a, b and c cards, respectively, from a deck of d = a+b+c cards. The cards are all different and players only know their own cards. Suppose Alice and Bob wish to communicate their cards to each other without Cath learning whether Alice or Bob holds a specific card. Considering the cards as consecutive natural numbers 0, 1, . . . , we investigate general conditions for when Alice or Bob can safely announce the sum of the cards they hold modulo an appropriately chosen integer. We demonstrate that this holds whenever a, b > 2 and c = 1. Because Cath holds a single card, this also implies that Alice and Bob will learn the card deal from the other player’s announcement. We implement a specific protocol for bit exchange among card-playing agents in three different state-of-the-art epistemic model checkers and compare the results. In this paper it is shown that no public announce- ment scheme that can be modeled in Dynamic Epistemic Logic (DEL) can solve the Russian Cards Problem (RCP) in one announcement. Since DEL is a general model for any public announcement scheme (11), (3), (6), (21), (12) we conclude that there exist no single announcement solution to the RCP. The proof demonstrates the utility of DEL in proving lower bounds for communication protocols. It is also shown that a general version of RCP has no two announcement solution when the adversary has sufficiently large number of cards. Using a random deal of cards to players and a computationally unlimited eavesdropper, all players wish to share a one-bit secret key which is information-theoretically secure from the eavesdropper. This can be done by a protocol to make several pairs of players share one-bit secret keys so that all these pairs form a tree over players. In this paper we obtain a necessary and sufficient condition on the number of cards for the existence of such a protocol. This paper is concerned with public communication with the Russian Cards protocol. First, a couple of small flaws in [10] are corrected. Then an improved Russian Cards protocol is presented. As a case study, R(6, 31)(6 players and 31 cards) protocol is used to generate a common password for 5 parties who wish to access a shared file over the Internet. Abstract : Protocols are developed and analyzed for transmitting a secret bit between a sender and a receiver process using only the information contained in a random deal of hands of specified sizes from a deck of n distinct cards. The sender's and receiver's algorithms are known i advance, and all conversation between sender and receiver is public and is heard by all. A correct protocol always succeeds in transmitting the secret bit, and the other player(s), who receive the remaining cards and are assumed to have unlimited computing power, gain no information whatsoever about the value of the secret bit. In other words, their probability of correctly guessing the secret is bit exactly the same after listening to a run of the protocol as it was before. Both randomized and deterministic protocols are considered. A randomized protocol is described which works whenever the sender's and receiver's hands comprise a constant fraction of the deck, for all sufficiently large decks. A deterministic protocol is also described, but it requires the sender and receiver to each have approximately 44 of the cards. A general condition is presented that provides a lower bound on sizes of the sender's and receiver's hands in order for a protocol to exist. There is still a considerable gap between the upper and lower bounds, and improving the bounds remains an open problem. (kr) Public key cryptography bases its security on mathematical problems that are computationally hard to solve. There are also cryptographic protocols wherein discovering the secret is not too complex given the current state of technology, but logically impossible. One approach involves the use of a random deck of cards for such protocols. The messages in the protocol consist of announcements made by the two players attempting to exchange a secret. In that approach one may require that these two players can communicate their holding of cards to each other without the remaining players (eavesdroppers) learning a single card in these holdings. In past work we described combinatorial axioms to achieve that. The eavesdroppers may still be able to make an educated guess about individual card occurrence (card ownership). In this work we focus on overcoming such bias. From the perspective of cryptography there are two ways to do that: either use protocols that produce announcements that are unbiased for card occurrence, or use protocols that ensure that there is no relation between patterns in the announcement, such as card occurrence, and the actual holding. We focus on the first. We devise an additional requirement for the announcement in order to eliminate the possibility of making educated guesses. To that effect we propose an additional combinatorial axiom CA4, and we give a method to design announcements that meet this requirement. Additionally, we present unbiased protocols for incidental cases. 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. Given an interpreted system, we investigate ways for two agents to communicate secrets by public announcements. For card deals, the problem to keep all of your cards a secret (i) can be distinguished from the problem to keep some of your cards a secret (ii). For (i): we characterize a novel class of protocols consisting of two announcements, for the case where two agents both hold n cards and the third agent a single card; the communicating agents announce the sum of their cards modulo 2n + 1. For (ii): we show that the problem to keep at least one of your cards a secret is equivalent to the problem to keep your local state (hand of cards) a secret; we provide a large class of card deals for which exchange of secrets is possible; and we give an example for which there is no protocol of less than three announcements. We consider the problem of multiparty secret key exchange. A "team" of players P1 through Pk wishes to determine an n-bit secret key in the presence of a computationally unlimited eavesdropper, Eve. The team players are dealt hands of cards of prespecified sizes from a deck of d distinct cards; any remaining cards are dealt to Eve. We explore how the team can use the information contained in their hands of cards to determine an n-bit key that is secret from Eve, that is, an n bit string which each team player knows exactly but for which Eve's probability of guessing the key correctly is 1 2n both before and after she hears the communication between the team players. We describe randomized protocols for secret key exchange that work for certain classes of deals, and we present some conditions on the deal for such a protocol to exist. We present a general model for communication among a "team" of players overheard by a passive eavesdropper, Eve, in which all players including Eve are given private inputs that may be correlated. We define and explore secret key exchange in this model. Our secrecy requirements are information-theoretic and hold even if Eve is computationally unlimited. In particular, we consider the situation in which the team players are dealt hands of cards of prespecified sizes from a known deck of distinct cards. We explore when the team players can use the information contained in their hands to determine a value that each team player knows exactly but Eve cannot guess. Two parties A and B select a cards and b cards from a known deck and a third party C receives the remaining c cards. We consider methods whereby A can, in a single message, publicly inform B of her hand without C learning any card held by A or by B. Conditions on a, b, c are given for the existence of an appropriate message. This paper investigates Russian Cards problem for the purpose of unconditional secure communication. First, a picking rule and deleting rule as well as safe communication condition are given to deal with the problem with 3 players and 7 cards. Further, the problem is generalized to tackle n players and n(n−1)+1 cards. A new picking rule for constructing the announcement is presented, and a new deleting rule for players to determine each other’s cards is formalized. Moreover, the safe communication condition is proved. In addition, to illustrate the approach, an example for 5 players and 21 cards is presented in detail.