Private information storage (extended abstract) 论文

摘要

) Rafail Ostrovsky Victor Shoup y Bellcore Bellcore, IBM May 1997 Abstract 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 informationtheoretic reduction from reading and writing to any read-only scheme that preserves the comm...