A Distributed Computing Perspective of Unconditionally Secure Information Transmission in Russian Cards Problems
This work addresses secure communication in cryptographic protocols, specifically for scenarios like card games or distributed systems, but it appears incremental as it builds on existing Russian cards problems with a new analytical framework.
The paper tackles the problem of securely transmitting information from A to B via a public announcement while preventing eavesdropper C from learning any of A's cards, using a deterministic protocol with correlated inputs modeled as card distributions. It provides a novel distributed computing perspective to analyze the required information transmission, addressing scenarios where B aims to learn all or some of A's cards.
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.