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

在计算机化的世界中维护用户隐私是一项艰巨的挑战。私有信息检索（PIR）方案允许用户检索在多个服务器之间复制的信息，而不向每个单独的服务器公开该信息的确切性质。 该项目的目的是开发新的技术来构建这样的协议，提高效率。在最近的一项突破中，PI引入了一种新技术，大大降低了最佳PIR协议的成本。这些项目的主要目标是进一步开发这种技术，并更好地理解使其工作的基础数学。追求该项目的研究目标将需要研究和教育的一体化，并对研究生和本科生进行培训。PI还将通过参加计算机科学暑期学校计划，为高中生的教育做出贡献，包括那些来自代表性不足群体的学生。PIR协议保证了在多个非通信服务器之间复制相同数据库的设置中的信息理论隐私。最有趣的情况是两个服务器（尽可能小）。目前的技术水平（PI在最近的工作中获得）给出了次多项式通信成本，改善了需要与数据库大小的立方根成比例的通信的二十年长记录。改进来自于利用PIR和局部可解码码（LDC）之间的连接，局部可解码码是允许通过仅在几个地方查询代码来快速校正单个码字位置的纠错码。 该项目的主要目标是进一步研究这两个对象（PIR和LDCs），并改进它们的已知结构。另一方面，该项目的目的是了解PIR和最不发达国家的局限性，其形式是可证明的效率下限。

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.