Paper 2018/1161

Adaptively Secure MPC with Sublinear Communication Complexity

Ran Cohen, Reichman University
abhi shelat, Northeastern University
Daniel Wichs, Northeastern University and NTT Research
Abstract

A central challenge in the study of MPC is to balance between security guarantees, hardness assumptions, and resources required for the protocol. In this work, we study the cost of tolerating adaptive corruptions in MPC protocols under various corruption thresholds. In the strongest setting, we consider adaptive corruptions of an arbitrary number of parties (potentially all) and achieve the following results: (1) A two-round secure function evaluation (SFE) protocol in the CRS model, assuming LWE and indistinguishability obfuscation (iO). The communication, the CRS size, and the online-computation are sublinear in the size of the function. The iO assumption can be replaced by secure erasures. Previous results required either the communication or the CRS size to be polynomial in the function size. (2) Under the same assumptions, we construct a "Bob-optimized" 2PC (where Alice talks first, Bob second, and Alice learns the output). That is, the communication complexity and total computation of Bob are sublinear in the function size and in Alice's input size. We prove impossibility of "Alice-optimized" protocols. (3) Assuming LWE, we bootstrap adaptively secure NIZK arguments to achieve proof size sublinear in the circuit size of the NP-relation. On a technical level, our results are based on laconic function evaluation (LFE) (Quach, Wee, and Wichs, FOCS'18) and shed light on an interesting duality between LFE and FHE. Next, we analyze adaptive corruptions of all-but-one of the parties and show a two-round SFE protocol in the threshold-PKI model (where keys of a threshold FHE scheme are pre-shared among the parties) with communication complexity sublinear in the circuit size, assuming LWE and NIZK. Finally, we consider the honest-majority setting, and show a two-round SFE protocol with guaranteed output delivery under the same constraints. Our results highlight that the asymptotic cost of adaptive security can be reduced to be comparable to, and in many settings almost match, that of static security, with only a little sacrifice to the concrete round complexity and asymptotic communication complexity.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2019
Keywords
secure multiparty computationadaptive securitysublinear communication
Contact author(s)
rancoen @ gmail com
abhi @ neu edu
wichs @ ccs neu edu
History
2023-02-14: last of 9 revisions
2018-12-03: received
See all versions
Short URL
https://ia.cr/2018/1161
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1161,
      author = {Ran Cohen and abhi shelat and Daniel Wichs},
      title = {Adaptively Secure MPC with Sublinear Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1161},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1161}},
      url = {https://eprint.iacr.org/2018/1161}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.