A Capacity-Achieving T-PIR Scheme Based On MDS Array Codes
Jingke Xu, Yaqian Zhang, Zhifang Zhang · 2019
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 MDS array codes. It only requires field size q≥ℓ√N, where ℓ = min {tM-2, (n - t)M-2}, t = T/gcd(N, T), n = N/gcd(N, T) and has the optimal sub-packetization NnM-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 ≥ 2 + ⌈logμlog2N⌉, where μ = min{t, n - t} > 1.