Towards Efficient Information-Theoretic Function Secret Sharing

A $(t,r)$ -function secret sharing ( $(t,r)$ -FSS) scheme allows a dealer to secret-share a function $f$ among $r$ parties as $r$ secret keys $k_{1},\ldots,k_{r}$ such that for any input $x$ the parties can compute $r$ output shares that allow the reconstruction of $f(x)$ but any $\leq t$ of the parties cannot learn any information about $f$ . FSS schemes for point functions have been constructed under the name of distributed point functions (DPFs). The existing DPFs are computationally secure and based on the existence of PRGs or OWFs. As a result, the protocols where DPFs work as building blocks are computationally secure as well. In this paper, we study information-theoretically secure $(t,r)$ -FSS (called $(t,r)$ -itFSS) and propose a generic transformation from information-theoretic private information retrieval (PIR) schemes to itFSS schemes for point functions. We measure the efficiency of itFSS with its communication complexity, which can be defined as the total length of the secret keys and the output shares, maximized over the choices of $f$ and $x$ . By instantiating the generic transformation, we obtain $(t,r)$ -itFSS schemes for a variety of choices of $(t,r)$ , which have sublinear (in the functions’ domain size) communication complexity. How to make sure that the parties’ shares of $f(x)$ do not reveal more information than what needed to compute $f(x)$ is an interesting problem. An itFSS with this property is called function-private. In this paper, we also define a parameter called the mutual rate of itFSS in order to measure the amount of information that will be leaked by the parties’ output shares. We calculate the mutual rates for several specific itFSS schemes. We also define computational function privacy and propose a 2-party itFSS scheme with computational function privacy.