In collaboration with IDC Herzliya + Technion and UCLA

Function Secret Sharing Improvements and Extensions

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-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α,β that evaluate to β on the
input α 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 ef-
ficient 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 ∈ F.
Permission to make digital or hard copies of all or part of this work for personal or
classroom use is granted without fee provided that copies are not made or distributed
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for components of this work owned by others than the
author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from
CCS’16, October 24 – 28, 2016, Vienna, Austria

c 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ISBN 978-1-4503-4139-4/16/10. . . $15.00
Such a verification may be critical for applications that
involve private writing or voting by many users.
Keywords: Function secret sharing, private information
retrieval, secure multiparty computation, homomorphic encryption