Cryptology ePrint Archive: Report 2015/705

Linear Overhead Optimally-resilient Robust MPC Using Preprocessing

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

Abstract: 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.

Category / Keywords: cryptographic protocols /

Original Publication (with major differences): SCN 2016

Date: received 13 Jul 2015, last revised 27 Jun 2016

Contact author: nigel at cs bris ac uk, arpitapatra10 at gmail com, partho31 at gmail com, Emmanuela Orsini at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20160627:124831 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]