## Abstract

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/2^{K})^{-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)(11/(q^{K}-1/q-1)^{N-1}.

Original language | English (US) |
---|---|

Title of host publication | IWCIT 2018 - Iran Workshop on Communication and Information Theory |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1-6 |

Number of pages | 6 |

ISBN (Electronic) | 9781538641491 |

DOIs | |

State | Published - Jul 5 2018 |

Externally published | Yes |

Event | 2018 Iran Workshop on Communication and Information Theory, IWCIT 2018 - Tehran, Iran, Islamic Republic of Duration: Apr 25 2018 → Apr 26 2018 |

### Publication series

Name | IWCIT 2018 - Iran Workshop on Communication and Information Theory |
---|

### Conference

Conference | 2018 Iran Workshop on Communication and Information Theory, IWCIT 2018 |
---|---|

Country/Territory | Iran, Islamic Republic of |

City | Tehran |

Period | 4/25/18 → 4/26/18 |

### Bibliographical note

Publisher Copyright:© 2018 IEEE.

## Keywords

- private computing
- Private function retrieval
- private information retrieval
- secure distributed storage systems