Building Capacity-Achieving PIR Schemes with Optimal Sub-Packetization over Small Fields

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 $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, reflexing 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 $\text{\hspace{0.17em}⁣}d{n}^{M-1}\text{\hspace{0.17em}⁣}$ over a finite field ${\mathbb{F}}_q$, $q\ge N$. The sub-packetization $\text{\hspace{0.17em}⁣}d{n}^{M-1}\text{\hspace{0.17em}⁣}$, where $\text{\hspace{0.17em}⁣}d\text{\hspace{0.17em}⁣}=\text{\hspace{0.17em}⁣}\mathrm{g}\mathrm{c}\mathrm{d}(N,T)\text{\hspace{0.17em}⁣}$ and $\text{\hspace{0.17em}⁣}n\text{\hspace{0.17em}⁣}=\text{\hspace{0.17em}⁣}N\mathrm{/}d$, has been proved to be optimal in our previous work. The field size of all existing capacity-achieving $T$-PIR schemes must be larger than $N{t}^{M-2}$ where $t=T\mathrm{/}d$, while our scheme reduces the field size by an exponential factor.