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

在计算机化的世界中维护用户隐私是一项艰巨的挑战。私有信息检索（PIR）方案允许用户检索在多个服务器之间复制的信息，而无需向每个单独的服务器透露该信息的确切性质。这个项目的目的是开发新的技术，以提高效率来构建这样的协议。在最近的一项突破中，PI引入了一项新技术，大大降低了最佳PIR协议的成本。这些项目的主要目标是进一步发展这种技术，并更好地理解使其工作的基础数学。为了实现该项目的研究目标，需要将研究与教育以及研究生和本科生的培训相结合。PI还将通过参加计算机科学暑期学校项目，为包括弱势群体在内的高中生的教育做出贡献。在多个非通信服务器之间复制同一数据库的情况下，PIR协议保证了信息理论上的保密性。最有趣的情况是两个服务器（最小的服务器）。目前的技术水平（由PI在最近的一项工作中获得）给出了次多项式的通信成本，改进了与数据库大小的立方根成正比的长达20年的通信记录。这种改进来自于利用PIR和本地可解码代码（ldc）之间的连接，ldc是纠错代码，允许通过仅在少数地方查询代码来快速纠正单个码字位置。该项目的主要目标是进一步研究这两个对象（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.