| Abstract: |
The problem of reliable/secure all-to-all communication over low-degree networks has been
essential for communication-local (CL) n-party MPC (i.e., MPC protocols where every party directly
communicates only with a few, typically polylogarithmic in n, parties) and more recently for com-
munication over ad hoc networks, which are used in blockchain protocols. However, a limited number
of adaptively secure solutions exist, and they all make relatively strong assumptions on the ability of
parties to act in some specific manner before the adversary can corrupt them. Two such assumptions
were made in the work of Chandran et al. [ITCS ’15]---parties can (a) multisend messages to several
receivers simultaneously; and (b) securely erase the message and the identities of the receivers, before the adversary gets a chance to corrupt the sender (even if a receiver is corrupted).
A natural question to ask is: Are these assumptions necessary for adaptively secure CL MPC? In this
paper, we characterize the feasibility landscape for all-to-all reliable message transmission (RMT) under these two assumptions, and use this characterization to obtain (asymptotically) tight feasibility results for CL MPC.
– First, we prove a strong impossibility result for a broad class of RMT protocols, termed here
store-and-forward protocols, which includes all known communication protocols for CL MPC from
standard cryptographic assumptions. Concretely, we show that no such protocol with a certain
expansion rate can tolerate a constant fraction of parties being corrupted.
– Next, under the assumption of only a PKI, we show that assuming secure erasures, we can obtain
an RMT protocol between all pairs of parties with polylogarithmic locality (even without assuming
multisend) for the honest majority setting. We complement this result by showing a negative result
for the setting of dishonest majority.
– Finally, and somewhat surprisingly, under stronger assumptions (i.e., trapdoor permutations
with a reverse domain sampler, and compact and malicious circuit-private FHE), we construct a
polylogarithmic-locality all-to-one RMT protocol, which is adaptively secure and tolerates any
constant fraction of corruptions, without assuming either secure erasures or multisend. This last
result uses a novel combination of adaptively secure (e.g., non-committing) encryption and (static)
FHE to bypass the impossibility of compact adaptively secure FHE by Katz et al. [PKC’13], which
we believe may be of independent interest. Intriguingly, even such assumptions do not allow reduc-
ing all-to-all RMT to all-to-one RMT (a reduction which is trivial in the non-CL setting). Still, we
can implement what we call sublinear output-set RMT (SOS-RMT for short). We show how SOS-
RMT can be used for SOS-MPC under the known bounds for feasibility of MPC in the standard
(i.e., non-CL) setting assuming, in addition to SOS-RMT, an anonymous PKI. |
