The Capacity of Private Information Retrieval from Byzantine and Colluding Databases

DOI10.1109/TIT.2018.2869154zbMATH Open1428.68142arXiv1706.01442OpenAlexW2963898134WikidataQ129207341 ScholiaQ129207341MaRDI QIDQ4615381FDOQ4615381

Authors: Karim Banawan, Sennur Ulukus 

Publication date: 28 January 2019

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We consider the problem of single-round private information retrieval (PIR) from $N$ replicated databases. We consider the case when $B$ databases are outdated (unsynchronized), or even worse, adversarial (Byzantine), and therefore, can return incorrect answers. In the PIR problem with Byzantine databases (BPIR), a user wishes to retrieve a specific message from a set of $M$ messages with zero-error, irrespective of the actions performed by the Byzantine databases. We consider the $T$-privacy constraint in this paper, where any $T$ databases can collude, and exchange the queries submitted by the user. We derive the information-theoretic capacity of this problem, which is the maximum number of emph{correct symbols} that can be retrieved privately (under the $T$-privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be $C=fracN-2BNcdotfrac1-fracTN-2B1-(fracTN-2B{)}^M$, if $2B+T<N$. This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing $2B$ databases from the system, with a penalty factor of $fracN-2BN$, which signifies that even though the number of databases needed for PIR is effectively $N-2B$, the user still needs to access the entire $N$ databases. The result shows that for the unsynchronized PIR problem, if the user does not have any knowledge about the fraction of the messages that are mis-synchronized, the single-round capacity is the same as the BPIR capacity. Our achievable scheme extends the optimal achievable scheme for the robust PIR (RPIR) problem to correct the emph{errors} introduced by the Byzantine databases as opposed to emph{erasures} in the RPIR problem. Our converse proof uses the idea of the cut-set bound in the network coding problem against adversarial nodes.

Full work available at URL: https://arxiv.org/abs/1706.01442

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Cryptography (94A60) Database theory (68P15) Privacy of data (68P27)

Cited In (6)

• On the optimal communication complexity of error-correcting multi-server PIR
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases
• Extended results on privacy against coalitions of users in user-private information retrieval protocols
• Verifiable single-server private information retrieval from LWE with binary errors
• Efficient and generic methods to achieve active security in private information retrieval and more advanced database search

This page was built for publication: The Capacity of Private Information Retrieval from Byzantine and Colluding Databases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615381)