Linear Overhead Optimally-resilient Robust MPC Using Preprocessing

Ashish Choudhury, Emmanuela Orsini, Arpita Patra, Nigel Smart

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

1 Citation (Scopus)


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 Damgard 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.
Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks - SCN 2016
Subtitle of host publication10th International Conference, SCN 2016, Amalfi, Italy, August 31 – September 2, 2016, Proceedings
EditorsVassilis Zikas, Roberto De Prisco
Number of pages22
ISBN (Electronic)9783319446189
ISBN (Print)9783319446172
Publication statusPublished - 2016
Event10th Conference on Security and Cryptography for Networks - Hotel La Bussola, Amalfi, Italy
Duration: 31 Aug 20162 Sept 2016

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Conference10th Conference on Security and Cryptography for Networks
Abbreviated titleSCN 2016


Dive into the research topics of 'Linear Overhead Optimally-resilient Robust MPC Using Preprocessing'. Together they form a unique fingerprint.
  • IRIS - MPC

    Smart, N. P.


    Project: Research

  • COED - Computing on Encrypted Data

    Smart, N. P.


    Project: Research

Cite this