Multiround Private Information Retrieval: Capacity and Storage Overhead

被引:46
作者
Sun, Hua [1 ]
Jafar, Syed Ali [2 ]
机构
[1] Univ North Texas, Dept Elect Engn, Denton, TX 76203 USA
[2] Univ Calif Irvine, Ctr Pervas Commun & Comp, Dept Elect Engn & Comp Sci, Irvine, CA 92697 USA
关键词
Private information retrieval; multiple rounds; capacity; storage overhead; ENTROPY;
D O I
10.1109/TIT.2018.2789426
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Private information retrieval (PIR) is the problem of retrieving one message out of K messages from N noncommunicating replicated databases, where each database stores all K messages, in such a way that each database learns no information about which message is being retrieved. The capacity of PIR is the maximum number of bits of desired information per bit of downloaded information among all PIR schemes. The capacity has recently been characterized for PIR as well as several of its variants. In every case it is assumed that all the queries are generated by the user simultaneously. Here we consider multiround PIR, where the queries in each round are allowed to depend on the answers received in previous rounds. We show that the capacity of multiround PIR is the same as the capacity of single-round PIR. The result is generalized to also include T-privacy constraints. Combined with previous results, this shows that there is no capacity advantage from multiround over single-round schemes, non-linear over linear schemes or from e-error over zero-error schemes. However, we show through an example that there is an advantage in terms of storage overhead. We provide an example of a multiround, non-linear, e-error PIR scheme that requires a strictly smaller storage overhead than the best possible with single-round, linear, zero-error PIR schemes.
引用
收藏
页码:5743 / 5754
页数:12
相关论文
共 32 条
[1]  
[Anonymous], PIR ARRAY CODES OPTI
[2]  
[Anonymous], PRIVATE INFORM RETRI
[3]  
Banawan K., 2016, CAPACITY PRIVATE INF
[4]   General constructions for information-theoretic private information retrieval [J].
Beimel, A ;
Ishai, Y ;
Kushievitz, E .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (02) :213-247
[5]  
Beimel A, 2001, LECT NOTES COMPUT SC, V2076, P912
[6]  
Blackburn S. R., 2016, PIR SCHEMES SMALL DO
[7]  
Blasiak A., 2011, LEXICOGRAPHIC PRODUC
[8]   Dualities between entropy functions and network codes [J].
Chan, Terence ;
Grant, Alex .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (10) :4470-4487
[9]  
Chan TH, 2015, IEEE INT SYMP INFO, P2842, DOI 10.1109/ISIT.2015.7282975
[10]  
Chor B, 1995, AN S FDN CO, P41, DOI 10.1109/SFCS.1995.492461