A new Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers

Abstract

In a distributed storage system, private information retrieval (PIR) guarantees that a user retrieves one file from the system without revealing any information about the identity of its interested file to any individual server. In this paper, we investigate $(N,K,M)$ coded sever model of PIR, where each of $M$ files is distributed to the $N$ servers in the form of $(N,K)$ maximum distance separable (MDS) code for some $N>K$ and $M>1$. As a result, we propose a new capacity-achieving $(N,K,M)$ coded linear PIR scheme such that it can be implemented with file length $\frac{K(N-K)}{\gcd (N,K)}$, which is much smaller than the previous best result $K(\frac{N}{\gcd (N,K)}{)}^{M-1}$. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if $M>\lfloor \frac{K}{\gcd (N,K)}-\frac{K}{N-K}\rfloor +1$, and within a multiplicative gap $\frac{K}{\gcd (N,K)}$ of a lower bound on the minimum file length otherwise.

17 pages, submitted to IEEE for possible publication