Multiround Private Information Retrieval: Capacity and Storage Overhead
Multiround Private Information Retrieval: Capacity and Storage Overhead
复制标题
DOI：
10.1109/tit.2018.2789426
复制
发表时间：
2016-11
影响因子：
2.5
通讯作者：
Hua Sun;S. Jafar
中科院分区：
文献类型：
--
作者：
Hua Sun;S. Jafar
私有信息检索（PIR）是指从$N$非通信复制数据库（其中每个数据库存储所有$K$消息）中的$K$消息中检索一条消息的问题，以这样一种方式，每个数据库不了解正在检索的消息的信息。PIR的容量是指在所有PIR方案中，每下载一个比特信息所需要的最大比特数。该能力最近被描述为PIR及其几种变体。在每种情况下，都假设所有查询都是由用户同时生成的。这里我们考虑多轮PIR，其中允许每轮查询依赖于前几轮收到的答案。我们证明了多轮PIR的容量与单轮PIR的容量相同。结果被推广到还包括$T$隐私约束。结合先前的结果，这表明多轮方案比单轮方案、非线性方案比线性方案或$\epsilon $ -error方案比零误差方案没有容量优势。但是，我们将通过一个示例说明在存储开销方面的优势。我们提供了一个多轮、非线性、$\epsilon $ -error PIR方案的例子，它比单轮、线性、零错误PIR方案需要更小的存储开销。
Private information retrieval (PIR) is the problem of retrieving one message out of $K$ messages from $N$ non-communicating replicated databases, where each database stores all $K$ messages, in such a way that each database learns no information about which message is being retrieved. The capacity of PIR is the maximum number of bits of desired information per bit of downloaded information among all PIR schemes. The capacity has recently been characterized for PIR as well as several of its variants. In every case it is assumed that all the queries are generated by the user simultaneously. Here we consider multiround PIR, where the queries in each round are allowed to depend on the answers received in previous rounds. We show that the capacity of multiround PIR is the same as the capacity of single-round PIR. The result is generalized to also include $T$ -privacy constraints. Combined with previous results, this shows that there is no capacity advantage from multiround over single-round schemes, non-linear over linear schemes or from $\epsilon $ -error over zero-error schemes. However, we show through an example that there is an advantage in terms of storage overhead. We provide an example of a multiround, non-linear, $\epsilon $ -error PIR scheme that requires a strictly smaller storage overhead than the best possible with single-round, linear, zero-error PIR schemes.