The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers

We consider the problem of private information retrieval from MDS-coded databases with T colluding servers, U robust servers, and B Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, M files are stored across N servers, and in this paper each file is independently encoded using an $(N,K)$ GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as C=N-U-2B/N-U(1+K+T-1/N-U-2B+⋯+(K+T-1/N-U-2B)M-1)⁻¹ when N-U-2B≥ KT. When $K=1$ or $T=1$, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of P out of M files. For P ≥ M/2, the resulting multi-file scheme achieves capacity when $K=1$ or $T=1$.