Welcome to the resource topic for 2017/665
Title:
Lower bounds on communication for multiparty computation of multiple «AND» instances with secret sharing
Authors: 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.
ePrint: https://eprint.iacr.org/2017/665
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .