On Share Conversions for Private Information Retrieval

Beimel et al. in CCC 12’ put forward a paradigm for constructing Private Information Retrieval (PIR) schemes, capturing several previous constructions for [Formula: see text] servers. A key component in the paradigm, applicable to three-server PIR, is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of “modified universal” relation. In a useful particular instantiation of the paradigm, they used a share conversion from [Formula: see text]-CNF over [Formula: see text] to three-additive sharing over [Formula: see text] for primes [Formula: see text] where [Formula: see text] and [Formula: see text]. The share conversion is with respect to the modified universal relation [Formula: see text]. They reduced the question of whether a suitable share conversion exists for a triple [Formula: see text] to the (in)solvability of a certain linear system over [Formula: see text]. Assuming a solution exists, they also provided a efficient (in [Formula: see text]) construction of such a sharing scheme. They proved a suitable conversion exists for several triples of small numbers using a computer program; in particular, [Formula: see text] yielded the three-server PIR with the best communication complexity at the time. This approach quickly becomes infeasible as the resulting matrix is of size [Formula: see text]. In this work, we prove that the solvability condition holds for an infinite family of [Formula: see text] ’s, answering an open question of Beimel et al. Concretely, we prove that if [Formula: see text] and [Formula: see text] , then a conversion of the required form exists. We leave the full characterization of such triples, with potential applications to PIR complexity, to future work. Although larger (particularly with [Formula: see text]) triples do not yield improved three-server PIR communication complexity via BIKO’s construction, a richer family of PIR protocols we obtain by plugging in our share conversions might have useful properties for other applications. Moreover, we hope that the analytic techniques for understanding the relevant matrices we developed would help to understand whether share conversion as above for [Formula: see text] , where m is a product of more than two (say three) distinct primes, exists. The general BIKO paradigm generalizes to work for such [Formula: see text] ’s. Furthermore, the linear condition in Beimel et al. generalizes to m’s, which are products of more than two primes, so our hope is somewhat justified. In case such a conversion does exist, plugging it into BIKO’s construction would lead to major improvement to the state of the art of three-server PIR communication complexity (reducing Communication Complexity (CC) in correspondence with certain matching vector families).