The Capacity of Private Computation
The Capacity of Private Computation
复制标题
DOI：
10.1109/tit.2018.2888494
复制
发表时间：
2017-10
影响因子：
2.5
通讯作者：
Hua Sun;S. Jafar
中科院分区：
文献类型：
--
作者：
Hua Sun;S. Jafar
我们引入了私有计算的问题，包括$ {N}$分布式和非串通的服务器，$ {K}$独立的数据集，以及想要私下计算数据集函数的用户，即不向任何单独的服务器透露他想要计算的函数。该私有计算问题是私有信息检索（PIR）问题的严格推广，通过扩展PIR消息集（仅由独立消息组成）来包含这些消息的函数。私有计算的容量$ {C}$被定义为从所有服务器的总下载中每比特可以检索所需函数的最大位数。我们描述了在每个服务器上复制的$ {N}$服务器和$ {K}$独立数据集的私有计算能力，当要计算的函数是数据集的任意线性组合时。令人惊讶的是，容量$ {C}=\left ({1+1/ {N}+\cdots +1/ {N}^{ {K}-1}}\right)^{-1}$与具有$ {N}$服务器和$ {K}$消息的PIR的容量相匹配。因此，与纯数据集检索相比，允许任意线性计算并不会降低通信速率。当数据集的数量为$ {K}\rightarrow \infty $时，同样的见解甚至适用于任意非线性计算。
We introduce the problem of private computation, comprised of $ {N}$ distributed and non-colluding servers, $ {K}$ 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, $ {C}$ , 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 $ {N}$ servers and $ {K}$ independent datasets that are replicated at each server, when the functions to be computed are arbitrary linear combinations of the datasets. Surprisingly, the capacity, $ {C}=\left ({1+1/ {N}+\cdots +1/ {N}^{ {K}-1}}\right)^{-1}$ , matches the capacity of PIR with $ {N}$ servers and $ {K}$ 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 $ {K}\rightarrow \infty $ .