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.
Gates 4B (opposite 490)