Paper 2018/707
Function Secret Sharing: Improvements and Extensions
Elette Boyle, Niv Gilboa, and Yuval Ishai
Abstract
Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secretsharing a function from a given function family $\mathcal F$. More concretely, an $m$party FSS scheme splits a function $f:\{0,1\}^n\to \mathbb G$, for some abelian group $\mathbb G$, into functions $f_1,\ldots,f_m$, described by keys $k_1,\ldots,k_m$, such that $f=f_1+\ldots+f_m$ and every strict subset of the keys hides $f$. A Distributed Point Function (DPF) is a special case where $\mathcal F$ is the family of point functions, namely functions $f_{\alpha,\beta}$ that evaluate to $\beta$ on the input $\alpha$ and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for largescale anonymous messaging. We improve and extend previous results in several ways:  Simplified FSS constructions. We introduce a tensoring operation for FSS which is used to obtain a conceptually simpler derivation of previous constructions and present our new constructions.  Improved 2party DPF. We reduce the key size of the PRGbased DPF scheme of Boyle et al. roughly by a factor of 4 and optimize its computational cost. The optimized DPF significantly improves the concrete costs of 2server PIR and related primitives.  FSS for new function families. We present an efficient PRGbased 2party FSS scheme for the family of decision trees, leaking only the topology of the tree and the internal node labels. We apply this towards FSS for multidimensional intervals. We also present a general technique for obtaining more expressive FSS schemes by increasing the number of parties.  Verifiable FSS. We present efficient protocols for verifying that keys $(k^*_1,\ldots,k^*_m)$, obtained from a potentially malicious user, are consistent with some $f\in\mathcal F$. Such a verification may be critical for applications that involve private writing or voting by many users.
Note: Typo in keywords
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. MAJOR revision.ACM CCS 2016
 Keywords
 function secret sharingprivate information retrievalsecure multiparty computationhomomorphic encryption
 Contact author(s)
 gilboan @ bgu ac il
 History
 20180802: revised
 20180801: received
 See all versions
 Short URL
 https://ia.cr/2018/707
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/707, author = {Elette Boyle and Niv Gilboa and Yuval Ishai}, title = {Function Secret Sharing: Improvements and Extensions}, howpublished = {Cryptology ePrint Archive, Paper 2018/707}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/707}}, url = {https://eprint.iacr.org/2018/707} }