Paper 2017/665

Lower bounds on communication for multiparty computation of multiple «AND» instances with secret sharing

Michael Raskin

Abstract

The present report contains a proof of a linear lower bound for a typical three-party secure computation scheme of $n$ independent $AND$ functions. The goal is to prove some linear communication lower bound for a maximally broad definition of «typical». The article [DNPR] contains various communications lower bounds for unconditionally secure multiparty computation. In particular, it contains a linear lower bound for communication complexity of a regular parallel multiplication protocol using an ideal secret sharing scheme. These conditions mean that the protocol starts with the input being secret-shared with each share of each input field element being a field element, all combinations are used, and the output is shared in the same way as input. In this report a weaker property of the secret sharing scheme that still allows to prove a linear (w.r.t. the number of multiplications) lower bound on communication is presented. Namely, if we have two (out of three) sides and two options for each party's shares and three possible combinations decode as the same value, the remaining combination should also be a valid pair of shares and reveal the same value.