The Capacity of Multi-round Private Information Retrieval from Byzantine Databases
Xinyu Yao, Nan Liu, Wei Kang · 2019
In this work, we investigate the capacity of private information retrieval (PIR) from N replicated databases, where a subset of the databases are byzantine. 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.