Capacity-achieving private information retrieval scheme with a smaller sub-packetization
Wenqin Zhang, Zhengchun Zhou, Udaya Parampalli, Vladimir R. Sidorenko · Advances in Mathematics of Communications · 2020
Private information retrieval (PIR) allows a user to retrieve one out of \begin{document}$ M $\end{document} messages from \begin{document}$ N $\end{document} servers without revealing the identity of the desired message. Every message consists of \begin{document}$ L $\end{document} symbols (packets) from an additive group and the length \begin{document}$ L $\end{document} is called the sub-packetization. A PIR scheme with download cost (DC) \begin{document}$ D/L $\end{document} is implemented by querying \begin{document}$ D $\end{document} sums of the symbols to servers. We assume that each uncoded server can store up to \begin{document}$ tLM/N $\end{document} symbols, \begin{document}$ t\in\{1,2,\cdots,N\} $\end{document} . The minimum DC of storage constrained PIR was determined by Attia et al. in 2018 to be \begin{document}$ DC_{min} = 1+1/t+1/t^{2}+\cdots+1/t^{M-1} $\end{document} . The capacity of storage constrained PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired symbols that can be privately retrieved per bit of downloaded symbols. Tandon et al. designed a capacity-achieving PIR scheme with sub-packetization \begin{document}$ L' = {N\choose t}t^{M} $\end{document} of each message. In this paper, we design a PIR scheme with \begin{document}$ t $\end{document} times smaller sub-packetization \begin{document}$ L'/t $\end{document} and with the minimum DC for any parameters \begin{document}$ N, M, t $\end{document} . We also prove that \begin{document}$ t^{M-1} $\end{document} is a factor of sub-packetization \begin{document}$ L $\end{document} for any capacity-achieving PIR scheme from storage constrained servers.