A new Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers
share
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 K(N-K)/(N,K), which is much smaller than the previous best result K(N/(N,K))^M-1. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if M>K/(N,K)-K/N-K+1, and within a multiplicative gap K/(N,K) of a lower bound on the minimum file length otherwise.
READ FULL TEXT