The Price of Low Communication in Secure Multi-Party Computation

Juan Garay, Yuval Ishai, Rafail Ostrovsky, Vasileios Zikas

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Traditional protocols for secure multi-party computation among n parties communicate at least a linear (in n) number of bits, even when computing very simple functions. In this work we investigate the feasibility of protocols with sublinear communication complexity. Concretely, we consider two clients, one of which may be corrupted, who wish to perform some “small” joint computation using n servers but without any trusted setup. We show that enforcing sublinear communication complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated in the setting of information-theoretic security.
We provide a complete investigation of security in the presence of semi-honest adversaries—static and adaptive, with and without erasures—and initiate the study of security in the presence of malicious adversaries. For semi-honest static adversaries, our bounds essentially match the corresponding bounds when there is no communication restriction—i.e., we can tolerate up tot < (1/2−ε)n corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures even a small constant fraction of corruptions is intolerable, and—more surprisingly—when erasures are allowed, we prove that
t < (1 −√0.5 − ε)n corruptions can be tolerated, which we also show to be essentially optimal. The latter optimality proof hinges on a new treatment of probabilistic adversary structures that may be of independent interest. In the case of active corruptions in the sublinear communication setting, we prove that static “security with abort” is feasible when t < (1/2 − ε)n, namely, the bound
that is tight for semi-honest security. All of our negative results in fact rule out protocols with sublinear message complexity.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2017
Number of pages30
ISBN (Electronic)978-3-319-63688-7
ISBN (Print)978-3-319-63687-0
Publication statusPublished - 29 Jul 2017
EventCRYPTO 2017: 37th Annual International Cryptology Conference - University of California, Santa Barbara, Santa Barbara, United States
Duration: 20 Aug 201624 Aug 2017

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceCRYPTO 2017
Abbreviated titleCRYPTO 2017
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'The Price of Low Communication in Secure Multi-Party Computation'. Together they form a unique fingerprint.

Cite this