Authenticated private information retrieval

Private-information-retrieval (PIR) protocols enable a client to fetch a record from a database while hiding from the server which specific record the client has fetched. Most private-information-retrieval protocols, however, do not ensure data authenticity in the presence of a malicious server.

In this talk, we introduce protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client has read, and (b) the client either obtains the "authentic" record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. I will present multi-server schemes that protect the security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Our authenticated multi-server schemes essentially match the communication and computational complexity of unauthenticated private-information-retrieval schemes, while single-server schemes are 30-100 times more costly than state-of-the-art unauthenticated schemes, though they achieve incomparably stronger integrity properties. I will conclude the talk with a demonstration of Keyd, a PGP public-key directory service that ensures privacy and authenticity.

This talk is based on joint work with Kirill Nikitin (Cornell Tech), Henry Corrigan-Gibbs (MIT), David J. Wu (UT Austin), and Bryan Ford (EPFL).
Bio:
Simone Colombo is a PhD student in the Decentralized Distributed Systems
Laboratory advised by Prof. Bryan Ford at the École polytechnique fédérale de Lausanne (EPFL). His research interests lie at the intersection of computer systems, cryptography, and security.