Private Information Retrieval From MDS Coded Data in Distributed Storage Systems

DOI10.1109/TIT.2018.2815607zbMATH Open1431.94130arXiv1602.01458WikidataQ130127124 ScholiaQ130127124MaRDI QIDQ4559581FDOQ4559581

Authors: Razane Tajeddine, Oliver Wilhelm Gnilke, Salim El Rouayheb 

Publication date: 4 December 2018

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: The problem of providing privacy, in the private information retrieval (PIR) sense, to users requesting data from a distributed storage system (DSS), is considered. The DSS is coded by an $(n,k,d)$ 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 trivially 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 $frac11-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. Also, when $bleqn-deltak$, for some $deltainmathbb{N}^{+}$, we construct linear PIR schemes with $cPoP=fracb+deltakdelta$.

Full work available at URL: https://arxiv.org/abs/1602.01458

Mathematics Subject Classification ID

Source coding (94A29) Authentication, digital signatures and secret sharing (94A62)

Cited In (8)

• Beyond the MDS Bound in Distributed Cloud Storage
• Private information retrieval from coded databases with colluding servers
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Private information retrieval schemes using cyclic codes
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Multi-value private information retrieval with colluding databases via trace functions
• Private information retrieval from locally repairable databases with colluding servers
• Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers

This page was built for publication: Private Information Retrieval From MDS Coded Data in Distributed Storage Systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4559581)