International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: CNF-FSS and its Applications

Paul Bunn , Stealth Software Technologies, Inc.
Eyal Kushilevitz , Technion
Rafail Ostrovsky , UCLA
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2022
Abstract: Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai~\cite{BGI15}, extends the classical notion of secret-sharing a \textit{value} to secret sharing a \textit{function}. Namely, for a secret function $f$ (from a class $\cal F$), FSS provides a sharing of $f$ whereby {\em 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 $\cal F$ (in particular, FSS for the class of point functions, a task referred to as DPF~--~Distributed Point Functions~\cite{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 \textsf{CNF-DPF} (or, more generally, \textsf{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 {\em 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 \cite{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~\cite{BKKO20}.
Video from PKC 2022
  title={CNF-FSS and its Applications},
  author={Paul Bunn and Eyal Kushilevitz and Rafail Ostrovsky},