Private Function Retrieval

The widespread use of cloud computing services raises the question of how one can delegate the processing tasks to the untrusted distributed parties without breeching the privacy of its data and algorithms. Motivated by the algorithm privacy concerns in a distributed computing system, in this paper, we introduce the private function retrieval (PFR) problem, where a user wishes to efficiently retrieve a linear function of K messages from N non-communicating replicated servers while keeping the function hidden from each individual server. The goal is to find a scheme with minimum communication cost. To characterize the fundamental limits of the communication cost, we define the capacity of PFR problem as the size of the message that can be privately retrieved (which is the size of one file) normalized to the required downloaded information bits. We first show that for the PFR problem with K messages, N=2 servers and a linear function with binary coefficients the capacity is C=frac12Big(1-frac12KBig)-1. Interestingly, this is the capacity of retrieving one of K messages from N=2 servers while keeping the index of the requested message hidden from each individual server, the problem known as private information retrieval (PIR). Then, we extend the proposed achievable scheme to the case of arbitrary number of servers and coefficients in the field GF(q) with arbitrary q and obtain R=Big(1-frac1NBig)Big(1+fracfrac1N-1(fracqK-1q-1)N-1Big).