2017/10/31 by Zhang, Zhifang, Xu, Jingke
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1710.11370
Suppose a database containing M records is replicated across N servers, and a user wants to privately retrieve one record by accessing the servers such that identity of the retrieved record is secret against any up to T servers. A scheme designed for this purpose is called a private information retrieval (PIR) scheme. In practice, capacity-achieving and small sub-packetization are both desired for PIR schemes, because the former implies the highest download rate and the latter usually means simple realization. For general values of N,T,M, the only known capacity-achieving PIR scheme was designed by Sun and Jafar in 2016 with sub-packetization NM. In this paper, we design a linear capacity-achieving PIR scheme with much smaller sub-packetization dnM-1, where d=\rm gcd(N,T) and n=N/d. Furthermore, we prove that for any linear capacity-achieving PIR scheme it must have sub-packetization no less than dnM-1, implying our scheme has the optimal sub-packetization. Moreover, comparing with Sun and Jafar's scheme, our scheme reduces the field size by a factor of \frac1NdM-2.