Paper 2015/705

Linear Overhead Optimally-resilient Robust MPC Using Preprocessing

Ashish Choudhury, Emmanuela Orsini, Arpita Patra, and Nigel P. Smart


We present a new technique for robust secret reconstruction with $O(n)$ communication complexity. By applying this technique, we achieve $O(n)$ communication complexity per multiplication for a wide class of robust practical Multi-Party Computation (MPC) protocols. In particular our technique applies to robust threshold computationally secure protocols in the case of $t<n/2$ in the pre-processing model. Previously in the pre-processing model, $O(n)$ communication complexity per multiplication was only known in the case of computationally secure non-robust protocols in the dishonest majority setting (i.e. with $t<n$) and in the case of perfectly-secure robust protocols with $t<n/3$. A similar protocol was sketched by Damgård and Nielsen, but no details were given to enable an estimate of the communication complexity. Surprisingly our robust reconstruction protocol applies for both the synchronous and asynchronous settings.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. SCN 2016
Contact author(s)
nigel @ cs bris ac uk
arpitapatra10 @ gmail com
partho31 @ gmail com
Emmanuela Orsini @ bristol ac uk
2016-06-27: last of 2 revisions
2015-07-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ashish Choudhury and Emmanuela Orsini and Arpita Patra and Nigel P.  Smart},
      title = {Linear Overhead Optimally-resilient Robust MPC Using Preprocessing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/705},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.