Communication complexity of secure computation (extended abstract)

ABSTRACT

A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior. In this paper, we initiate the investigation of the communication complexity of unconditionally secure multi-party computation, and its relation with various fault-tolerance models. We present upper and lower bounds on communication, as well as tradeoffs among resources. First, we consider the “direct sum problem” for communications complexity of perfectly secure protocols: Can the communication complexity of securely computing a single function f : Fn → F at k sets of inputs be smaller if all are computed simultaneously than if each is computed individually? We show that the answer depends on the failure model. A factor of O(n/log n) can be gained in the privacy model (where processors are curious but correct); specifically, when f is n-ary addition (mod 2), we show a lower bound of &OHgr;(n2 log n) for computing f O(n) times simultaneously. No gain is possible in a slightly stronger fault model (fail-stop mode); specifically, when f is n-ary addition over GF(q), we show an exact bound of &THgr;(kn2 log q) for computing f at k sets of inputs simultaneously (for any k ≥ 1). However, if one is willing to pay an additive cost in fault tolerance (from t to t-k+1), then a variety of known non-cryptographic protocols (including “provably unparallelizable” protocols from above!) can be systematically compiled to compute one function at k sets of inputs with no increase in communication complexity. Our compilation technique is based on a new compression idea of polynomial-based multi-secret sharing. Lastly, we show how to compile private protocols into error-detecting protocols at a big savings of a factor of O(n3) (up to a log factor) over the best known error-correcting protocols. This is a new notion of fault-tolerant protocols, and is especially useful when malicious behavior is infrequent, since error-detection implies error-correction in this case.

REFERENCES

• 1: J. Bar-Ilan , D. Beaver, Non-cryptographic fault-tolerant computing in constant number of rounds of interaction, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.201-209, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72995]
• 2: R. Bar-Yehuda, B. Chor, and E. Kushilevitz, "Privacy, additional information, and communication," IEEE S#ructure in Complexity Theory 1990, pp. 55-65.
• 3: Donald Beaver, Multiparty protocols tolerating half faulty processors, Proceedings on Advances in cryptology, p.560-572, July 1989, Santa Barbara, California, United States
• 4: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 5: Donald Beaver , Joan Feigenbaum , Joe Kilian , Phillip Rogaway, Security with Low Communication Overhead, Proceedings of the 10th Annual International Cryptology Conference on Advances in Cryptology, p.62-76, August 11-15, 1990
• 6: 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]
• 7: 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]
• 8: B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, "Verifiable Secret Sharing" IEEE FOCS 1985, pp. 383-395.
• 9: D. Dolev, C. Dwork, O. Waarts, and M. Yung, "Secret Message Transmissions," IEEE FOCS 1990, pp. 36-45.
• 10: Tomàs Feder , Eyal Kushilevitz , Moni Naor, Amortized communication complexity (Preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.239-248, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185374]
• 11: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 12: E. Kushilevitz, "Privacy and communication complexity," IEEE FOCS 1989, pp. 416-421.
• 13: E. Kushilevitz, "On computing the sum privately," manuscript.
• 14: S. Micah and P. Rogaway, "Secure computation," Crypto 1991.
• 15: Alon Orlitsky , Abbas El Gamal, Communication with secrecy constraints, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.217-224, December 1984 [doi>10.1145/800057.808684]
• 16: T. Rabin , M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.73-85, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73014]
• 17: 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]
• 18: C. Small, Arithmetic of Finite Fields, Monographs and Textbooks in Pure and Applied Mathematics (Vol. 148), Marcel Dekker, Inc., New York, 1991.
• 19: A. Yao, "How to generate and exchange secrets," IEEE FOCS 1986, pp. 162-167.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Performance, Theory