International Association
for Cryptologic Research

Many information theoretically secure protocols are known for general secure multi-party computation, both in the honest majority setting, and in the dishonest majority setting with preprocessing. All known protocols that are efficient in the circuit size of the evaluated function follow the same typical ``gate-by-gate\'\' design pattern: we work our way through a boolean or arithmetic circuit, maintaining as an invariant that after we process a gate, the output of the gate is represented as a random secret sharing among the players. Finally, all shares for the outputs are revealed. This approach usually allows non-interactive processing of addition gates but requires communication for every multiplication gate.

This means that while information theoretically secure protocols are very efficient in terms of computational work, they (seem to) require more communication and more rounds than computationally secure protocols. Whether this is inherent is an open and probably very hard problem. However, in this work we show that it is indeed inherent for protocols that follow the ``gate by gate\'\' design pattern. In particular, we present the following results:

- In the honest majority setting, any gate-by-gate protocol must communicate for every multiplication gate, even if only semi-honest security is required.

- For dishonest majority with preprocessing, a different proof technique is needed. We again show that any gate-by-gate protocol must communicate for every multiplication gate when the underlying secret sharing scheme is the additive one. We obtain similar results for arbitrary secret sharing schemes.

- In the honest majority setting, we also show that amortising over several multiplication gates can at best save an O(n) factor on the computational work.

All our lower bounds are met up to a constant factor by known protocols that follow the typical gate-by-gate paradigm.

Our results imply that a fundamentally new approach must be found in order to improve the communication complexity of known protocols that are efficient in the circuit size of the function, such as GMW, SPDZ etc.