International Association
for Cryptologic Research

In this paper, we present an MPC protocol in the preprocessing model with essentially the same concrete online communication and rounds as the state-of-the-art MPC protocols such as online-BGW (with precomputed Beaver tuples) for $t < n/3$ malicious corruptions. However, our protocol additionally guarantees robustness and correctness against up to $t < n/2$ malicious corruptions while the privacy threshold remains at $n/3$. This is particularly useful in settings (e.g. commodity/stock market auctions, national elections, IACR elections) where it is paramount that the correct outcome is certified, while maintaining the best possible online speed. In addition, this honest-majority correctness allows us to use optimistic Berlekamp-Welch decoding in contrast to BGW. Moreover, just like online-BGW, our protocol is responsive until a final attestation phase.

We also give a complementary verifiable input-sharing scheme for the multi-client distributed-server setting which satisfies both robustness and correctness against up to $t < n/2$ malicious servers. This is accomplished by having the servers first run a preprocessing phase that does not involve the clients. The novelty of this input-sharing scheme is that a client only interacts for one round, and hence need not be online, which, again, is highly desirable in applications such as elections/auctions.

We prove our results in the universally-composable model with statistical security against static corruptions. Our protocol is achieved by combining global authenticators of SPDZ with an augmented Reed-Solomon code in a novel manner. This augmented code enables honest-majority decoding of degree $n/2$ Reed-Solomon codes. Our particular augmentation (often referred to as robust sharing) has the additional property that the preprocessing phase can generate this augmented sharing with a factor $n$ speedup over prior information-theoretic robust sharing schemes.