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 2017/871

Non-Interactive Multiparty Computation without Correlated Randomness

Shai Halevi, Yuval Ishai, Abhishek Jain, Ilan Komargodski, Amit Sahai, and Eylon Yogev


We study the problem of non-interactive multiparty computation (NI-MPC) where a group of completely asynchronous parties can evaluate a function over their joint inputs by sending a single message to an evaluator who computes the output. Previously, the only general solutions to this problem that resisted collusions between the evaluator and a set of parties were based on multi-input functional encryption and required the use of complex correlated randomness setup. In this work, we present a new solution for NI-MPC against arbitrary collusions using a public-key infrastructure (PKI) setup supplemented with a common random string. A PKI is, in fact, the minimal setup that one can hope for in this model in order to achieve a meaningful ``best possible'' notion of security, namely, that an adversary that corrupts the evaluator and an arbitrary set of parties only learns the residual function obtained by restricting the function to the inputs of the uncorrupted parties. Our solution is based on indistinguishability obfuscation and DDH both with sub-exponential security. We extend this main result to the case of general interaction patterns, providing the above best possible security that is achievable for the given interaction. Our main result gives rise to a novel notion of (public-key) multiparty obfuscation, where $n$ parties can independently obfuscate program modules $M_i$ such that the obfuscated modules, when put together, exhibit the functionality of the program obtained by ``combining'' the underlying modules $M_i$. This notion may be of independent interest.

Available format(s)
Publication info
A minor revision of an IACR publication in ASIACRYPT 2017
secure multiparty computationnon-interactiveindistinguishability obfuscation
Contact author(s)
komargodski @ cornell edu
2017-09-13: received
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Yuval Ishai and Abhishek Jain and Ilan Komargodski and Amit Sahai and Eylon Yogev},
      title = {Non-Interactive Multiparty Computation without Correlated Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2017/871},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/871}},
      url = {https://eprint.iacr.org/2017/871}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.