In particular, all previous information theoretic PIR schemes required multiple replications of the database into separate entities which are not allowed to communicate with each other; and in all previous schemes (including ones which do not achieve information theoretic security), the amount of computation performed by the database on-line for every query is at least linear in the size of the database. In contrast, in our solutions the database does not give away its contents to any other entity; and after the initial setup stage, which costs at most O(n log n) in computation, the database needs to perform only O(1) amount of computation to answer questions of users on-line. All the extra on-line computation is done by the auxiliary random servers.
Category / Keywords: Private Information Retrieval, Information Theoretic Privacy, database replication, security servers, multi-party computation. Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive. Date: received April 30th, 1998. Contact author: ygertner at saul cis upenn edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Discussion forum: Show discussion | Start new discussion