In this paper, we show, for the first time, an MPC protocol that can tolerate dishonest minority of malicious players that matches the communication complexity of the best known MPC protocol in the honest-but-curious setting. More specifically, we present a new n-player MPC protocol that is secure against a computationally-unbounded active and malicious adversary that can adaptively corrupt up to a minority t < n/2 of the players. For polynomially-large binary circuits that are not too unshaped, our protocol has an amortized communication complexity of O(n log n + k/n^c) bits per multiplication (i.e. AND) gate, where k denotes the security parameter and c is an arbitrary non-negative constant. This improves on the previously most efficient protocol with the same security guarantee, which offers an amortized communication complexity of O(n^2 k) bits per multiplication gate. For any k polynomial in n, the amortized communication complexity of our protocol matches the best known O(n log n) communication complexity of passive security MPC protocol. Thus, our result gives the first near-linear complexity of MPC (instead of quadratic) in the dishonest-minority setting and settles the question of the difference in communication complexity between the honest-but-curious and fully malicious settings. For sufficiently large circuits, our protocol can be improved only if the honest-but-curious protocol can be improved.
We introduce several novel techniques for reducing communication complexity of MPC in the malicious setting that are of independent interest and we believe will have wider applicability. One is a novel idea of computing authentication tags by means of a mini MPC, which allows us to avoid expensive double-sharings when dealing with malicious players; the other is a batch-wise multiplication verification that allows us to speedup Beaver's ``multiplication triples''. The techniques draw from the PCP world and this infusion of new techniques from other domains of computational complexity may find further uses in the context of MPC.Category / Keywords: cryptographic protocols / MPC Publication Info: Full version of CRYPTO 2012 article Date: received 21 Nov 2011, last revised 17 Aug 2012 Contact author: serge fehr at cwi nl Available format(s): PDF | BibTeX Citation Version: 20120817:191745 (All versions of this report) Short URL: ia.cr/2011/629 Discussion forum: Show discussion | Start new discussion