On Sub-Packetization of Capacity-Achieving PIR Schemes for MDS Coded Databases
share
Consider the problem of private information retrieval (PIR) over a distributed storage system where M records are stored across N servers by using an [N,K] MDS code. For simplicity, this problem is usually referred as the coded-PIR problem. The capacity of coded-PIR with privacy against any individual server was determined by Banawan and Ulukus in 2016, i.e., C_ C-PIR=(1+K/N+...+K^M-1/N^M-1)^-1. They also presented a linear capacity-achieving scheme with sub-packetization KN^M. In this paper we focus on minimizing the sub-packetization for linear capacity-achieving coded-PIR schemes. We prove that the sub-packetization for all linear capacity-achieving coded-PIR schemes in the nontrivial cases (i.e. N>K≥ 1 and M>1) must be no less than Kn^M-1, where n=N/ gcd(N,K). Moreover, we design a linear capacity-achieving coded-PIR scheme with sub-packetization Kn^M-1 for all N>K≥ 1 and M>1. Therefore, Kn^M-1 is the optimal sub-packetization for linear capacity-achieving coded-PIR schemes.
READ FULL TEXT