[freehaven-dev] Ostrovsky on "Private Information Storage"

[dmolnar@belegost.mit.edu]

A while back, we thought about the question 

"Is it possible to create a system in which it can not be shown that 
a server contains an Evil File, even if the server is itself compromised 
at some point?"

noted that our current framework didn't seem to meet this notion of
"security" or "anonymity", and moved on. 

I just noticed a paper by Ostrovsky & Shoup which might be relevant to
this question. I haven't read it carefully yet, but the abstract and the
specification of security requirements are interesting. 

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.
 
http://www.argreenhouse.com/papers/rafail/28.html