Upper bound on the communication complexity of private information retrieval.

Abstract

We construct a scheme for private information retrieval with k databases and communication complexity O(n 1=(2k\\Gamma1) ). 1 Introduction Much attention has been given to the problem of protecting a database from the user that tries to retrieve the information that he is not allowed to access[2, 8, 12]. In some scenarios, the opposite problem can appear: a user wishes to retrieve some infomation from a database without revealing to the database what information he needs. For example[7], an investor wishes to receive information about certain stock but he does not wishe others (even the database) to know in which particular stock he is interesed. However, there is only one way to reach complete privacy: the user should ask for the copy of entire database. Otherwise, the database will get some information what the user wishes to know. This is not a good solution because it requires much time and much communiction from the database to the user. If there are several identical copies ...