AF: Small: New Techniques for Private Information Retrieval and Locally Decodable Codes

Princeton University, Princeton NJ

Investigators

Abstract

Maintaining user privacy in a computerized world is a difficult challenge. Private Information Retrieval (PIR) schemes allow a user to retrieve a piece of information replicated among several servers without disclosing the precise nature of that information to each individual server. The aim of this project is to develop new techniques for constructing such protocols with improved efficiency. In a recent breakthrough, the PI introduced a new technique that dramatically reduced the cost of the best PIR protocols. The main goals of the projects are to develop this technique further and to understand better the underlying mathematics that make it work. Pursuing the research goals of the project will require integration of research and education and training of gradate and undergraduate students. The PI will also contribute to education of high school students, including those from under-represented groups, by participating in a computer science summer school program. PIR protocols guarantee information theoretic privacy in the setting where the same database is replicated among several non-communicating servers. The most interesting case is that of two servers (the smallest possible). The current state of the art (obtained in a recent work by the PI) gives sub-polynomial communication cost, improving the two-decades long record requiring communication proportional to the cube root of the database size. The improvement comes from leveraging the connection between PIR and Locally Decodable Codes (LDCs) which are error correcting codes that allow for quick correction of a single codeword position by querying the code in only a few places. The main goals of this project are to further study these two objects (PIR and LDCs) and to improve their known constructions. On the other hand, the project will aim to understand the limitation of PIR and LDCs in the form of provable lower bounds on their efficiency.