Capacity limits for private retrieval from coded storage with faulty servers
The Capacity of Private Information Retrieval from Coded Storage Systems with Colluding, Robust and Byzantine Servers
Information Theory
Summary
This paper studies how to privately fetch information from distributed databases where data is encoded and spread across many servers. Some servers may collude to learn what is being requested, some may be unresponsive, and some may act maliciously by returning wrong data. The authors find exact formulas for the best possible retrieval rate in these scenarios under certain coding assumptions. They also extend their results to cases retrieving multiple files at once.
What this means in practice
- •For cloud storage providers: Design storage systems that allow users to privately and reliably fetch data despite some servers being faulty or conspiring.
- •For distributed database engineers: Implement retrieval schemes that optimize data download rates while protecting user privacy against colluding and malicious nodes.
Authors
Rui Sun, Yiwei Zhang
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$.