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.
arXiv comment8 pages, 2 figures
References in corpus (7)
- Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
- A general private information retrieval scheme for MDS coded databases with colluding servers
- Private Information Retrieval from Storage Constrained Databases -- Coded Caching meets PIR
- Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
- Cross Subspace Alignment and the Asymptotic Capacity of -Secure -Private Information Retrieval
- Single-Server Multi-Message Private Information Retrieval with Side Information
- On the Capacity of Single-Server Multi-Message Private Information Retrieval with Side Information