Paper 2018/913

Best Possible Information-Theoretic MPC

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


We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be ``best possible.'' Our new notion still requires full security against dishonest minority in the usual sense, but also requires a meaningful notion of information-theoretic security against dishonest majority. We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

Available format(s)
Publication info
Published by the IACR in TCC 2018
MPCInformation TheoreticBest possible security
Contact author(s)
talr @ us ibm com
2018-09-26: received
Short URL
Creative Commons Attribution


      author = {Shai Halevi and Yuval Ishai and Eyal Kushilevitz and Tal Rabin},
      title = {Best Possible Information-Theoretic MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2018/913},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.