Paper 2017/1248

Foundations of Homomorphic Secret Sharing

Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin, and Stefano Tessaro

Abstract

Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over a finite Abelian group. While strong feasibility results for HSS are known under specific cryptographic assumptions, many natural questions remain open. 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Major revision. ITCS 2018
Keywords
homomorphic secret sharingsecure computationcommunication complexityworst-case to average-case reductions
Contact author(s)
eboyle @ alum mit edu
History
2017-12-30: received
Short URL
https://ia.cr/2017/1248
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1248,
      author = {Elette Boyle and Niv Gilboa and Yuval Ishai and Huijia Lin and Stefano Tessaro},
      title = {Foundations of Homomorphic Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1248},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1248}},
      url = {https://eprint.iacr.org/2017/1248}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.