Title: Weakly-Private Information Retrieval,
Abstract: Private information retrieval (PIR) protocols make it possible to retrieve a
file from a database without disclosing any information about the identity of
the file being retrieved. These protocols have been rigorously explored from an
information-theoretic perspective in recent years. While existing protocols
strictly impose that no information is leaked on the file's identity, this work
initiates the study of the tradeoffs that can be achieved by relaxing the
requirement of perfect privacy. In case the user is willing to leak some
information on the identity of the retrieved file, we study how the PIR rate,
as well as the upload cost and access complexity, can be improved. For the
particular case of replicated servers, we propose two weakly-private
information retrieval schemes based on two recent PIR protocols and a family of
schemes based on partitioning. Lastly, we compare the performance of the
proposed schemes.