A case study in almost-perfect security for unconditionally secure communication
This work addresses secure communication in multi-party scenarios, offering a practical compromise between weak and perfect security, though it is incremental as it builds on existing geometric strategies.
The paper tackles the Russian cards problem by introducing an intermediate security notion called ε-strong security, where an eavesdropper's probability estimates change by at most a factor of ε, and shows that a variant of the geometric strategy achieves this for arbitrarily small ε with suitable parameters.
In the Russian cards problem, Alice, Bob and Cath draw $a$, $b$ and $c$ cards, respectively, from a publicly known deck. Alice and Bob must then communicate their cards to each other without Cath learning who holds a single card. Solutions in the literature provide weak security, where Cath does not know with certainty who holds each card that is not hers, or perfect security, where Cath learns no probabilistic information about who holds any given card from Alice and Bob's exchange. We propose an intermediate notion, which we call $\varepsilon$-strong security, where the probabilities perceived by Cath may only change by a factor of $\varepsilon$. We then show that a mild variant of the so-called geometric strategy gives $\varepsilon$-strong safety for arbitrarily small $\varepsilon$ and appropriately chosen values of $a,b,c$.