Malicious Security Comes Free in Honest-Majority MPC

Vipul Goyal; Yifan Song

Paper 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.

Note: Merged with Report 2020/189 and Appeared in Crypto 2020

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint. MINOR revision.
Keywords: Multiparty Computation Information-theoretic Cryptography Communication Complexity
Contact author(s): vipul @ cmu edu
yifans2 @ andrew cmu edu
History: 2020-09-08: last of 2 revisions; 2020-02-10: received; See all versions
Short URL: https://ia.cr/2020/134
License: CC BY

BibTeX

@misc{cryptoeprint:2020/134,
      author = {Vipul Goyal and Yifan Song},
      title = {Malicious Security Comes Free in Honest-Majority {MPC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/134},
      year = {2020},
      url = {https://eprint.iacr.org/2020/134}
}