On sub-packetization and access number of capacity-achieving PIR schemes for MDS coded non-colluding servers

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. In 2016, Banawan and Ulukus designed the first capacityachieving coded PIR scheme with sub-packetization K NMand access number M K NM, where capacity characterizes the minimal download size for retrieving per unit of data, and sub-packetization and access number are two metrics closely related to implementation complexity. In this paper, we focus on minimizing the sub-packetization and the access number for linear capacity-achieving coded PIR schemes. We first determine the lower bounds on sub-packetization and access number, which are K nM-1 and M K nM-1,respectively, in the nontrivial cases(i.e., N > K 1 and M > 1), where n = N/gcd(N, K). We then design a general linear capacity-achieving coded PIR scheme to simultaneously attain these two bounds, implying tightness of both bounds.