Paper 2011/629
NearLinear UnconditionallySecure Multiparty Computation with a Dishonest Minority
Eli BenSasson, Serge Fehr, and Rafail Ostrovsky
Abstract
Secure multiparty computation (MPC) allows a set of n players to compute any public function, given as an arithmetic circuit, on private inputs, so that privacy of the inputs as well as correctness of the output are guaranteed. Of special importance both in cryptography and in complexity theory is the setting of informationtheoretic MPC, where (dishonest) players are unbounded, and no cryptographic assumptions are used. In this setting, it was known since the 1980's that an honest majority of players is both necessary and sufficient to achieve privacy and correctness. The main open question that was left in this area is to establish the exact communication complexity of MPC protocols that can tolerate malicious behavior of a minority of dishonest players. In all works, there was a large gap between the communication complexity of the best known protocols in the malicious setting and the ``honestbutcurious'' setting, where players do not deviate from the protocol. 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 honestbutcurious setting. More specifically, we present a new nplayer MPC protocol that is secure against a computationallyunbounded active and malicious adversary that can adaptively corrupt up to a minority t < n/2 of the players. For polynomiallylarge 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 nonnegative 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 nearlinear complexity of MPC (instead of quadratic) in the dishonestminority setting and settles the question of the difference in communication complexity between the honestbutcurious and fully malicious settings. For sufficiently large circuits, our protocol can be improved only if the honestbutcurious 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 doublesharings when dealing with malicious players; the other is a batchwise 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.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. Full version of CRYPTO 2012 article
 Keywords
 MPC
 Contact author(s)
 serge fehr @ cwi nl
 History
 20120817: revised
 20111121: received
 See all versions
 Short URL
 https://ia.cr/2011/629
 License

CC BY
BibTeX
@misc{cryptoeprint:2011/629, author = {Eli BenSasson and Serge Fehr and Rafail Ostrovsky}, title = {NearLinear UnconditionallySecure Multiparty Computation with a Dishonest Minority}, howpublished = {Cryptology ePrint Archive, Paper 2011/629}, year = {2011}, note = {\url{https://eprint.iacr.org/2011/629}}, url = {https://eprint.iacr.org/2011/629} }