Skip to main content

Mathematical Sciences Seminar - Optimally Robust Private Information Retrieval

When: —
Venue: Birkbeck Main Building, Malet Street

No booking required

Private information retrieval (PIR) allows clients to retrieve information from databases without revealing to the database servers what is being requested. In one type of PIR, called information-theoretic PIR (IT-PIR), the process works by having the client split her query across multiple database servers. The question then arises: what happens if some of these servers are offline (the "robustness" problem), or are misbehaving and producing incorrect replies (the "Byzantine robustness" problem)?

In this talk, we will examine past approaches to the robustness and Byzantine robustness problems, and discuss our new approach, which achieves the theoretical limit for Byzantine robustness. That is, our protocol can allow a client to successfully complete queries and identify server misbehaviour in the presence of the maximum possible number of malicious servers.

We achieve these optimal bounds by employing a variant of Cohn and Heninger's recent polynomial-lattice-based error-correcting code, which we will describe in the talk. We have implemented our scheme and it is extremely fast in practice: up to thousands of times faster than previous work. This is joint work with Casey Devet (University of Waterloo) and Nadia Heninger (University of Pennsylvania)

Bio

Ian Goldberg is an Associate Professor of Computer Science and a University Research Chair in the Faculty of Mathematics at the University of Waterloo, where he is a founding member of the Cryptography, Security, and Privacy (CrySP) research group. His research focuses on developing usable and useful technologies to help Internet users maintain their security and privacy. He is a Lifetime Member of the Canadian Mathematical Society, a Senior Member of the Association for Computing Machinery, and a winner of the Electronic Frontier Foundation's Pioneer Award.

Contact name: