Improving the Robustness of Private Information Retrieval
Ian Goldberg
University of Waterloo
Abstract
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. We will conclude with some recent
results further improving the effeciency of these protocols.
Biography
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.