SaTC: CORE: Small: Practical private information retrieval

私有信息检索（PIR）允许客户端查询数据库，而不向数据库服务器透露其查询。从理论上讲，私人信息检索系统可以让客户搜索在线医学百科全书而不透露她的搜索词，或者浏览在线新闻网站而不透露她正在阅读的文章，或者执行Web搜索查询而不向搜索引擎透露她的查询。在实践中，今天的私人信息检索方案在计算上过于昂贵，无法大规模部署，而且它们缺乏标准数据库支持的许多功能，这些功能对于现实世界的数据库支持的应用程序至关重要。这个项目的目标是：减少私有信息检索协议的服务器端计算成本，增加现有PIR协议的能力，并建立使用PIR保护用户隐私的大规模数据检索系统。为了减少PIR的服务器端计算成本，这个项目将建立在文献中的两种技术上：查询（让服务器一次处理多个查询）和预处理（让服务器以一种允许它更快地回答查询的形式存储数据库）。这个项目将重新审视这些经典的想法，以减少PIR的服务器端成本与新的加密工具，包括最近的工作离线/在线私人信息检索和本地可解码代码的发展。该项目的第二个组成部分将是扩展PIR系统，以处理更有趣的查询类型，如私人全文搜索，甚至私人查询。这将需要新的安全定义、新的加密协议和仔细的实现工作。最后，本项目将把PIR技术构建到开源软件系统中。该项目旨在设计一个私钥服务器（用于WhatsApp，Signal等）。允许客户端将电话号码映射到公钥而不向服务器泄露其地址簿，允许客户端将域名私下映射到Internet协议地址的私有域名系统解析器，以及支持私人搜索和文章下载的维基百科克隆。将PIR应用到这些应用中需要在该项目的第一部分开发新技术，以及大量的系统级优化和实施工作。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Private information retrieval (PIR) allows a client to query a database without revealing its query to the database server. In theory, private-information-retrieval systems would let a client search an online medical encyclopedia without revealing her search terms, or to browse an online news site without revealing which articles she is reading, or to execute a Web-search query without revealing her query to the search engine. In practice, today's schemes for private information retrieval are far too computationally expensive to deploy at scale, and they lack much of the functionality that standard databases support and that are critical for real-world database-backed applications. The goals of this project are to: reduce the server-side computational cost of private-information retrieval protocols, increase the power of existing PIR protocols, and build large-scale data-retrieval systems that use PIR to protect user privacy.To reduce the server-side computation cost of PIR, this project will build on two techniques from the literature: batching (having the server process multiple queries at once) and preprocessing (have the server store the database in a form that allows it to answer queries more quickly). This project will revisit these classic ideas to reducing the server-side cost of PIR with new cryptographic tools, including recent work on offline/online private information retrieval and developments in locally decodable codes. The second component of this project will be to extend PIR systems to handle more interesting query types, such as private full-text searches or even private queries. This will require new security definitions, new cryptographic protocols, and careful implementation work. Finally, this project will build PIR technology into open-source software systems. The project aims to design a private key server (for WhatsApp, Signal, etc.) that allows clients to map phone numbers to public keys without revealing their address book to the server, a private domain-name system resolver that allows clients to privately map domain names to Internet-protocol addresses, and a Wikipedia clone that supports private search and article download. Bringing PIR to such applications will require the new techniques developed in the first parts of this project, as well as substantial systems-level work on optimizations and implementation.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.