Linear Overhead Robust MPC with Honest Majority Using Preprocessing.

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 u003c n/2 in the pre-processing model. Surprisingly our protocol for robust share reconstruction withO(n) communication applies for both synchronous and asynchronous communication models. We go on to discuss implications for asynchronous variants of our resulting MPC protocol.