Rafail Ostrovsky, Victor Shoup, Private Information Storage, May 1996.
We consider the setting of hiding information through the use of multiple databases that do not interact with one another. In this setting, there are k > 1 ``databases'' which can be accessed by some ``users''. Users do not keep any state information, but wish to access O(n) bits of ``data''. Previously, in this setting solutions for retrieval of data in the efficient manner were given, where a user achieves this by interacting with all the da- tabases. We consider the case of both writing and reading. While the case of reading was well studied before, the case of writing was previously completely open. In this paper, we show how to implement both read and write operations, with the following strong security guarantees: all the information about the read/write operation is information-theoretically hidden from all the databases (i.e. both the value of the bit and the address of the bit). As in the previous papers, we measure, as a function of k and n the amount of communication required between a user and all the databases for a single read/write operation, and achieve efficient read/write schemes. Moreover, we show a general reduc- tion from reading database scheme to reading and writing database scheme, with the following guarantees: for any k, given a re- trieval only k-database scheme with communication complexity R(k,n) we show a (k+1) reading and writing database scheme with total communication complexity O(R(k,n) * (log n)^{O(1)}). As corollary of our general reduction in combination with the paper of [Chor,Goldreich,Kushilevitz,Sudan STOC-95] yields:
Fetch PostScript file of the full paper.