Secure Private Information Retrieval from Colluding Databases with Eavesdroppers
Secure Private Information Retrieval from Colluding Databases with Eavesdroppers
复制标题
DOI：
10.1109/isit.2018.8437848
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Qiwen Wang;M. Skoglund
中科院分区：
文献类型：
--
作者：
Qiwen Wang;M. Skoglund
私有信息检索（PIR）的问题是从$N$个数据库中复制的$K$个消息中检索出一个消息，而不向数据库透露所需消息的身份。我们考虑的问题PIR与勾结的数据库和窃听，命名为ETPIR。具体来说，$N$个数据库中的任何$T$个数据库都可能串通，也就是说，它们可能会与用户进行交互，以猜测所请求消息的身份。窃听者很想知道消息的内容，可以窃听用户的任何$E$数据库的传入和传出传输。数据库共享一些窃听者和用户未知的公共随机性，并使用公共随机性来生成答案，使得窃听者无法获知关于$K$消息的任何信息。容量被定义为最大检索速率，即每个下载比特检索的所需消息的信息比特数。在我们以前的工作中，我们发现当$E\geq T$时，容量等于$1-\frac{E}{N}$。在这项工作中，我们专注于当$E\leq T$的情况下。我们发现一个外边界（匡威边界）和内边界（可扩展性）上的最佳可实现的速率。当消息数K趋于无穷大时，导出的内界和外界之间的差距消失。
The problem of private information retrieval (PIR) is to retrieve one message out of $K$ messages replicated at $N$ databases, without revealing the identity of the desired message to the databases. We consider the problem of PIR with colluding databases and eavesdroppers, named ETPIR. Specifically, any $T$ out of $N$ databases may collude, that is, they may communicate their interactions with the user to guess the identity of the requested message. An eavesdropper is curious to know the content of the messages and can tap in on the incoming and outgoing transmissions of any $E$ databases with the user. The databases share some common randomness unknown to the eavesdropper and the user, and use the common randomness to generate the answers, such that the eavesdropper can learn no information about the $K$ messages. The capacity is defined as the maximum retrieval rate, i.e. the number of information bits of the desired message retrieved per downloaded bit. In our previous work [1], we found that when $E\geq T$, the capacity equals $1-\frac{E}{N}$. In this work, we focus on the case when $E\leq T$. We find an outer bound (converse bound) and an inner bound (achievability) on the optimal achievable rate. The gap between the derived inner and outer bounds vanishes as the number of messages $K$ tends to infinity.