The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases

Mohamed Adel Attia, Deepak Kumar, Ravi Tandon

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

Private information retrieval (PIR) allows a user to retrieve a desired message from a set of databases without revealing the identity of the desired message. The replicated database scenario, where N databases store each of the K messages was considered by Sun and Jafar, and the optimal download cost was characterized as (1+ 1/N+ 1/N2+ ⋯ + 1/NK-1). In this work, we consider the problem of PIR from uncoded storage constrained databases. Each database has a storage capacity of μ KL bits, where L is the size of each message in bits, and μ in [1/N, 1] is the normalized storage. The novel aspect of this work is to characterize the optimum download cost of PIR from uncoded storage constrained databases for any 'normalized storage' value in the range μ in [1/N, 1]. In particular, for any (N,K), we show that the optimal trade-off between normalized storage, μ, and the download cost, D(μ), is a piece-wise linear function given by the lower convex hull of the N pairs (t/N, (1+ 1/t+ 1/t2+ ⋯ + 1/tK-1)) for t=1,2,⋯, N. To prove this result, we first present a storage constrained PIR scheme for any (N,K). Next, we obtain a general lower bound on the download cost for PIR, which is valid for any arbitrary storage architecture. The uncoded storage assumption is then applied which allows us to express the lower bound as a linear program (LP). Finally, we solve the LP to obtain tight lower bounds on the download cost for different regimes of storage, which match the proposed storage constrained PIR scheme.

Original languageEnglish (US)
Article number9189813
Pages (from-to)6617-6634
Number of pages18
JournalIEEE Transactions on Information Theory
Volume66
Issue number11
DOIs
StatePublished - Nov 2020
Externally publishedYes

Keywords

  • capacity
  • distributed storage
  • Private information retrieval
  • storage constrained databases
  • uncoded storage

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Fingerprint

Dive into the research topics of 'The Capacity of Private Information Retrieval from Uncoded Storage Constrained Databases'. Together they form a unique fingerprint.

Cite this