Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

Razane Tajeddine, Salim El Rouayheb

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

53 Citations (Scopus)


We consider the problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS). The DSS uses an (n, k) Maximum Distance Separable (MDS) code to store the data reliably on unreliable storage nodes. Some of these nodes can be spies which report to a third party, such as an oppressive regime, which data is being requested by the user. An information theoretic PIR scheme ensures that a user can satisfy its request while revealing, to the spy nodes, no information on which data is being requested. A user can achieve PIR by downloading all the data in the DSS. However, this is not a feasible solution due to its high communication cost. We construct PIR schemes with low download communication cost. When there is b = 1 spy node in the DSS, we construct PIR schemes with download cost 1/1-R per unit of requested data (R = k/n is the code rate), achieving the information theoretic limit for linear schemes. The proposed schemes are universal since they depend on the code rate, but not on the generator matrix of the code. When there are 2 ≤ b ≤ n - k spy nodes, we devise linear PIR schemes that have download cost equal to b + k per unit of requested data.
Original languageEnglish
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
ISBN (Electronic)978-1-5090-1806-2
Publication statusPublished - Jul 2016
MoE publication typeA4 Article in a conference publication
EventIEEE International Symposium on Information Theory - Barcelona, Spain
Duration: 10 Jul 201615 Jul 2016

Publication series

NameIEEE International Symposium on Information Theory
ISSN (Electronic)2157-8117


ConferenceIEEE International Symposium on Information Theory
Abbreviated titleISIT
Internet address


  • Decision support systems
  • Peer-to-peer computing
  • Privacy
  • Databases
  • Reliability
  • Servers
  • Spread spectrum communication

Fingerprint Dive into the research topics of 'Private Information Retrieval from MDS Coded Data in Distributed Storage Systems'. Together they form a unique fingerprint.

Cite this