cs.CR cs.DC cs.DM
A Distributed Computing Perspective of Unconditionally Secure Information Transmission in Russian Cards Problems. The problem of A privately transmitting information to B by a public announcement overheard by an eavesdropper C is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature (a,b,c) , where n a b c r , and A gets a cards, B gets b cards, and C gets c cards, out of the deck of n cards. Using a deterministic protocol, A decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that A needs to send, while preventing C from learning a single card of her hand. In one extreme, the generalized Russian cards problem, B wants to learn all of A 's cards, and in the other, B wishes to learn something about A 's hand.