The Capacity of Multi-round Private Information Retrieval from Byzantine Databases
arXiv:1901.06907
Abstract
In this work, we investigate the capacity of private information retrieval (PIR) from replicated databases, where a subset of the databases are untrustworthy (byzantine) in their answers to the query of the user. We allow for multi-round queries and demonstrate that the identities of the byzantine databases can be determined with a small additional download cost. As a result, the capacity of the multi-round PIR with byzantine databases (BPIR) reaches that of the robust PIR problem when the number of byzantine databases is less than the number of trustworthy databases.
8 pages, 2 figures