DEPARTMENT SEMINAR

Ian Goldberg
University of Waterloo
David R. Cheriton School of Computer Science

Friday, April 13, 2007
Computer Science Building, Room 151
11:00 AM

Faculty Host: Brian Levine

"Improving the Robustness of Private Information Retrieval"

Suppose you want to look up a specific patent from an online patent database, but you don't want the operator of the database to learn *which* patent you're interested in. A trivial solution is for the database operator to send you the whole database; can we do better? Private Information Retrieval (PIR) is the field that examines these kinds of problems. There are a wide variety of PIR protocols; some protect the privacy of the query through encryption, while others protect it information-theoretically by splitting the query across multiple database servers. In the latter case, an important consideration is robustness: how do we deal with servers that may maliciously return incorrect results, collude for an adversarial purpose, or simply fail.
In this talk, we present a new PIR protocol that information-theoretically protects queries from a group of servers, some of which may respond incorrectly or not at all. Our new protocol increases the maximum privacy level (the number of servers which need to collude in order to determine your query) by a factor of 3 over the previous work. It also allows more servers to reply maliciously, while still maintaining your ability to determine the correct response to your query and to identify bad actors. We then extend this protocol to produce one which provides hybrid privacy protection:
information-theoretic protection if a limited number of servers collude; cryptographic protection if they all do.
No prior knowledge of PIR will be assumed.

Bio:
Ian Goldberg is an Assistant Professor of Computer Science at the University of Waterloo, where he is part of the Cryptography, Security, and Privacy (CrySP) research group. He holds a Ph.D. from the University of California, Berkeley, where he co-founded that university's Internet Security, Applications, Authentication and Cryptography group. From 1999 to 2006, he was Chief Scientist of Radialpoint (formerly known as Zero-Knowledge Systems), a company offering security and privacy technologies for Internet users.