Semantic Private Information Retrieval
Semantic Private Information Retrieval
复制标题
DOI：
10.1109/tit.2021.3136583
复制
发表时间：
2020-03
影响因子：
2.5
通讯作者：
Sajani Vithana;Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Sajani Vithana;Karim A. Banawan;S. Ulukus
研究了语义私有信息检索问题。在语义PIR中，用户从存储在$N$个复制和非共谋数据库中的$K$个独立消息中检索消息，而不向任何单个数据库透露所需消息的身份。消息具有不同的语义，即，允许消息具有由$（p_{i}>0，i \in [K]）$表示的非均匀先验概率，其是它们各自的检索流行度的代理，以及任意消息大小$（L_{i}，i \in [K]）$。这是经典的私有信息检索（PIR）问题的推广，其中消息被假设为具有相等的消息大小。我们推导出一般的$K$，$N$的语义PIR容量。结果表明，语义PIR容量取决于数据库数N、消息数K、消息的先验概率分布p {i}$和消息大小L {i}$。我们提出了两个可实现的语义PIR计划：第一个是一个确定性的计划，这是基于消息不对称。该方案采用非均匀子分组化。第二种方案是概率性的，并且基于随机地从多个选项中选择一个查询集来检索所需的消息，而不需要指数子分组化。我们推导出的语义PIR容量超过经典PIR容量具有相同的先验和大小的必要和充分条件。我们的研究结果表明，语义PIR容量可以大于经典的PIR容量时，较长的消息具有较高的流行度。然而，当消息是等长的，非均匀的先验不能被利用来提高检索率超过经典的PIR容量。我们提供了两个扩展的语义PIR问题，即，语义PIR从MDS编码的数据库和语义PIR从勾结数据库。对于这两个扩展，我们推导出确切的PIR能力，除了提供相应的最佳方案。
We investigate the problem of semantic private information retrieval (semantic PIR). In semantic PIR, a user retrieves a message out of $K$ independent messages stored in $N$ replicated and non-colluding databases without revealing the identity of the desired message to any individual database. The messages come with different semantics, i.e., the messages are allowed to have non-uniform a priori probabilities denoted by $(p_{i}>0,\: i \in [K])$ , which are a proxy for their respective popularity of retrieval, and arbitrary message sizes $(L_{i},\: i \in [K])$ . This is a generalization of the classical private information retrieval (PIR) problem, where messages are assumed to have equal message sizes. We derive the semantic PIR capacity for general $K$ , $N$ . The results show that the semantic PIR capacity depends on the number of databases $N$ , the number of messages $K$ , the a priori probability distribution of messages $p_{i}$ , and the message sizes $L_{i}$ . We present two achievable semantic PIR schemes: The first one is a deterministic scheme which is based on message asymmetry. This scheme employs non-uniform subpacketization. The second scheme is probabilistic and is based on choosing one query set out of multiple options at random to retrieve the required message without the need for exponential subpacketization. We derive necessary and sufficient conditions for the semantic PIR capacity to exceed the classical PIR capacity with equal priors and sizes. Our results show that the semantic PIR capacity can be larger than the classical PIR capacity when longer messages have higher popularities. However, when messages are equal-length, the non-uniform priors cannot be exploited to improve the retrieval rate over the classical PIR capacity. We provide two extensions of the semantic PIR problem, namely, the semantic PIR from MDS-coded databases and the semantic PIR from colluding databases. For both extensions, we derive the exact PIR capacity in addition to providing a corresponding optimal scheme.