Multi-message private information retrieval
Multi-message private information retrieval
复制标题
DOI：
10.1109/isit.2017.8006859
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Karim A. Banawan;S. Ulukus
研究了N个非通信复制数据库中多消息私有信息检索问题。在MPIR中，用户感兴趣的是从M个存储的消息中检索P个消息，而不泄露检索到的消息的身份。MPIR CP的信息理论总和容量是每个下载符号可以私下检索的期望消息符号的最大数量。当P ≥ M/2时，我们确定MPIR的精确容量和为CP =1/1+M-P/PN。当P≤M/2时，我们给出了所有M，P，N的上下界。如果消息数M是所需消息数P的整数倍，则这些边界匹配，在这种情况下，CP = 1 - 1 N/1-（1/N）M/P。我们的结果表明，联合检索所需消息比连续使用单消息检索方案更有效。
We consider the problem of multi-message private information retrieval (MPIR) from N non-communicating replicated databases. In MPIR, the user is interested in retrieving P messages out of M stored messages without leaking the identity of the retrieved messages. The information-theoretic sum capacity of MPIR CP is the maximum number of desired message symbols that can be retrieved privately per downloaded symbol. For the case P ≥ M/2, we determine the exact sum capacity of MPIR as CPs=1/1+M-P/PN For P≤M/2, we develop lower and upper bounds for all M, P, N. These bounds match if the number of messages M is an integer multiple of the number of desired messages P, in which case, CPs = 1−1N/1−(1/N)M/P. Our results indicate that joint retrieval of desired messages is more efficient than successive use of single-message retrieval schemes.