Function Secret Sharing: Improvements and Extensions

By Elette Boyle, Niv Gilboa, Yuval Ishai. 2016

417 citations recorded by the source corpus.

Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family F. More concretely, an m-party FSS scheme splits a function f : {0, 1}n -> G, for some abelian group G, into functions f1,...,fm, described by keys k1,...,km, such that f = f1 + ... + fm and every strict subset of the keys hides f. A Distributed Point Function (DPF) is a special case where F is the family of point functions, namely functions f_{a,b} that evaluate to b on the input a and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging. We improve and extend previous results in several ways: * Simplified FSS constructions. We introduce a tensoring operation for FSS which is used to obtain a conceptually simpler derivation of previous constructions and present our new constructions. * Improved 2-party DPF. We reduce the key size of the PRG-based DPF scheme of Boyle et al. roughly by a factor of 4 and optimize its computational cost. The optimized DPF significantly improves the concrete costs of 2-server PIR and related primitives. * FSS for new function families. We present an efficient PRG-based 2-party FSS scheme for the family of decision trees, leaking only the topology of the tree and the internal node labels. We apply this towards FSS for multi-dimensional intervals. We also present a general technique for extending FSS schemes by increasing the number of parties. * Verifiable FSS. We present efficient protocols for verifying that keys (k*/1,...,k*/m ), obtained from a potentially malicious user, are consistent with some f in F. Such a verification may be critical for applications that involve private writing or voting by many users.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Information Systems

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “[25] construct what we can view as a very efficient SNIP for a specific Valid function, in which the servers are semi-honest (“honest but curious”) [25].”
Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (2019, methodology): “A sequence of works [39, 17, 19] has led to highly efficient constructions of DPF schemes from any pseudorandom generator (PRG), which can be implemented in practice using block ciphers such as AES.”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “combine homomorphic encryption with generic MPC (Brickell et al., 2007; Huang et al., 2011c; Nikolaenko et al., 2013a; Nikolaenko et al., 2013b). The TASTY compiler (Henecka et al., 2010) provides a language for describing protocols involving both homomorphic encryption and garbled circuits. It comp”
End-to-end privacy preserving deep learning on multi-institutional medical imaging (2021, methodology): “In our recent work, we introduced AriaNN 26 , an SMPC protocol leveraging function secret sharing (FSS) 28 and building upon SPDZ 25 .”