Cryptology ePrint Archive: Report 2018/1161

Adaptively Secure MPC with Sublinear Communication Complexity

Ran Cohen and abhi shelat and Daniel Wichs

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) two-round secure function evaluation (SFE) protocol in the CRS model, assuming LWE and iO for circuits. The communication, the CRS size, and the online-computation are independent of 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 only depending on the witness size, and independent 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, assuming LWE and NIZK, with communication complexity only depending on the input and output of the parties. 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.

Category / Keywords: cryptographic protocols / secure multiparty computation, adaptive security, sublinear communication

Date: received 27 Nov 2018

Contact author: rancohen at ccs neu edu

Available format(s): PDF | BibTeX Citation

Version: 20181203:030206 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]