Single-server Multi-user Private Information Retrieval with Side Information
Single-server Multi-user Private Information Retrieval with Side Information
复制标题
带辅助信息的单服务器多用户隐私信息检索
DOI：
10.1109/isit.2018.8437545
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
M. Gastpar
中科院分区：
文献类型：
--
作者：
Su Li;M. Gastpar
在带边信息的私有信息检索问题中，单个用户希望恢复存储在一个或多个服务器上的$K$个独立消息中的一个。用户最初有一个消息子集作为辅助信息。用户的目标是在请求消息的索引不应被服务器推断的条件下，通过使用从服务器到用户的最小传输次数$（R^{\ast}）$来检索请求消息。我们将多用户变体引入到这个问题中，每个用户都希望检索一条消息，并将消息的子集作为边信息。在本文中，我们研究的特殊情况下，所有用户都希望从一个单一的服务器检索一个共同的消息，但每个用户有不同的边信息消息。我们表明，最佳的编码方案，可以通过第一次最佳划分的消息，然后分别在每个子集中的分区的消息生成MDS码。我们确定$R^{\ast}$，提出算法来计算$R^{\ast}$，并构造最佳的线性编码方案的复杂性多项式在$K$（但指数的边信息消息的数量）。
In the problem of private information retrieval with side information, a single user wants to recover one of the $K$ independent messages which are stored at one or multiple servers. The user initially has a subset of messages as side information. The goal of the user is to retrieve the demand message by using minimum number of transmissions $(R^{\ast})$ from the server(s) to the user under the condition that the index of the demand message should not be inferred by the server. We introduce the multi-user variant into this problem, where each user wants to retrieve one message and has a subset of messages as side information. In this paper, we study the special cases where all users want to retrieve one common message from a single server, but each user has different side information messages. We show that the optimal coding scheme can be constructed by first optimally partitioning the messages and then generating MDS codes separately in each subset of messages in the partition. We determine the $R^{\ast}$, propose algorithms to compute $R^{\ast}$, and construct optimal linear coding schemes with complexity polynomial in $K$ (but exponential in the number of side information messages).
影响因子：
2.5
作者：
Hua Sun;S. Jafar
通讯作者：
Hua Sun;S. Jafar