Technical Program

Paper Detail

Paper Title A Capacity-Achieving T-PIR Scheme Based On MDS Array Codes
Paper IdentifierTU3.R3.2
Authors Jingke Xu, Yaqian Zhang, Zhifang Zhang, Academy of Mathematics and Systems Science, Chinese Academy of Sciences; University of Chinese Academy of Sciences, China
Session Private Information Retrieval II
Location Monge, Level 3
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 14:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract Suppose a database containing $M$ records is replicated in each of $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. In this paper we focus on the field size of $T$-PIR schemes. We design a general capacity-achieving $T$-PIR scheme whose queries are generated by using some {\rm MDS } array codes. It only requires field size $q\geq\sqrt[\ell]{N}$, where $\ell=\min\{t^{M-2},(n-t)^{M-2}\}, ~t=T/{\rm gcd}(N,T), ~n=N/{\rm gcd}(N,T)$ and has the optimal sub-packetization $Nn^{M-2}$. Comparing with existing capacity-achieving $T$-PIR schemes, our scheme has the following advantage, that is, its field size monotonically decreases as the number of records $M$ grows. In particular, the binary field is sufficient for building a capacity-achieving T-PIR scheme as long as $M\geq 2+\lceil\log_\mu\log_2N\rceil$, where $\mu=\min\{t,n-t\}>1$.