-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.Category / Keywords: cryptographic protocols / secure computation, information theoretic protocols, lower bounds Original Publication (with minor differences): IACR-CRYPTO-2016 Date: received 10 Nov 2015, last revised 7 Jun 2016 Contact author: antigoni at cs au dk Available format(s): PDF | BibTeX Citation 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).Version: 20160607:143327 (All versions of this report) Short URL: ia.cr/2015/1097 Discussion forum: Show discussion | Start new discussion