The Capacity of Private Information Retrieval from Byzantine and Colluding Databases
We consider the problem of single round private information retrieval (PIR) from <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> replicated databases. We consider the case when <inline formula> <tex math notation="LaTeX"$B$ /tex math>/inline formula> 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 <inline formula> <tex math notation="LaTeX"$M$ /tex math>/inline formula> messages with zero error, irrespective of the actions performed by the Byzantine databases. We consider the <inline formula> <tex math notation="LaTeX"$T$ /tex math>/inline formula> privacy constraint in this paper, where any <inline formula> <tex math notation="LaTeX"$T$ /tex math>/inline formula> 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 <italic>correct symbols</italic> that can be retrieved privately (under the <inline formula> <tex math notation="LaTeX"$T$ /tex math>/inline formula> privacy constraint) for every symbol of the downloaded data. We determine the exact BPIR capacity to be <inline formula> <tex math notation="LaTeX"$C=(N 2B)/N \cdot (1 T/(N 2B)(1 (T/(N 2B){M} /tex math>/inline formula> if <inline formula> <tex math notation="LaTeX"$2B+T N$ /tex math>/inline formula> This capacity expression shows that the effect of Byzantine databases on the retrieval rate is equivalent to removing <inline formula> <tex math notation="LaTeX"$2B$ /tex math>/inline formula> databases from the system, with a penalty factor of <inline formula> <tex math notation="LaTeX"(N 2B)/N$ /tex math>/inline formula> which signifies that even though the number of databases needed for PIR is effectively <inline formula> <tex math notation="LaTeX"$N 2B$ /tex math>/inline formula> the user still needs to access the entire <inline formula> <tex math notation="LaTeX"$N$ /tex math>/inline formula> 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 <italic>errors</italic> introduced by the Byzantine databases as opposed to <italic>erasures</italic> in the RPIR problem. Our converse proof uses the idea of the cut set bound in the network coding problem against adversarial nodes.
IEEE Transactions on Information Theory