Private information retrievalFrom CryptoDox, The Online Encyclopedia on Cryptography and Information SecurityIn cryptography, a private information retrieval (PIR) protocol allows a user to retrieve an item from a server in possession of a database without revealing which item she is retrieving. PIR is a weaker version of 1outofn oblivious transfer, where it is also required that the user should not get information about other database items. One trivial, but very inefficient way to achieve PIR is for the server to send an entire copy of the database to the user. In fact, this is the only possible protocol that gives the user information theoretic privacy for her query. There are two ways to get around this problem: one is to make the server computationally bounded and the other is to assume that there are multiple noncooperating servers, each having a copy of the database. The problem was introduced in 1996 by Chor, Goldreich, Kushilevitz and Sudan in the informationtheoretic setting and in 1997 by Kushilevitz and Ostrovsky in the computational setting. Since then, very efficient solutions have been discovered. Single database (computationally private) PIR can be achieved with constant (amortized) communication and kdatabase (information theoretic) PIR can be done with communication.
Advances in computational PIRThe first singledatabase computational PIR scheme to achieve communication complexity less than n was created in 1997 by Eyal Kushilevitz and Rafail Ostrovsky [1] and achieved communication complexity of n^{ε} for any ε, where n is the number of bits in the database. The security of their scheme was based on the wellstudied Quadratic residuosity problem. In 1999, Christian Cachin, Silvio Micali and Michael Stadler [2] achieved polylogarithmic communication complexity. The security of their system is based on the Phihiding assumption. In 2004, Helger Lipmaa [3] achieved logsquared communication complexity , where is the length of the strings and k is the security parameter. The security of his system reduces to the semantic security of a lengthflexible additively homomorphic cryptosystem like the DamgaardJurik cryptosystem. In 2005 Craig Gentry and Zulfikar Ramzan [4] achieved logsquared communication complexity which retrieves logsquare (consecutive) bits of the database. The security of their scheme is also based on a variant of the Phihiding assumption. Amortization techniques that retrieve nonconsecutive bits have been considered by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai [5]. Advances in information theoretic PIRAchieving information theoretic security requires the assumption that there are multiple noncooperating servers, each having a copy of the database. Without this assumption, any informationtheoretically secure PIR protocol requires an amount of communication that is at least the size of the database n. For the case of 2 noncooperating servers, the best protocol is due to Chor et al. and uses communication . For the case of 3 servers, if 2^{p}  1 is a Mersenne prime, then the communication of O(n^{1 / p}) is sufficient (Yekhanin, 2006). Based on largest known Mersenne prime (as of February 2007), this gives a protocol with the communication of O(n^{1 / 32582658}). If there are infinitely many Mersenne primes, then for infinitely many n, there is a protocol with the communication of O(n^{1 / loglogn}). For k>3 servers, Beimel et al., 2002 have shown that there is an information theoretically secure protocol with the communication of . This is now superseded by Yekhanin's work, except for very large k. Relation to other cryptographic primitivesOneway functions are necessary, but not known to be sufficient, for nontrivial (i.e, with sublinear communication) single database computationally private information retrieval. In fact, such a protocol was proved by G. Di Crescenzo, T. Malkin and R. Ostrovsky in [6] to imply oblivious transfer (see below). Oblivious transfer, also called symmetric PIR, is PIR with the additional restriction that the user not learn any item other than the one she requested. It is termed symmetric because both the user and the database have a privacy requirement. CollisionResistant Hash Functions are implied by any oneround computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky [7]. External links
References
Proceedings of the 43nd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, Canada, pages 261270, 2002.
