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 large-scale 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 2-party DPF. We reduce the key size of the PRG-based 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 2-server PIR and related primitives.
- FSS for new function families. We present an efficient PRG-based 2-party 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 multi-dimensional 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.
Category / Keywords: foundations / function secret sharing, private information retrieval, secure multiparty computation, homomorphic encryption Original Publication (with major differences): ACM CCS 2016 Date: received 26 Jul 2018, last revised 2 Aug 2018 Contact author: gilboan at bgu ac il Available format(s): PDF | BibTeX Citation Note: Typo in keywords Version: 20180802:082349 (All versions of this report) Short URL: ia.cr/2018/707