Function secret sharing
Annual international conference on the theory and applications of …, 2015•Springer
Motivated by the goal of securely searching and updating distributed data, we introduce and
study the notion of function secret sharing (FSS). This new notion is a natural generalization
of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and
Ishai (Eurocrypt 2014). Given a positive integer p ≥ 2 and a class\mathcal F of functions f:{0,
1\}^ n →\mathbb G, where\mathbb G is an Abelian group, a p-party FSS scheme for\mathcal
F allows one to split each f ∈\mathcal F into p succinctly described functions f_i:{0, 1\}^ n …
study the notion of function secret sharing (FSS). This new notion is a natural generalization
of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and
Ishai (Eurocrypt 2014). Given a positive integer p ≥ 2 and a class\mathcal F of functions f:{0,
1\}^ n →\mathbb G, where\mathbb G is an Abelian group, a p-party FSS scheme for\mathcal
F allows one to split each f ∈\mathcal F into p succinctly described functions f_i:{0, 1\}^ n …
Abstract
Motivated by the goal of securely searching and updating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer and a class of functions , where is an Abelian group, a -party FSS scheme for allows one to split each into succinctly described functions , , such that: (1) , and (2) any strict subset of the hides . Thus, an FSS for can be thought of as method for succinctly performing an “additive secret sharing” of functions from . The original definition of DPF coincides with a two-party FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input.
We present two types of results. First, we obtain efficiency improvements and extensions of the original DPF construction. Then, we initiate a systematic study of general FSS, providing some constructions and establishing relations with other cryptographic primitives. More concretely, we obtain the following main results:
- Improved DPF. We present an improved (two-party) DPF construction from a pseudorandom generator (PRG), reducing the length of the key describing each from to , where is the PRG seed length.
- Multi-party DPF. We present the first nontrivial construction of a -party DPF for , obtaining a near-quadratic improvement over a naive construction that additively shares the truth-table of . This constrcution too can be based on any PRG.
- FSS for simple functions. We present efficient PRG-based FSS constructions for natural function classes that extend point functions, including interval functions and partial matching functions.
- A study of general FSS. We show several relations between general FSS and other cryptographic primitives. These include a construction of general FSS via obfuscation, an indication for the implausibility of constructing general FSS from weak cryptographic assumptions such as the existence of one-way functions, a completeness result, and a relation with pseudorandom functions.
Springer