Computationally private information retrieval (extended abstract)
Benny Chor, Niv Gilboa · 1997
Gilboat show that the computational approach leads to substantial savings.For every ~> 0, we present a two database computational PIR scheme whose communication complexity is O(n').This improved efficiency is achieved by a combination of a novel balancing technique, together with careful application of pseudo random generators.Our schemes preserve some desired properties of previous solutions.In particular, all our schemes use only one round of communication, they are fairly simple, they are memoryless, and the database contents is stored in its plain form, without any encoding.is possible to protect the user's privacy.The solutions to this private information retrieval (PIR) problem enable the user to retrieve a desired data item, while giving each individual database no partial information on the query.The quality of a solution is measured primarily ' Details on related models and techniques can also be found in [3].random generators [2, 10].(This is equivalent to the existence of one way functions [6, 5]. ) Under this assumption, we develop a family of computational PIR schemes.All these schemes