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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
information theorysecret sharing
Contact author(s)
raskin @ mccme ru
History
2017-07-05: received
Short URL
https://ia.cr/2017/665
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/665,
      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{https://eprint.iacr.org/2017/665}},
      url = {https://eprint.iacr.org/2017/665}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.