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

ABSTRACT

We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks—distributed database maintenance and message transmission—a computationally unbounded adversary “plays an eavesdrpping game,” coordinating the moment of the bugs among the sites to learn the current memory contents. Many different adversaries 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.

REFERENCES

• 1: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 2: D. Bienstock , Paul Seymour, Monotonicity in graph searching, Journal of Algorithms, v.12 n.2, p.239-245, June 1991 [doi>10.1016/0196-6774(91)90003-H]
• 3: BREISCH, R. 1967. An intuitive approach to speleo-topology. Southwestern Cavers (published by the Southwestern Region of the National Speleological Society) 6, 72-78.
• 4: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 5: Benny Chor , Eyal Kushilevitz, A zero-one law for Boolean privacy, SIAM Journal on Discrete Mathematics, v.4 n.1, p.36-47, Feb. 1991 [doi>10.1137/0404004]
• 6: DENDRIS, N., KIROUSIS, L., AND THILIKOS, D. 1997. Fugitive-search games on graphs and related parameters. Theoret. Comput. Sci. 172, 233-254.
• 7: Danny Dolev , Cynthia Dwork , Orli Waarts , Moti Yung, Perfectly secure message transmission, Journal of the ACM (JACM), v.40 n.1, p.17-47, Jan. 1993 [doi>10.1145/138027.138036]
• 8: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 9: FOMIN, F., AND PETROV, N. 1996. Pursuit-evasion and search problems on graphs. Cong. Numer. 122, 47-58.
• 10: FRANKLIN, M., GALIL, Z., AND YUNG, M. 1993. Eavesdropping games: A graph-theoretic approach to privacy in distributed systems. In Proceedings of the Symposium on Foundations of Computer Science. IEEE, New York, pp. 670-679.
• 11: KIROUSIS, L., AND PAPADIMITRIOU, C. 1985. Interval graphs and searching. Discr. Math. 55, 181-184.
• 12: M Kirousis , C H Papadimitriou, Searching and pebbling, Theoretical Computer Science, v.47 n.2, p.205-218, Nov. 1986
• 13: Andrea S. LaPaugh, Recontamination does not help to search a graph, Journal of the ACM (JACM), v.40 n.2, p.224-245, April 1993 [doi>10.1145/151261.151263]
• 14: MAKEDON, F., PAPADIMITRIOU, C., AND SUDBOROUGH, I. 1985. Topological bandwidth. SIAM J. Alg. Disc. Meth. 6, 418-444.
• 15: N. Megiddo , S. L. Hakimi , M. R. Garey , D. S. Johnson , C. H. Papadimitriou, The complexity of searching a graph, Journal of the ACM (JACM), v.35 n.1, p.18-44, Jan. 1988 [doi>10.1145/42267.42268]
• 16: Rafail Ostrovsky , Moti Yung, How to withstand mobile virus attacks (extended abstract), Proceedings of the tenth annual ACM symposium on Principles of distributed computing, p.51-59, August 19-21, 1991, Montreal, Quebec, Canada [doi>10.1145/112600.112605]
• 17: PARSONS, T. 1976. Pursuit-evasion in a graph. In Theory and Application of Graphs. Y. Alavi and D. Lick, eds. Springer-Verlag, New York, pp. 426-441.
• 18: SAVITCH, W. 1970. Relationship between nondeterministic and deterministic tape complexities. J . Comput. Sys. Sci. 4, 177-192.
• 19: SHANNON, C. 1949. Communication theory of secrecy systems. Bell Sys. Tech. J. 30, 656-715.
• 20: P. Spirakis , B. Tampakas, Distributed pursuit-evasion: some aspects of privacy and security in distributed computing, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.403, August 14-17, 1994, Los Angeles, California, United States [doi>10.1145/197917.198191]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Security, Theory