ML p(r)ior | Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

### Private Information Retrieval from MDS Coded Data in Distributed Storage Systems

2016-02-03
1602.01458 | cs.IT
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 $\frac{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, when $b\leq n-\delta k$, for some $\delta \in \mathbb{N^+}$, we construct linear PIR schemes with $cPoP = \frac{b+\delta k}{\delta}$.

Highlights - Most important sentences from the article

# Related Articles

2019-03-16
1903.06921 | cs.IT

In a distributed storage system, private information retrieval (PIR) guarantees that a user retrieve… show more

Highlights - Most important sentences from the article

2017-09-26
1709.08928 | cs.IT

The majority of works in distributed storage networks assume a simple network model with a collectio… show more

Highlights - Most important sentences from the article

2018-12-04
1812.01142 | cs.IT

Determinant codes are a class of exact-repair regenerating codes for distributed storage systems wit… show more

Highlights - Most important sentences from the article

2019-01-09
1901.02938 | cs.IT

Information-theoretical private information retrieval (PIR) is considered from a coded database with… show more

Highlights - Most important sentences from the article

2019-01-20
1901.06730 | cs.IT

Private information retrieval (PIR) protocols make it possible to retrieve a file from a database wi… show more

Highlights - Most important sentences from the article

2018-04-08
1804.02692 | cs.IT

Private information retrieval has been reformulated in an information-theoretic perspective in recen… show more

Highlights - Most important sentences from the article

2017-12-11
1712.03898 | cs.IT

We propose three private information retrieval (PIR) protocols for distributed storage systems (DSSs… show more

Highlights - Most important sentences from the article

2019-03-19
1903.08229 | cs.IT

We consider constructing capacity-achieving linear codes with minimum message size for private infor… show more

Highlights - Most important sentences from the article

2019-01-16
1901.05112 | cs.IT

An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some… show more

Highlights - Most important sentences from the article

2018-12-10
1812.04142 | cs.IT

Private computation is a generalization of private information retrieval, in which a user is able to… show more

Highlights - Most important sentences from the article

2018-10-12
1810.05719 | cs.IT

We study a class of private information retrieval (PIR) methods that we call one-shot schemes. The i… show more

Highlights - Most important sentences from the article

2018-08-22
1808.07457 | cs.IT

$X$-secure and $T$-private information retrieval (XSTPIR) is a form of private information retrieval… show more

Highlights - Most important sentences from the article

2019-01-14
1901.04419 | cs.IT

The paper is devoted to the problem of erasure coding in distributed storage. We consider a model of… show more

Highlights - Most important sentences from the article

2018-09-04
1809.00872 | cs.IT

Highlights - Most important sentences from the article

2018-11-07
1811.02898 | cs.IT

A private information retrieval (PIR) scheme allows a user to retrieve a file from a database withou… show more

Highlights - Most important sentences from the article

2016-09-22
1609.07027 | cs.IT

In the classical model for (information theoretically secure) Private Information Retrieval (PIR), a… show more

Highlights - Most important sentences from the article