| dc.description.abstract | The objective of the classical Private Information Retrieval (PIR) problem is to enable a user to
download a message from a database that is replicated across a collection of non-colluding servers
without revealing the identity of the demanded message to the servers. In the classical PIR problem
the user has no prior information about the content of messages in the database. It is easy to verify
in the special case of the PIR problem when there is only one server in the system, the user must
download all messages from the database in order keep information about the message they want
private.
In a real environment the user may have other sources to download and obtain messages from
such as trusted peer-to-peer communication. In this way, the user has the potential to obtain some
of the messages that are contained in the database to use as side information in a PIR scheme with
the servers. Accordingly, we introduce the Private Information Retrieval with Side Information
(PIR-SI) problem that focuses on settings in which the user has side information about some messages
in the database. To capture the different levels of privacy a user may want to enforce in
PIR-SI schemes two metrics of privacy, W-privacy and (W,S)-privacy, are introduced. W-privacy
only protects information about the identity of the message that the user wants and is most similar
to the measure of privacy in the original PIR problem. (W, S)-privacy protects the identity of the
wanted message as well as the identities of the messages they have as side information and is a
stronger sense of privacy than W-privacy. When enforcing either measure of privacy the user no
longer has to download all the messages in the database, even if there is only one server in the
system; side information reduces the amount of data that one has to download in a PIR scheme.
The first case of the PIR-SI problem that we consider is when the user has M messages for side
information and wants a different message from the database of K messages. When there is only
one server in the system, we show that the optimal download rate for a W-private scheme is k^-1/M+1
and the optimal download rate for a (W, S)-private scheme is 1/K-M.
When there is more than one
server in the system a W-private scheme is presented that has a larger rate than the classical PIR
scheme, but its optimality is not shown.
The second case of the PIR-SI problem that is considered is when the user has M messages as
side information, the user wants D > 1 distinct messages from the database, and there is only one
server in the system. In the case when M = 1 a (W, S)-private optimal scheme is presented and
shown to be optimal. In the case when M ≥ D and D = 2 a W-private scheme that can increase
the rate from the (W, S)-private scheme with the same parameters is presented. This scheme’s
optimality reminds an open problem. We highlight the difficulty of finding an optimal scheme and
determining the capacity of the multi-message PIR-SI problem. | en |
