We initiate a systematic study of HSS, making the following contributions.
* A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework.
* Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer.
* Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.
Category / Keywords: foundations / homomorphic secret sharing, secure computation, communication complexity, worst-case to average-case reductions Original Publication (with major differences): ITCS 2018 Date: received 27 Dec 2017 Contact author: eboyle at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20171230:180600 (All versions of this report) Short URL: ia.cr/2017/1248 Discussion forum: Show discussion | Start new discussion