Paper 2017/665

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

Michael Raskin


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
information theorysecret sharing
Contact author(s)
raskin @ mccme ru
2017-07-05: received
Short URL
Creative Commons Attribution


      author = {Michael Raskin},
      title = {Lower bounds on communication for multiparty computation of multiple «AND» instances with secret sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2017/665},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.