Private Sequential Function Computation
Private Sequential Function Computation
复制标题
DOI：
10.1109/isit.2019.8849524
复制
发表时间：
2019-07
期刊：
影响因子：
--
通讯作者：
B. Tahmasebi;M. Maddah-ali
中科院分区：
文献类型：
--
作者：
B. Tahmasebi;M. Maddah-ali
In this paper, we introduce the problem of private sequential function computation, where a user wishes to compute a composition of a sequence of K linear functions, in a specific order, for an arbitrary input. The user does not run these computations locally, rather it exploits the existence of N non-colluding servers, each can compute any of the K functions on any given input. However, the user does not want to reveal any information about the desired order of computations to the servers. For this problem, we study the capacity, defined as the supremum of the number of desired computations, normalized by the number of computations done at the servers, subject to the privacy constraint. In particular, we show that the capacity satisfies $\left( {1 - \frac{1}{N}} \right)/\left( {1 - \frac{1}{{\max \left( {K,N} \right)}}} \right) \leq C \leq 1$. For the achievability, we show that the user can retrieve the desired order of computations, by choosing a proper order of inquiries among different servers, while keeping the order of computations for each server fixed, irrespective of the desired order of computations.
In this paper, we introduce the problem of private sequential function computation, where a user wishes to compute a composition of a sequence of K linear functions, in a specific order, for an arbitrary input. The user does not run these computations locally, rather it exploits the existence of N non-colluding servers, each can compute any of the K functions on any given input. However, the user does not want to reveal any information about the desired order of computations to the servers. For this problem, we study the capacity, defined as the supremum of the number of desired computations, normalized by the number of computations done at the servers, subject to the privacy constraint. In particular, we show that the capacity satisfies $\left( {1 - \frac{1}{N}} \right)/\left( {1 - \frac{1}{{\max \left( {K,N} \right)}}} \right) \leq C \leq 1$. For the achievability, we show that the user can retrieve the desired order of computations, by choosing a proper order of inquiries among different servers, while keeping the order of computations for each server fixed, irrespective of the desired order of computations.