PIR from storage constrained databases - Coded caching meets PIR

Ravi Tandon, Maryam Abdul-Wahid, Firas Almoualem, Deepak Kumar

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

12 Scopus citations

Abstract

Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases without revealing the identity of the desired message. There has been significant recent progress on understanding fundamental information theoretic limits of PIR, and in particular the download cost of PIR for several variations. Majority of existing works however, assume the presence of replicated databases, each storing all the K messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of μ KL bits, where K is the number of messages, L is the size of each message in bits, and μ ϵ [1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any (N,K), with normalized storage μ= t/N, where the parameter t can take integer values t ϵ {1, 2, ⋯, N}, we show that our proposed PIR scheme achieves a download cost of (1+ 1/t + 1/t2+ ⋯ + 1/tK-1). The extreme case when μ=1 (i.e., t=N) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as (1+ 1/N+ ⋯ + 1/NK-1). For the other extreme, when μ= 1/N (i.e., t=1), the proposed scheme achieves a download cost of K. The most interesting aspect of the result is that for intermediate values of storage, i.e., 1/N < μ <1, the proposed scheme can strictly outperform memory-sharing between extreme values of storage.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Communications, ICC 2018 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Print)9781538631805
DOIs
StatePublished - Jul 27 2018
Event2018 IEEE International Conference on Communications, ICC 2018 - Kansas City, United States
Duration: May 20 2018May 24 2018

Publication series

NameIEEE International Conference on Communications
Volume2018-May
ISSN (Print)1550-3607

Other

Other2018 IEEE International Conference on Communications, ICC 2018
Country/TerritoryUnited States
CityKansas City
Period5/20/185/24/18

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'PIR from storage constrained databases - Coded caching meets PIR'. Together they form a unique fingerprint.

Cite this