New Bounds and a Generalization for Share Conversion for 3-Server PIR

Private Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replicated among the non-colluding servers, provide high efficiency in the information-theoretic setting. Beimel et al. in CCC 12’ (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for [Formula: see text] servers, as well as improving the best-known share complexity for 3-server PIR. A key component there 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] , and the relation is modified universal relation [Formula: see text]. They reduced the question of the existence of the share conversion for a triple [Formula: see text] to the (in)solvability of a certain linear system over [Formula: see text] , and provided an efficient (in [Formula: see text]) construction of such a sharing scheme. Unfortunately, the size of the system is [Formula: see text] which entails the infeasibility of a direct solution for big m’s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd [Formula: see text] , [Formula: see text] when [Formula: see text] , obtaining in this way infinitely many parameters for which the conversion exists, but also for infinitely many of them it remained open. In this work, using some algebraic techniques from the work of Paskin-Cherniavsky and Schmerler, we prove the existence of the conversion for even m’s in case [Formula: see text] (we computed [Formula: see text] in this case) and the absence of the conversion for even m’s in case [Formula: see text]. This does not improve the concrete efficiency of 3-server PIR; however, our result is promising in a broader context of constructing PIR through composition techniques with [Formula: see text] servers, using the relation [Formula: see text] where m has more than two prime divisors. Another our suggestion about 3-server PIR is that it’s possible to achieve a shorter server’s response using the relation [Formula: see text] for extended [Formula: see text]. By computer search, in BIKO framework we found several such sets for small m’s which result in share conversion from [Formula: see text]-CNF over [Formula: see text] to 3-additive secret sharing over [Formula: see text] , where [Formula: see text] is several times less than [Formula: see text] , which implies several times shorter server’s response. We also suggest that such extended sets [Formula: see text] can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension.