Paper 2015/1097

On the Communication required for Unconditionally Secure Multiplication

Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou, and Michael Raskin

Abstract

Many information-theoretic secure protocols are known for general secure multi-party computation, 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 ''gate-by-gate'' design pattern: we work through an arithmetic (boolean) circuit on secret-shared inputs, such that after we process a gate, the output of the gate is represented as a random secret sharing among the players. This approach usually allows non-interactive processing of addition gates but requires communication for every multiplication gate. Thus, while information-theoretic 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. We present the following results: -In the honest majority setting, as well as for dishonest majority with preprocessing, any gate-by-gate protocol must communicate \Omega(n) bits for every multiplication gate, where n is the number of players. -In the honest majority setting, we show that one cannot obtain a bound that also grows with the field size. Moreover, for a constant number of players, amortizing over several multiplication gates does not allow us to save on the computational work, and - in a restricted setting - we show that this also holds for communication. 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, such as BGW, GMW, SPDZ etc.

Note: This version includes two observations. The first observation is a counterexample showing that one cannot hope to get a lower bound on the communication complexity of a multiplication gate protocol (MGP) that grows with the field size. This means that the bound we already had is optimal. The second observation is a lower bound on the communication complexity of an MGP for k parallel multiplications. The bound grows linearly with k and it holds for "sufficiently nice" secret sharing schemes, including all linear schemes. This confirms a conjecture we made in the previous version (modulo the fact that not all secret schemes are covered).