The Capacity of Private Information Retrieval From Coded Databases

被引:216
作者
Banawan, Karim [1 ]
Ulukus, Sennur [1 ]
机构
[1] Univ Maryland, Dept Elect & Comp Engn, College Pk, MD 20742 USA
关键词
Private information retrieval; distributed storage; MDS code; capacity; alignment;
D O I
10.1109/TIT.2018.2791994
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider the problem of private information retrieval (PIR) over a distributed storage system. The storage system consists of N non-colluding databases, each storing an MDS-coded version of M messages. In the PIR problem, the user wishes to retrieve one of the available messages without revealing the message identity to any individual database. We derive the information-theoretic capacity of this problem, which is defined as the maximum number of bits of the desired message that can be privately retrieved per one bit of downloaded information. We show that the PIR capacity in this case is C = (1 + K/N + K-2/N-2 + ... + KM-1/NM-1)(-1) = (1 + R-c + R-c(2) + ... + R-c(M-1))(-1) = (1 - R-c)/(1 - R-c(M)), where R-c is the rate of the (N, K) MDS code used. The capacity is a function of the code rate and the number of messages only regardless of the explicit structure of the storage code. The result implies a fundamental tradeoff between the optimal retrieval cost and the storage cost when the storage code is restricted to the class of MDS codes. The result generalizes the achievability and converse results for the classical PIR with replicated databases to the case of MDS-coded databases.
引用
收藏
页码:1945 / 1956
页数:12
相关论文
共 16 条
[1]  
[Anonymous], 2012, ELEMENTS INFORM THEO
[2]  
Banawan K., 2017, 2017 IEEE INT C COMM, P1
[3]  
Chan TH, 2015, IEEE INT SYMP INFO, P2842, DOI 10.1109/ISIT.2015.7282975
[4]   Private information retrieval [J].
Chor, B ;
Goldreich, O ;
Kushilevitz, E ;
Sudan, M .
JOURNAL OF THE ACM, 1998, 45 (06) :965-982
[5]   A Survey on Network Codes for Distributed Storage [J].
Dimakis, Alexandros G. ;
Ramchandran, Kannan ;
Wu, Yunnan ;
Suh, Changho .
PROCEEDINGS OF THE IEEE, 2011, 99 (03) :476-489
[6]  
Fazeli A., 2015, Pir with low storage overhead: Coding instead of replication
[7]  
Gasarch W., 2004, Bulletin of the European Association for Theoretical Computer Science, P72
[8]   Blind Interference Alignment [J].
Jafar, Syed A. .
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING, 2012, 6 (03) :216-227
[9]  
Ostrovsky R, 2007, LECT NOTES COMPUT SC, V4450, P393
[10]  
Shah NB, 2014, IEEE INT SYMP INFO, P856, DOI 10.1109/ISIT.2014.6874954