Public Key Encryption That Allows PIR Queries
Authors: D. Boneh, E. Kushilevitz, R. Ostrovsky, and W. Skeith
Abstract:
We consider the following problem: Alice wishes to maintain
her email using a storage-provider Bob (such as a Yahoo! or hotmail
e-mail account). This storage-provider should provide for Alice the
ability to collect, retrieve, search and delete emails but, at the
same time, should learn neither the content of messages sent from the
senders to Alice (with Bob as an intermediary), nor the search
criteria used by Alice. A trivial solution is that messages will be
sent to Bob in encrypted form and Alice, whenever she wants to search
for some message, will ask Bob to send her a copy of the entire
database of encrypted emails. This however is highly inefficient. We
will be interested in solutions that are communication-efficient and,
at the same time, respect the privacy of Alice. In this paper, we show
how to create a public-key encryption scheme for Alice that allows PIR
searching over encrypted documents. Our solution is the first to
reveal no partial information regarding the user's search (including
the access pattern) in the public-key setting and with non-trivially
small communication complexity. This provides a theoretical solution
to a problem posed by Boneh, DiCrescenzo, Ostrovsky and Persiano on
``Public-key Encryption with Keyword Search.'' The main technique of
our solution also allows for Single-Database PIR writing with
sub-linear communication complexity, which we consider of independent
inter est.
Reference:
In proceedings of Crypto 2007, LNCS 4622, pp. 50-67, 2007