Paper 2014/105

Reducing the Overhead of MPC over a Large Population

Ashish Choudhury, Arpita Patra, and Nigel P. Smart


We present a secure honest majority MPC protocol, against a static adversary, which aims to reduce the communication cost in the situation where there are a large number of parties and the number of adversarially controlled parties is relatively small. Our goal is to reduce the usage of point-to-point channels among the parties, thus enabling them to run multiple different protocol executions. Our protocol has highly efficient theoretical communication cost when compared with other protocols in the literature; specifically the circuit-dependent communication cost, for circuits of suitably large depth, is $\Order(|\Circuit|\kappa^7)$, for security parameter $\kappa$~and circuit size $|\Circuit|$. Our protocol finds application in cloud computing scenario, where the fraction of corrupted parties is relatively small. By minimizing the usage of point-to-point channels, our protocol can enable a cloud service provider to run multiple MPC protocols.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.SCN 2014
Contact author(s)
partho31 @ gmail com
arpitapatra10 @ gmail com
nigel @ cs bris ac uk
2014-07-01: last of 2 revisions
2014-02-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ashish Choudhury and Arpita Patra and Nigel P.  Smart},
      title = {Reducing the Overhead of MPC over a Large Population},
      howpublished = {Cryptology ePrint Archive, Paper 2014/105},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.