The capacity of cache aided private information retrieval

Research output: Chapter in Book/Report/Conference proceedingConference contribution

95 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1078-1082
Number of pages5
ISBN (Electronic)9781538632666
DOIs
StatePublished - Jul 1 2017
Event55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States
Duration: Oct 3 2017Oct 6 2017

Publication series

Name55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Volume2018-January

Other

Other55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Country/TerritoryUnited States
CityMonticello
Period10/3/1710/6/17

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Signal Processing
  • Energy Engineering and Power Technology
  • Control and Optimization

Fingerprint

Dive into the research topics of 'The capacity of cache aided private information retrieval'. Together they form a unique fingerprint.

Cite this