Function Secret Sharing: Improvements and Extensions

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