SaTC: CORE: Small: Practical private information retrieval

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

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.