Rafail Ostrovsky - Publications

Private Information Storage

Rafail Ostrovsky, Victor Shoup

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 of user requests while maintaining information-theoretic privacy (i.e., so that individual databases do not get any information about the data or the nature of the users' queries). While previously communication-efficient solutions for reading only was given in a very nice paper of Chor, Goldreich, Kishilevtiz, Sudan (FOCS '95), the question of whether it is possible to perform both reading and writing in a communication-efficient manner remained completely open. In this paper, we answer this question in the affirmative, and show that efficient read/write schemes are indeed possible. Moreover, we show a 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. It should be stressed that prior to the current paper no non-trivial (i.e., sub-linear) bounds for private information storage (i.e., both reading and writing) were known.

comment: Appeared In Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing (STOC-97)

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List