A survey of single-database private information retrieval: techniques and applications <s> Connections: Single Database PIR and OT <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> Connections: Single Database PIR and OT <s> A Single-Database Private Information Retrieval (PIR) is a protocol that allows a user to privately retrieve from a database an entry with as small as possible communication complexity. We call a PIR protocol non-trivial if its total communication is strictly less than the size of the database. Non-trivial PIR is an important cryptographic primitive with many applications. Thus, understanding which assumptions are necessary for implementing such a primitive is an important task, although (so far) not a well-understood one. In this paper we show that any non-trivial PIR implies Oblivious Transfer, a far better understood primitive. Our result not only significantly clarifies our understanding of any non-trivial PIR protocol, but also yields the following consequences: - Any non-trivial PIR is complete for all two-party and multiparty secure computations. - There exists a communication-efficient reduction from any PIR protocol to a 1-out-of-n Oblivious Transfer protocol (also called SPIR). - There is strong evidence that the assumption of the existence of a one-way function is necessary but not sufficient for any non-trivial PIR protocol. <s> BIB002 </s> A survey of single-database private information retrieval: techniques and applications <s> Connections: Single Database PIR and OT <s> We show that general one-way trapdoor permutations are sufficient to privately retrieve an entry from a database of size n with total communication complexity strictly less than n. More specifically, we present a protocol in which the user sends O(K2) bits and the server sends n - cn/K bits (for any constant c), where K is the security parameter of the trapdoor permutations. Thus, for sufficiently large databases (e.g., when K = nƐ for some small Ɛ) our construction breaks the information-theoretic lower-bound (of at least n bits). This demonstrates the feasibility of basing single-server private information retrieval on general complexity assumptions. ::: ::: An important implication of our result is that we can implement a 1-out-of- n Oblivious Transfer protocol with communication complexity strictly less than n based on any one-way trapdoor permutation. <s> BIB003
Single-database PIR has a close connection to the notion of Oblivious Transfer (OT), introduced by Rabin  . A different variant of Oblivious Transfer, called 1-out-of-2 OT, was introduced by Even, Goldreich and Lempel [14] and, more generally, 1-outof-n OT was considered in Brassard, Crepeau and Robert [3] . Informally, 1-out-of-n OT is a protocol for two players: A sender who initially has n secrets x 1 , . . . , x n and a receiver who initially holds an index 1 ≤ i ≤ n. At the end of the protocol the receiver knows x i but has no information about the other secrets, while the sender has no information about the index i. Note that OT is different from PIR in that there is no communication complexity requirement (beyond being polynomially bounded) but, on the other hand, "secrecy" is required for both players, while for the PIR it is required only for the user. All Oblivious Transfer definitions are shown to be equivalent  . As mentioned, communication-efficient implementation of 1-out-of-n OT can be viewed as a single-server PIR protocol with an additional guarantee that only one (out of n) secrets is learned by the user and the remaining n−1 remain hidden. In BIB001 , it is noted that their protocol can also be made into a 1-out-of-n OT protocol  , showing the first 1-out-of-n OT with sublinear communication complexity. Naor and Pinkas  have subsequently shown how to turn any PIR protocol into 1-out-of-n protocol with one invocation of a Single-Database PIR protocol and logarithmic number of invocations of 1-out-of-2 OT. DiCresenzo, Malkin and Ostrovsky BIB002 showed that any single database PIR protocol implies OT. In fact, their result holds even if PIR protocol allows the communcation from database to the user to be as big as n − 1. Thus, BIB002 combined with  tells us that any Single-Database PIR implies 1-out-of-n OT. In BIB003 , it is shown how to build 1-out-of-n OT based on any one-way trapdoor permutation with communication complexity strictly less than n.