no. 4 · Wednesday 28 October 2026
The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
Abstract
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=\frac{N-U-2B}{N-U}(1+\frac{K+T-1}{N-U-2B}+\cdots+(\frac{K+T-1}{N-U-2B})^{M-1})^{-1}$ when $N-U-2B\ge 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 \ge \frac{M}{2}$, the resulting multi-file scheme achieves capacity when $K=1$ or $T=1$.
- fields
- Information Theory