  A \emph{private proximity retrieval} (\emph{PPR}) scheme is a protocol which
allows a user to retrieve the identities of all records in a database that are
within some distance $r$ from the user's record $x$. The user's \emph{privacy}
at each server is given by the fraction of the record $x$ that is kept private.
In this paper, this research is initiated and protocols that offer trade-offs
between privacy and computational complexity and storage are studied. In
particular, we assume that each server stores a copy of the database and study
the required minimum number of servers by our protocol which provides a given
privacy level. Each server gets a query in the protocol and the set of queries
forms a code. We study the family of codes generated by the set of queries and
in particular the minimum number of codewords in such a code which is the
minimum number of servers required for the protocol. These codes are closely
related to a family of codes known as \emph{covering designs}. We introduce
several lower bounds on the sizes of such codes as well as several
constructions. This work focuses on the case when the records are binary
vectors together with the Hamming distance. Other metrics such as the Johnson
metric are also investigated.
