Paper 2021/163
CNFFSS and its Applications
Paul Bunn, Eyal Kushilevitz, and Rafail Ostrovsky
Abstract
Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai [BGI15], extends the classical notion of secretsharing a *value* to secret sharing a *function*. Namely, for a secret function f (from a class $F$), FSS provides a sharing of f whereby *succinct shares (``keys'') are distributed to a set of parties, so that later the parties can noninteractively compute an additive sharing of f(x), for any input x in the domain of f. Previous work on FSS concentrated mostly on the twoparty case, where highly efficient schemes are obtained for some simple, yet extremely useful, classes $F$ (in particular, FSS for the class of point functions, a task referred to as DPF  Distributed Point Functions [GI14,BGI15]. In this paper, we concentrate on the multiparty case, with p >= 3 parties and tsecurity (1 <= t < p). First, we introduce the notion of CNFDPF (or, more generally, CNFFSS), where the scheme uses the CNF version of secret sharing (rather than additive sharing) to share each value $f(x)$. We then demonstrate the utility of CNFDPF by providing several applications. Our main result shows how CNFDPF can be used to achieve substantial asymptotic improvement in communication complexity when using it as a building block for constructing *standard* (t,p)DPF protocols that tolerate t > 1 (semihonest) corruptions. For example, we build a 2outof5 secure (standard) DPF scheme of communication complexity O(N^{1/4}), where N is the domain size of f (compared with the current bestknown of O(N^{1/2}) for (2,5)DPF). More generally, with p > d*t parties, we give a (t,p)DPF whose complexity grows as O(N^{1/2d}) (rather than O(\sqrt{N}) that follows from the (p1,p)DPF scheme of [BGI15]). We also present a 1outof3 secure CNFDPF scheme, in which each party holds two of the three keys, with polylogarithmic communication complexity. These results have immediate implications to scenarios where (multiserver) DPF was shown to be applicable. For example, we show how to use such a scheme to obtain asymptotic improvement (O(\log^2N) versus O(\sqrt{N})) in communication complexity over the 3party protocol of [BKKO20].
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 secret sharingreplicated secret sharing (CNF)Function secret sharing
 Contact author(s)

paul @ stealthsoftwareinc com
eyalk @ cs technion ac il
rafail @ cs ucla edu  History
 20211223: last of 2 revisions
 20210217: received
 See all versions
 Short URL
 https://ia.cr/2021/163
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/163, author = {Paul Bunn and Eyal Kushilevitz and Rafail Ostrovsky}, title = {CNFFSS and its Applications}, howpublished = {Cryptology ePrint Archive, Paper 2021/163}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/163}}, url = {https://eprint.iacr.org/2021/163} }