Lower Bound for the Communication Complexity of the Russian Cards Problem

2008/05/14 by Aiswarya Cyriac, Cyriac, Aiswarya, K. Murali Krishnan +1 · 1 citation
Computer Science · #Advanced Algebra and Logic #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Multi-Agent Systems and Negotiation #cs.LO

paper · pdf · doi:10.48550/arxiv.0805.1974

5 pages

openalex publication_date 2008/05/14 · arxiv created 2008/12/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper it is shown that no public announcement scheme that can be modeled in Dynamic Epistemic Logic (DEL) can solve the Russian Cards Problem (RCP) in one announcement. Since DEL is a general model for any public announcement scheme we conclude that there exist no single announcement solution to the RCP. The proof demonstrates the utility of DEL in proving lower bounds for communication protocols. It is also shown that a general version of RCP has no two announcement solution when the adversary has sufficiently large number of cards.

Cited by

• Combinatorial Solutions Providing Improved Security for the Generalized Russian Cards Problem

Related

• A Distributed Computing Perspective of Unconditionally Secure Information Transmission in Russian Cards Problems
• Additional Constructions to Solve the Generalized Russian Cards Problem using Combinatorial Designs
• Combinatorial Solutions Providing Improved Security for the Generalized Russian Cards Problem
• Finding Collisions in Interactive Protocols -- Tight Lower Bounds on the Round and Communication Complexities of Statistically Hiding Commitments
• A case study in almost-perfect security for unconditionally secure\n communication