Communication in the presence of replication

ABSTRACT

We consider the following problem. Suppose that a big amount of data is distributed among several parties, so that each party misses only few pieces of data. The parties wish to perform some global computation on the data while minimizing the communication between them. This situation is common in many real-life scenarios. A naive solution to this problem is to first perform a synchronization step, letting one party learn all pieces of data, and then let this party perform the required computation locally. We study the question of obtaining better solutions to the problem, focusing mainly on the case of computing low-degree polynomials via non-interactive protocols. We present interesting connections between this problem and the well studied cryptographic problem of secret sharing. We use this connection to obtain nontrivial upper bounds and lower bounds using results and techniques from the domain of secret sharing. The relation with open problems from the area of secret sharing also provides evidence for the difficulty of resolving some of the questions we leave open.

REFERENCES

• 1: László Babai , Anna Gál , Peter G. Kimmel , Satyanarayana V. Lokam, Communication Complexity of Simultaneous Messages, SIAM Journal on Computing, v.33 n.1, p.137-166, 2004 [doi>10.1137/S0097539700375944]
• 2: O. Barkol and Y. Ishai. Secure computation of constant-depth circuits with applications to database search problems. In Proc. of Crypto 2005, pages 395--411.
• 3: A. Beimel. Secure schemes for secret sharing and key distribution. PhD thesis, Technion, 1996.
• 4: Amos Beimel , Yuval Ishai, Information-Theoretic Private Information Retrieval: A Unified Construction, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.912-926, July 08-12, 2001
• 5: G.R. Blakley. Safeguarding cryptographic keys. In Proc. of the American Federation of Information Processing Societies (AFIPS), volume 48, pages 313--317, 1979.
• 6: C. Blundo, A. De Santis, D. R. Stinson, and U. Vaccaro. Graph decompositions and secret sharing schemes. J. Cryptology, 8(1):39--64, 1995.
• 7: Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
• 8: R. Cramer, I. Damgå rd, and Y. Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In Proc. 2nd TCC, pages 342--362, 2005.
• 9: L. Csirmaz. Secret sharing schemes on graphs. http://citeseer.ist.psu.edu/246719.html.
• 10: Tomas Feder , Moni Naor , Eyal Kushilevitz , Noam Nisan, Amortized Communication Complexity, SIAM Journal on Computing, v.24 n.4, p.736-750, Aug. 1995 [doi>10.1137/S0097539792235864]
• 11: Anna Gál, A characterization of span program size and improved lower bounds for monotone span programs, Computational Complexity, v.10 n.4, p.277-296, May 2002 [doi>10.1007/s000370100001]
• 12: P. Harsha, Y. Ishai, J. Kilian, K. Nissim, and S. Venkatesh. Communication versus computation. In Proc. 31st ICALP, pages 745--756, 2004.
• 13: J. Hastad and M. Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1(2):113--129, 1991.
• 14: M. Karchmer and A. Wigderson. On span programs. In Proc. 8th CCC, pages 102--1111, 1993.
• 15: J. Kilian and N. Nisan. Private communication, 1990.
• 16: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 17: S. Sandeep Pradhan , Kannan Ramchandran, Distributed Source Coding Using Syndromes (DISCUS): Design and Construction, Proceedings of the Conference on Data Compression, p.158, March 29-31, 1999
• 18: P. Pudlák , V. Rödl, Modified ranks of tensors and the size of circuits, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.523-531, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167228]
• 19: P. Pudlák and J. Sgall. Algebraic models of computation and interpolation for algebraic proof systems. DIMACS Ser. in Disc. Math. and Th. Comp. Sci., 39:279--295, 1998.
• 20: A. Razborov. Lower bounds for the size of circuits of bounded depth with basis (AND, XOR). Math. Notes of the Academy of Sci. of USSR, 41(4):333--338, 1987.
• 21: Ron Roth, Introduction to Coding Theory, Cambridge University Press, New York, NY, 2006
• 22: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 23: D. Slepian and J. Wolf. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19(4):471--480, 1973.
• 24: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Reliability, Security, Theory

Keywords:
communication complexity, secret sharing, simultaneous messages