Cryptology ePrint Archive: Report 2015/705

Linear Overhead Robust MPC with Honest Majority Using Preprocessing

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

Abstract: We present a technique to achieve O(n) communication complexity per multiplication for a wide class of robust practical MPC protocols. Previously such a communication complexity was only known in the case of non-robust protocols in the full threshold, dishonest majority setting. In particular our technique applies to robust threshold computationally secure protocols in the case of t<n/2 in the pre-processing model. Surprisingly our protocol for robust share reconstruction with O(n) communication applies for both synchronous and asynchronous communication models. We go on to discuss implications for asynchronous variants of our resulting MPC protocol.

Category / Keywords: cryptographic protocols /

Date: received 13 Jul 2015

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

Available format(s): PDF | BibTeX Citation

Version: 20150714:044936 (All versions of this report)

Short URL: ia.cr/2015/705

Discussion forum: Show discussion | Start new discussion