Private Information Retrieval from MDS Coded Data in Distributed Storage Systems
Loading...
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
View publication in the Research portal
View/Open full text file from the Research portal
Other link related to publication
Date
2018-03-13
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
IEEE Transactions on Information Theory
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 no information on which data is being requested to the nodes. 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, in other words, no collusion between the nodes, 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. Also, if b ≤ n — δk nodes collude, with δ = b ⌊ n—b/k ⌋, we construct linear PIR schemes with download cost b+δk/δ .Description
Keywords
Data models, Databases, Information retrieval, Peer-to-peer computing, Privacy, Reliability, Servers
Other note
Citation
Tajeddine, R, Gnilke, O W & El Rouayheb, S 2018, ' Private Information Retrieval from MDS Coded Data in Distributed Storage Systems ', IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 7081-7093 . https://doi.org/10.1109/TIT.2018.2815607
