A survey of single-database private information retrieval: techniques and applications <s> PIR Based on Group-Homomorphic Encryption <s> We establish the following, quite unexpected, result: replication of data for the computational private information retrieval problem is not necessary. More specifically, based on the quadratic residuosity assumption, we present a single database, computationally private information retrieval scheme with O(n/sup /spl epsiv//) communication complexity for any /spl epsiv/>0. <s> BIB001 </s> A survey of single-database private information retrieval: techniques and applications <s> PIR Based on Group-Homomorphic Encryption <s> We study the problem of single database private information retrieval, and present a solution with only logarithmic server-side communication complexity and a solution with only logarithmic user-side communication complexity. Previously the best result could only achieve polylogarithmic communication on each side, and was based on certain less well-studied assumptions in number theory [6]. On the contrary, our schemes are based on Paillier’s cryptosystem [16], which along with its variants have drawn extensive studies in recent cryptographic researches [3, 4, 8, 9], and have many important applications [7, 8]. <s> BIB002 </s> A survey of single-database private information retrieval: techniques and applications <s> PIR Based on Group-Homomorphic Encryption <s> We propose a one-round 1-out-of-n computationally-private information retrieval protocol for l-bit strings with low-degree polylogarithmic receiver-computation, linear sender-computation and communication Θ(klog2n+llogn), where k is a possibly non-constant security parameter. The new protocol is receiver-private if the underlying length-flexible additively homomorphic public-key cryptosystem is IND-CPA secure. It can be transformed to a one-round computationally receiver-private and information-theoretically sender-private 1-out-of-n oblivious-transfer protocol for l-bit strings, that has the same asymptotic communication and is private in the standard complexity-theoretic model. <s> BIB003
The original work on computational PIR by Kushilevitz and Ostrovsky BIB001 presented a private information retrieval protocol based upon homomorphic encryption. Such techniques are often very natural ways to construct a variety of privacy-preserving protocols. It is often the case with such protocols based upon homomorphic encryption, that although the protocol is designed with a specific cryptosystem, there is a more fundamental, underlying design that could be instantiated with many different cryptosystems in place of the original, and furthermore this choice of cryptosystem can have a very non-trivial impact on performance. For example, the work of BIB001 used the homomorphic cryptosystem of Goldwasser and Micali  to create a PIR protocol, and in the following years, many other similar protocols were developed based upon other cryptosystems, e.g., the work of Chang BIB002 which is based upon the cryptosystem of Paillier  , and also the work of Lipmaa BIB003 . However, the method of BIB001 was actually quite generic, although it was not originally stated in generality. In this section, we'll present an abstract construction based upon any group homomorphic encryption scheme which has BIB001 and BIB002 as special cases, as well as capturing the work of BIB003 . Hopefully, this section will provide the reader with general intuition regarding private information retrieval, as well as a pleasant way to understand the basics of a moderate amount of the literature in computational PIR.