The Capacity of Private Information Retrieval With Partially Known Private Side Information
The Capacity of Private Information Retrieval With Partially Known Private Side Information
复制标题
DOI：
10.1109/tit.2019.2936023
复制
发表时间：
2017-10
影响因子：
2.5
通讯作者：
Yi-Peng Wei;Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Yi-Peng Wei;Karim A. Banawan;S. Ulukus
我们考虑从$ n $复制的$ n $消息中的一条消息的私人信息检索（PIR）的问题以数据库部分已知的完整消息的形式。在此模型中，用户和数据库参与了两相方案，即，用户获取侧面信息以及用户下载所需信息的检索阶段的预取阶段。在预取阶段，用户从$ n $ th数据库中接收$ m_ {n} $完整消息，在缓存内存大小约束下$ \ sum _ {n = 1}^{n} m_ {n} m_ {n} \ leq m $。在检索阶段，用户希望检索一条消息（在其内存中不存在），以便没有单个数据库了解所需消息的身份的任何信息。此外，用户未从数据库预取的附带信息消息的身份必须在该数据库中保持私密。由于提供的数据库已知每个数据库提供的侧面信息，因此必须将侧面信息私有在其余数据库中，因此我们将此模型作为部分众所周知的私人侧面信息进行汇总。我们以部分已知的私人侧面信息为$ c = \ left（{1+ \ frac {1} {1} {n} {n}+\ cdots+\ frac {1} {n^n^{k-m-10}} } \ right）^{ - 1} = \ frac {1- \ frac {1} {n}} {1- \ left（{\ frac {1} {n}}}} \ right）^{k-m}} $。有趣的是，如果数据库都不知道任何预取的侧面信息，即当外部获得侧面信息时，这一结果是相同的。最近由Chen-Wang-Jafar定居。因此，我们的结果意味着，在预取阶段和检索阶段使用相同的数据库没有损失。
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 (retriever) of cache-size $M$ 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 where the user acquires side information and the retrieval phase where the user downloads desired information. In the prefetching phase, the user receives $m_{n}$ full messages from the $n$ th database, under the cache memory size constraint $\sum _{n=1}^{N} m_{n} \leq M$ . In the retrieval phase, the user wishes to retrieve a message (which is not present in its memory) 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=\left ({1+\frac {1}{N}+\cdots +\frac {1}{N^{K-M-1}}}\right)^{-1}=\frac {1-\frac {1}{N}}{1-\left({\frac {1}{N}}\right)^{K-M}}$ . Interestingly, this result is the same if none of the databases knows any of the prefetched side information, i.e., when the side information is obtained externally, a problem posed by Kadhe et al. and settled by Chen-Wang-Jafar recently. Thus, our result implies that there is no loss in using the same databases for both prefetching and retrieval phases.