2015/06/12 by Esteban Landerreche, Landerreche, Esteban, David Fernández–Duque +1 · 1 citation
Computer Science · Engineering · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1506.04188
openalex publication_date 2015/06/12 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
In the Russian cards problem, Alice, Bob and Cath draw a, b and c\ncards, respectively, from a publicly known deck. Alice and Bob must then\ncommunicate their cards to each other without Cath learning who holds a single\ncard. Solutions in the literature provide weak security, where Cath does not\nknow with certainty who holds each card that is not hers, or perfect security,\nwhere Cath learns no probabilistic information about who holds any given card\nfrom Alice and Bob's exchange. We propose an intermediate notion, which we call\n\ε-strong security, where the probabilities perceived by Cath may\nonly change by a factor of \ε. We then show that a mild variant of\nthe so-called geometric strategy gives \ε-strong safety for\narbitrarily small \ε and appropriately chosen values of a,b,c.\n