Building Capacity-Achieving PIR Schemes with Optimal Sub-Packetization over Small Fields
Jingke Xu, Zhifang Zhang · 2018
Consider N servers with replicated databases containing M records. Suppose a user wants to privately retrieve one record by accessing the servers such that the identity of the retrieved record is secret against any up to T servers. A scheme designed for this purpose is called a T -private information retrieval ( T -PIR) scheme. Three indexes are concerned for PIR schemes: (1) rate, indicating the amount of retrieved information per unit of downloaded data. The highest achievable rate is characterized by the capacity; (2) sub-packetization, reflecting the implementation complexity for linear schemes; (3) field size. We consider linear schemes over a finite field. In this paper, a general T - PIR scheme simultaneously attaining the optimality of almost all of the three indexes is presented. Specifically, we design a linear capacity-achieving T-PIR scheme with sub-packetization dnM-1over a finite field \mathbbFq, q ≥ N. The sub-packetization dnM-1, where d=gcd(N, T) and n=N/d, has been proved to be optimal in our previous work. The field size is reduced by an exponential factor in our scheme comparing with existing capacity -achieving T - PIR schemes.