Technical Program

Paper Detail

Paper Title The Capacity of Multi-round Private Information Retrieval from Byzantine Databases
Paper IdentifierTH3.R3.3
Authors Xinyu Yao, Nan Liu, Wei Kang, Southeast University, China
Session Private Information Retrieval IV
Location Monge, Level 3
Session Time Thursday, 11 July, 14:30 - 16:10
Presentation Time Thursday, 11 July, 15:10 - 15:30
Manuscript  Click here to download the manuscript
Abstract 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.