A new capacity-achieving private information retrieval scheme with (almost) optimal file length for coded servers

J Zhu, Q Yan, C Qi, X Tang - IEEE Transactions on Information …, 2019 - ieeexplore.ieee.org
IEEE Transactions on Information Forensics and Security, 2019ieeexplore.ieee.org
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 an (N, K, M) coded server
model of PIR, where each of M files is distributed to 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 …
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 an (N, K, M) coded server model of PIR, where each of M files is distributed to 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)/(gcd(N,K)), which is much smaller than the previous best result K(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 > ⌊K/(gcd(N,K)) - K/(N-K)⌋ + 1 or min(K, N - K)|N, and within a multiplicative gap (min(K,N-K))/(gcd(N,K) ) of a lower bound on the minimum file length otherwise.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果