On the Asymptotic Capacity of $X$-Secure $T$-Private Information Retrieval with Graph Based Replicated Storage

Understand

The problem of private information retrieval with graph-based replicated storage was recently introduced by Raviv, Tamo and Yaakobi.

• Its capacity remains open in almost all cases.
• In this work the asymptotic (large number of messages) capacity of this problem is studied along with its generalizations to include arbitrary $T$-privacy and $X$-security constraints, where the privacy of the user must be protected against any set of up to $T$ colluding servers and the security of the stored data must be protected against any set of up to $X$ colluding servers.
• A general achievable scheme for arbitrary storage patterns is presented that achieves the rate $(\rho_{\min}-X-T)/N$, where $N$ is the total number of servers, and each message is replicated at least $\rho_{\min}$ times.