Private information storage

This paper deals with the problem of efficiently and privately storing and retrieving information that is distributively maintained in several databases that do not communicate with one another. The goal is to minimize the communication complexity while maintaining privacy (i.e., so that individual databases do not get any information about the data or the nature of the users' queries). The question of private retrieval from multiple databases was introduced in a very nice paper of Chor, Goldreich, Kushilevitz and Sudan (FOCS '95), but the question whether it is possible to perform both reading and writing in a communication-efficient manner remained open. In this paper, we answer this question in the affirmative, and show that efficient read/write schemes are indeed possible. In fact, we show a general information-theoretic reduction from reading and writing to any read-only scheme that preserves the communication complexity of the read scheme to within a poly-logarithmic factor (in the size of the database), thus establishing that read/write schemes could be implemented as efficiently (up to poly-log factors) as read-only schemes. Additionally, we consider the question of both reading and writing in the computational security setting.