The Capacity of Private Information Retrieval with Disjoint Colluding Sets
Zhuqing Jia, Hua Sun, Syed A. Jafar · 2017
An extension of private information retrieval (PIR) with colluding servers is considered. The N servers are partitioned into M disjoint sets, such that collusion can only occur between servers that belong to the same set. Specifically, the m-th set is comprised of Nmservers, of which any Tmcan collude. The capacity of this PIR problem is shown to be C = (1 + (Σm = 1MNm/Tm)-1 + ⋯ + (Σm = 1MNm/Tm)-(κ-1))-1.