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

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 $Kbig(frac{N}{gcd(N,K)}big)^{M-1}$. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if $M>biglfloor frac{K}{gcd(N,K)}-frac{K}{N-K}bigrfloor+1$, and within a multiplicative gap $frac{K}{gcd(N,K)}$ of a lower bound on the minimum file length otherwise.