Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers

Abstract

The problem of Private Information Retrieval (PIR) from coded storage systems with colluding, byzantine, and unresponsive servers is considered. An explicit scheme using an $[n,k]$ Reed-Solomon storage code is designed, protecting against $t$-collusion and handling up to $b$ byzantine and $r$ unresponsive servers, when $n>k+t+2b+r-1$. This scheme achieves a PIR rate of $\frac{n-r-(k+2b+t-1)}{n-r}$. In the case where the capacity is known, namely when $k=1$, it is asymptotically capacity-achieving as the number of files grows. Lastly, the scheme is adapted to symmetric PIR.

arXiv commentThis is an extended journal version of the ISIT paper arXiv:1802.03731

References in corpus (4)

• Private Information Retrieval from Coded Databases with Colluding Servers
• Linear Symmetric Private Information Retrieval for MDS Coded Distributed Storage with Colluding Servers
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers