In collaboration with IDC Herzliya + Technion and UCLA
Elette Boyle, Niv Gilboa and Yuval Ishai
ACM CCS 2016, pages 1292-1303, 2016
Function Secret Sharing (FSS), introduced by Boyle et al.(Eurocrypt 2015), provides a way for additively secret-sharinga 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 everystrict subset of the keys hides f. A Distributed Point Function(DPF) is a special case where F is the family of pointfunctions, namely functions fα,β that evaluate to β on theinput α and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases whileminimizing the amount of communication. These includedifferent flavors of private information retrieval (PIR), aswell as a recent application of DPF for large-scale anonymousmessaging. We improve and extend previous results in several ways:• Simplified FSS constructions. We introduce a tensoringoperation for FSS which is used to obtain a conceptuallysimpler derivation of previous constructionsand present our new constructions.• Improved 2-party DPF. We reduce the key size ofthe PRG-based DPF scheme of Boyle et al. roughlyby a factor of 4 and optimize its computational cost.The optimized DPF significantly improves the concretecosts of 2-server PIR and related primitives.• FSS for new function families. We present an ef-ficient PRG-based 2-party FSS scheme for the familyof decision trees, leaking only the topology of the treeand the internal node labels. We apply this towardsFSS for multi-dimensional intervals. We also presenta general technique for extending FSS schemes by increasingthe number of parties.• Verifiable FSS. We present efficient protocols for verifyingthat keys (k ∗ 1 , . . . , k∗ m), obtained from a potentiallymalicious user, are consistent with some f ∈ F.Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, orrepublish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org.CCS’16, October 24 – 28, 2016, Vienna, Austriac 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.ISBN 978-1-4503-4139-4/16/10. . . $15.00DOI: http://dx.doi.org/10.1145/2976749.2978429Such a verification may be critical for applications thatinvolve private writing or voting by many users.Keywords: Function secret sharing, private informationretrieval, secure multiparty computation, homomorphic encryption