**CNF-FSS and its Applications**

*Paul Bunn and Eyal Kushilevitz and Rafail Ostrovsky*

**Abstract: **Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai [BGI15],
extends the classical notion of secret-sharing 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 non-interactively compute an additive
sharing of f(x), for any input x in the domain of f. Previous work on FSS
concentrated mostly on the two-party 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 multi-party case, with p >= 3 parties and t-security (1 <= t < p). First, we introduce the notion of CNF-DPF (or, more generally, CNF-FSS), 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 CNF-DPF by providing several applications. Our main result shows how CNF-DPF 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 (semi-honest) corruptions. For example, we build a 2-out-of-5 secure (standard) DPF scheme of communication complexity O(N^{1/4}), where N is the domain size of f (compared with the current best-known 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 (p-1,p)-DPF scheme of [BGI15]).

We also present a 1-out-of-3 secure CNF-DPF scheme, in which each party holds two of the three keys, with poly-logarithmic communication complexity. These results have immediate implications to scenarios where (multi-server) 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 3-party protocol of [BKKO20].

**Category / Keywords: **foundations / secret sharing, replicated secret sharing (CNF), Function secret sharing

**Date: **received 14 Feb 2021, last revised 23 Dec 2021

**Contact author: **paul at stealthsoftwareinc com, eyalk at cs technion ac il, rafail at cs ucla edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20211223:215111 (All versions of this report)

**Short URL: **ia.cr/2021/163

[ Cryptology ePrint archive ]