Private information storage

Rafail Ostrovsky, Victor Shoup

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)294-303
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Private information storage'. Together they form a unique fingerprint.

Cite this