CNF-FSS and Its Applications
Paul Bunn, Eyal Kushilevitz, 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 \(\mathcal 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 \(\mathcal 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\ge 3\) parties and t-security (\(1\le 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 (of the p parties). 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>dt\) parties, we give a (t, p)-DPF whose communication grows as \(O(N^{1/2d})\) (rather than \(O(\sqrt{N})\) that follows from the \((p-1,p)\)-DPF scheme of [BGI15]). (We ignore here terms that depend on the number of parties, p, the security parameter, etc. See precise statements in the main body of the paper below)
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].
comment:
Public Key Cryptography (1) 2022: 283-314
Fetch PDF file of the paper