The Capacity of Private Information Retrieval from Byzantine and Colluding Databases

By Karim A. Banawan, Sennur Ulukus. 2017

207 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Information Systems

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

Citations in the corpus

Staircase-PIR: Universally Robust Private Information Retrieval (2018, background): “, [12], [22]–[28] and the capacity of robust PIR schemes under download cost was characterized in [12], [22], [23] for replicated data.”
Private function retrieval (2017, background): “Several extensions of PIR problem have been studied in literature, including the PIR with colluding servers [8], [9], the PIR with coded servers [10], and the symmetric PIR [11], [12].”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, background): “The asymptotic capacity of PIR on replicated storage systems with t colluding servers and b byzantine servers was found in [19] to be 1 − 2b+t n .”
Private Computation of Systematically Encoded Data with Colluding Servers (2018, background): “Related PIR schemes and capacity results have been studied in [6]–[10].”