eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2015/1173

Secure Multiparty Computation with General Interaction Patterns

Shai Halevi, Yuval Ishai, Abhishek Jain, Eyal Kushilevitz, and Tal Rabin


We present a unified framework for studying secure multi-party computation (MPC) with *arbitrarily restricted interaction patterns*. Our study generalizes both standard MPC and recent models for MPC with specific restricted interaction patterns (such as a chain or a star), which were studied by Halevi et al. (Crypto 2011), Goldwasser et al. (Eurocrypt 2014), and Beimel et al. (Crypto 2014). Since restricted interaction patterns cannot always yield full security for MPC, we start by formalizing the notion of "best possible security" for any interaction pattern. We then obtain the following results: * Completeness theorem. We prove that the star interaction pattern is *complete* for the problem of MPC with general interaction patterns. * Positive results. We present both information-theoretic and computationally secure protocols for computing arbitrary functions with general interaction patterns. We also present more efficient protocols for computing symmetric functions and for computing arbitrary functions over a chain. * Negative results. We give evidence that our information-theoretic protocols for general functions will be hard to substantially improve on. All of our protocols rely on a correlated randomness setup, which is *necessary* for computing general functions in our setting. In the computational case, we also present a generic procedure to make any correlated randomness setup *reusable*, in the common random string model. Although most of our information-theoretic protocols have exponential complexity, they may be practical for functions on small domains (e.g., {0,1}^20), where they are concretely faster than their computational counterparts.

Available format(s)
Publication info
Published elsewhere. Major revision. The 7th Annual Innovations in Theoretical Computer Science, ITCS 2016
Secure multiparty computationInteractionsObfuscation
Contact author(s)
shaih @ alum mit edu
2015-12-08: received
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Yuval Ishai and Abhishek Jain and Eyal Kushilevitz and Tal Rabin},
      title = {Secure Multiparty Computation with General Interaction Patterns},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1173},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1173}},
      url = {https://eprint.iacr.org/2015/1173}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.