TY - GEN
T1 - The capacity of cache aided private information retrieval
AU - Tandon, Ravi
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of K messages, each of size L bits from N distributed databases. The user has a local cache of storage SL bits which can be used to store any function of the K messages. The main contribution of this work is the exact characterization of the capacity of cache enabled PIR as a function of the storage parameter S. In particular, for a given cache storage parameter S, the information-Theoretically optimal download cost D(S)/L (or the inverse of capacity) is shown to be equal to (1-S/K)(1 + 1/N +.. + 1/NK-1). Special cases of this result correspond to the settings when S = 0, for which the optimal download cost was shown by Sun and Jafar to be (1 + 1/N +.. + 1/NK-1), and the case when S = K, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is 0. The intermediate points S (0, K) can be readily achieved through a simple memory-sharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage S which shows that memory sharing is information-Theoretically optimal.
AB - The problem of cache enabled private information retrieval (PIR) is considered in which a user wishes to privately retrieve one out of K messages, each of size L bits from N distributed databases. The user has a local cache of storage SL bits which can be used to store any function of the K messages. The main contribution of this work is the exact characterization of the capacity of cache enabled PIR as a function of the storage parameter S. In particular, for a given cache storage parameter S, the information-Theoretically optimal download cost D(S)/L (or the inverse of capacity) is shown to be equal to (1-S/K)(1 + 1/N +.. + 1/NK-1). Special cases of this result correspond to the settings when S = 0, for which the optimal download cost was shown by Sun and Jafar to be (1 + 1/N +.. + 1/NK-1), and the case when S = K, i.e., cache size is large enough to store all messages locally, for which the optimal download cost is 0. The intermediate points S (0, K) can be readily achieved through a simple memory-sharing based PIR scheme. The key technical contribution of this work is the converse, i.e., a lower bound on the download cost as a function of storage S which shows that memory sharing is information-Theoretically optimal.
UR - http://www.scopus.com/inward/record.url?scp=85047982096&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85047982096&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2017.8262857
DO - 10.1109/ALLERTON.2017.8262857
M3 - Conference contribution
AN - SCOPUS:85047982096
T3 - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
SP - 1078
EP - 1082
BT - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Y2 - 3 October 2017 through 6 October 2017
ER -