Strong authenticated key exchange with auxiliary inputs

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 Alice and Bob’s exchanges do not allow Cath to 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. 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 strategies based on affine or projective geometries yield \(\varepsilon \)-strong safety for arbitrarily small \(\varepsilon \) and appropriately chosen values of a, b, c.