论文标题
带有个人和联合隐私的私人计算
Private Computation with Individual and Joint Privacy
论文作者
论文摘要
本文在存在侧面信息（SI）的情况下考虑了单服务器私人计算（PC）的问题。在此问题中，有一台服务器存储$ k $ i.i.d。消息，以及具有$ M $未编码的消息子集的用户或将其作为侧面信息的编码线性组合，服务器的这些消息的身份是未知的。用户希望私下计算（通过从服务器下载信息）的线性组合，该子集的其他消息的其他消息，其中这些消息的身份必须单独或共同保存。对于每种设置，我们将容量定义为所有可实现的下载率的至高无上。 对于所有$ k，m，d $，我们在需要单个隐私时用编码和未编码的SI来表征PC的容量。我们的结果表明，这两个设置具有相同的容量。此外，当需要联合隐私时，我们在PC的容量上建立了一个非平凡的下限，对于一系列参数$ k，m，d $。该下限与我们先前在需要联合隐私时未编码的SI的PC的能力上建立的下边界相同。
This paper considers the problem of single-server Private Computation (PC) in the presence of Side Information (SI). In this problem, there is a server that stores $K$ i.i.d. messages, and a user who has a subset of $M$ uncoded messages or a coded linear combination of them as side information, where the identities of these messages are unknown to the server. The user wants to privately compute (via downloading information from the server) a linear combination of a subset of $D$ other messages, where the identities of these messages must be kept private individually or jointly. For each setting, we define the capacity as the supremum of all achievable download rates. We characterize the capacity of both PC with coded and uncoded SI when individual privacy is required, for all $K, M, D$. Our results indicate that both settings have the same capacity. In addition, we establish a non-trivial lower bound on the capacity of PC with coded SI when joint privacy is required, for a range of parameters $K, M, D$. This lower bound is the same as the lower bound we previously established on the capacity of PC with uncoded SI when joint privacy is required.
