The Capacity of Private Computation

By Hua Sun, Syed Ali Jafar. 2017

119 citations recorded by the source corpus.

We introduce the problem of private computation, comprised of <inline-formula> <tex-math notation="LaTeX">$ {N}$ </tex-math></inline-formula> distributed and non-colluding servers, <inline-formula> <tex-math notation="LaTeX">$ {K}$ </tex-math></inline-formula> independent datasets, and a user who wants to compute a function of the datasets privately, i.e., without revealing which function he wants to compute, to any individual server. This private computation problem is a strict generalization of the private information retrieval (PIR) problem, obtained by expanding the PIR message set (which consists of only independent messages) to also include functions of those messages. The capacity of private computation, <inline-formula> <tex-math notation="LaTeX">$ {C}$ </tex-math></inline-formula>, is defined as the maximum number of bits of the desired function that can be retrieved per bit of total download from all servers. We characterize the capacity of private computation, for <inline-formula> <tex-math notation="LaTeX">$ {N}$ </tex-math></inline-formula> servers and <inline-formula> <tex-math notation="LaTeX">$ {K}$ </tex-math></inline-formula> independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the capacity, <inline-formula> <tex-math notation="LaTeX">$ {C}=\left ({1+1/ {N}+\cdots +1/ {N}^{ {K}-1}}\right)^{-1}$ </tex-math></inline-formula>, matches the capacity of PIR with <inline-formula> <tex-math notation="LaTeX">$ {N}$ </tex-math></inline-formula> servers and <inline-formula> <tex-math notation="LaTeX">$ {K}$ </tex-math></inline-formula> messages. Thus, allowing arbitrary linear computations does not reduce the communication rate compared to pure dataset retrieval. The same insight is shown to hold even for arbitrary non-linear computations when the number of datasets <inline-formula> <tex-math notation="LaTeX">$ {K}\rightarrow \infty $ </tex-math></inline-formula>.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

On the Upload versus Download Cost for Secure and Private Matrix Multiplication (2019, background): “In particular, starting from the work of [13], private information retrieval (PIR) has been studied extensively within an information theoretic framework (such as PIR from coded databses [14] and private computation [15]–[18]).”
Private Computation of Systematically Encoded Data with Colluding Servers (2018, methodology): “In addition to generalizing the model of [11] from certain linear functions of the data vector to arbitrary functions, our model is perhaps simpler in 2018 IEEE International Symposium on Information Theory (ISIT)”
Private function retrieval (2017, background): “While the scheme of [13] is optimal, our proposed scheme has less complexity and is easier to implement.”
Achievable Rate of Private Function Retrieval from MDS Coded Databases (2018, methodology): “Then, the subroutine “M-Sym” [4] is used to generate side information to be exploited in the following blocks.”