Eavesdropping games: A graph-theoretic approach to privacy in distributed systems

We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks-distributed datab ase maintenance and message transmission-a computationally unbounded advers ary "plays an eavesdropping game," coordinating the movement of the bugs am ong the sites to learn the current memory contents. Many different adversar ies are considered, motivated by differences in eavesdropping technologies. We characterize the feasibility of the two privacy tasks combinatorially, construct protocols for the feasible cases, and analyze their computational complexity.