Advances in Private Communications: Semantics, Symmetry, Storage and Side Information
Private information retrieval (PIR) refers to the problem of retrieving a file (a message) out of K messages from N distributed databases in such a way that no individual database can tell which message has been retrieved, hence the name, “private” information retrieval. PIR has originated in the computer science literature in late 1990s and has been revisited by the information and communication theory community recently. Information-theoretic reformulation of the problem defines the “PIR capacity” as the largest number of bits that can be retrieved privately per download. In this talk, I will describe the problem, summarize a few break-through results in the history of the problem, and present some of our recent results focusing on semantics of information, symmetry in privacy, effects of storage constraints on privacy, and critical use of side information especially in single-database systems.