Private function retrieval

By Mahtab Mirmohseni, Mohammad Ali Maddah-Ali. 2017

77 citations recorded by the source corpus.

The widespread use of cloud computing services raises the question of how one can delegate the processing tasks to the untrusted distributed parties without breaching 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 maximum 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 = 1/2 (1-1/2K)−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 an achievable rate R = (1-1/N)(1+1/N-1/(qK-1/q-1)N-1.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

The Capacity of Private Computation (2017, background): “For this general case, our capacity characterization implies that the achievable scheme of [20] is strictly suboptimal.”
Achievable Rate of Private Function Retrieval from MDS Coded Databases (2018, background): “While this line of work, commonly known as private information retrieval (PIR), is concerned with downloading individual messages in a private manner from databases, a recently proposed generalization of this problem [3], [4] addresses the private computation of functions of these messages.”
Private Secure Coded Computation (2019, background): “There have been various works on PIR and its variations [11] - [14].”
Private Computation of Systematically Encoded Data with Colluding Servers (2018, background): “In [11], [13] the authors set K = 1 and consider a replication system with C = Rep(N)F, so each of N servers is storing a copy of X ∈ FM×1.”