Cryptology ePrint Archive: Report 2020/134

Malicious Security Comes Free in Honest-Majority MPC

Vipul Goyal and Yifan Song

Abstract: We study the communication complexity of unconditionally secure MPC over point-to-point channels for corruption threshold t < n/2. We ask the question: "is it possible to achieve security-with-abort with the same concrete cost as the best-known semi-honest MPC protocol?" While a number of works have focused on improving the concrete efficiency in this setting, the answer to the above question has remained elusive until now.

We resolve the above question in the affirmative by providing a secure-with-abort MPC protocol with the same cost per gate as the best-known semi-honest protocol. Concretely, our protocol only needs 5.5 field elements per multiplication gate per party which matches (and even improves upon) the corresponding cost of the best known protocol in the semi-honest setting by Damgard and Nielsen. Previously best-known maliciously secure (with abort) protocols require 12 field elements. An additional feature of our protocol is its conceptual simplicity. Our result is achieved by relying on a novel technique of verifying a batch of multiplication tuples.

Category / Keywords: applications / Multiparty Computation, Information-theoretic Cryptography, Communication Complexity

Date: received 7 Feb 2020, last revised 15 Feb 2020

Contact author: vipul at cmu edu,yifans2@andrew cmu edu

Available format(s): PDF | BibTeX Citation

Version: 20200216:003536 (All versions of this report)

Short URL: ia.cr/2020/134


[ Cryptology ePrint archive ]