Abstract:

Private Information Retrieval (PIR) protocols allow a user to
retrieve a data item from a database while hiding the identity of the
item being retrieved. This problem was introduced in '95 by Chor,
Goldreich, Kushilevitz and Sudan and has since been the subject of a
considerable amount of research. Much of the recent interest in PIR
is due to its close relation with the notion of locally-decodable
codes: error correcting codes which can provide high fault tolerance
while allowing for a very efficient "local" decoding of a single bit
of data. We will survey some of the research in this area and provide
a high-level view of recently proposed PIR protocols. The talk does
not assume prior background in cryptography or coding theory.