Private information retrieval with partially known private side information
Private information retrieval with partially known private side information
复制标题
DOI：
10.1109/ciss.2018.8362308
复制
发表时间：
2018-03
期刊：
影响因子：
--
通讯作者：
Yi-Peng Wei;Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Yi-Peng Wei;Karim A. Banawan;S. Ulukus
我们认为一个单一的消息从N个复制和非串通数据库中的K个消息的私人信息检索（PIR）的问题，其中一个缓存启用用户的缓存大小的M个消息拥有侧信息的形式是部分已知的数据库的完整的消息。在这个模型中，用户和数据库参与一个两阶段的计划，即预取阶段和检索阶段。在预取阶段，用户从第n个数据库接收mn个完整的消息，该高速缓存大小约束下，Nn=1 mn ≤ M。在检索阶段，用户希望检索一条消息，使得没有任何单独的数据库了解所需消息的身份。此外，用户没有从数据库预取的辅助信息消息的身份必须相对于该数据库保持私有。由于在预取阶段由每个数据库提供的侧信息是已知的提供数据库和侧信息必须保持私有对其余的数据库，我们硬币这个模型作为部分已知的私有侧信息。我们将具有部分已知的私有侧信息的PIR的容量表征为C =（1 + 1/N +...+1/NK-M-1）−1 = 1−1/N/1-（1/N）K-M，如果没有数据库知道任何预取的侧信息，则这是相同的。因此，我们的结果意味着，在预取和检索阶段使用相同的数据库没有损失。
We consider the problem of private information retrieval (PIR) of a single message out of K messages from N replicated and non-colluding databases where a cache-enabled user of cache-size M messages possesses side information in the form of full messages that are partially known to the databases. In this model, the user and the databases engage in a two-phase scheme, namely, the prefetching phase and the retrieval phase. In the prefetching phase, the user receives mn full messages from the nth database, under the cache memory size constraint ΣNn=1 mn ≤ M. In the retrieval phase, the user wishes to retrieve a message such that no individual database learns anything about the identity of the desired message. In addition, the identities of the side information messages that the user did not prefetch from a database must remain private against that database. Since the side information provided by each database in the prefetching phase is known by the providing database and the side information must be kept private against the remaining databases, we coin this model as partially known private side information. We characterize the capacity of the PIR with partially known private side information to be C = (1 + 1/N +…+1/NK−M−1)−1 = 1−1/N/1−(1/N)K−M, which is the same if none of the databases knows any of the prefetched side information. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases.