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

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