PIR is a weaker version of 1-out-of-n 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.
The first single-database computational PIR scheme to achieve communication complexity less than
The security of their scheme was based on the well-studied Quadratic residuosity problem.
In 1999, Christian Cachin, Silvio Micali and Markus Stadler[4] achieved poly-logarithmic communication complexity.
by Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, Qiang Tang, in 2015.
In 2009, Helger Lipmaa[8] designed a computational PIR protocol with communication complexity
Amortization techniques that retrieve non-consecutive bits have been considered by Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky and Amit Sahai.
Achieving information theoretic security requires the assumption that there are multiple non-cooperating servers, each having a copy of the database.
Without this assumption, any information-theoretically secure PIR protocol requires an amount of communication that is at least the size of the database n. Multi-server PIR protocols tolerant of non-responsive or malicious/colluding servers are called robust or Byzantine robust respectively.
In 2012, C. Devet, I. Goldberg, and N. Heninger (DGH 2012) proposed an optimally robust scheme that is Byzantine-robust to
It is based on an earlier protocol of Goldberg that uses Shamir's Secret Sharing to hide the query.
[11] One-way 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 Giovanni Di Crescenzo, Tal Malkin and Rafail Ostrovsky to imply oblivious transfer (see below).
Collision-resistant cryptographic hash functions are implied by any one-round computational PIR scheme, as shown by Ishai, Kushilevitz and Ostrovsky.
[13] The basic motivation for Private Information Retrieval is a family of two-party protocols in which one of the parties (the sender) owns a database, and the other part (the receiver) wants to query it with certain privacy restrictions and warranties.
In a general PIR protocol, a computationally unbounded sender can learn nothing about i so privacy is theoretically preserved.
Since the PIR problem was posed, different approaches to its solution have been pursued and some variations were proposed.
A CPIR (Computationally Private Information Retrieval) protocol is similar to a PIR protocol: the receiver retrieves an element chosen by him from the sender's database, so that the sender obtains no knowledge about which element was transferred.