Noisy Private Information Retrieval: On Separability of Channel Coding and Information Retrieval
Noisy Private Information Retrieval: On Separability of Channel Coding and Information Retrieval
复制标题
DOI：
10.1109/tit.2019.2935440
复制
发表时间：
2018-07
影响因子：
2.5
通讯作者：
Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Karim A. Banawan;S. Ulukus
我们考虑的问题，嘈杂的私人信息检索（NPIR）从$N$非通信数据库，每个存储相同的一组$M$消息。在这个模型中，答案字符串不是通过无噪声比特管道返回的，而是通过有噪声的无记忆通道返回的。我们的目的是在表征PIR容量为这个模型作为一个函数的统计信息措施的噪声信道，如熵和互信息。我们推导出一个一般的上限检索率的最大最小优化的形式。我们使用可实现的计划下的非对称交通约束和随机编码参数的PIR问题，推导出一个一般的下限检索率。对于$M=2$和$M=3$，对于任何$N$和任何噪声信道，上界和下界匹配。的下限和上限之间的分离信道编码和检索方案，除了从数据库中适应的业务比率。我们称之为几乎分离。接下来，我们考虑从多个访问通道（MAC-PIR）的私人信息检索问题。在MAC-PIR中，数据库响应通过以随机方式将响应混合在一起的多路访问信道（MAC）到达用户。我们发现，添加剂MAC和合取/析取MAC，信道编码和检索方案是不可分割的，不像在NPIR。我们发现，检索方案取决于MAC的属性，特别是在线性方面。对于这两种情况下，我们提供的计划，实现了充分的能力，没有任何损失，由于隐私约束，这意味着用户可以利用的性质，以提高隐私的渠道。最后，我们表明，完全无约束的能力并不总是可以通过确定的选择信道的容量。
We consider the problem of noisy private information retrieval (NPIR) from $N$ non-communicating databases, each storing the same set of $M$ messages. In this model, the answer strings are not returned through noiseless bit pipes, but rather through noisy memoryless channels. We aim at characterizing the PIR capacity for this model as a function of the statistical information measures of the noisy channels such as entropy and mutual information. We derive a general upper bound for the retrieval rate in the form of a max-min optimization. We use the achievable schemes for the PIR problem under asymmetric traffic constraints and random coding arguments to derive a general lower bound for the retrieval rate. The upper and lower bounds match for $M=2$ and $M=3$ , for any $N$ , and any noisy channel. The lower and upper bounds show a separation between channel coding and retrieval scheme except for adapting the traffic ratio from the databases. We refer to this as almost separation. Next, we consider the private information retrieval problem from multiple access channels (MAC-PIR). In MAC-PIR, the database responses reach the user through a multiple access channel (MAC) that mixes the responses together in a stochastic way. We show that for the additive MAC and the conjunction/disjunction MAC, channel coding and retrieval scheme are inseparable unlike in NPIR. We show that the retrieval scheme depends on the properties of the MAC, in particular on the linearity aspect. For both cases, we provide schemes that achieve the full capacity without any loss due to the privacy constraint, which implies that the user can exploit the nature of the channel to improve privacy. Finally, we show that the full unconstrained capacity is not always attainable by determining the capacity of the selection channel.