On the Capacity of Private Information Retrieval from Coded, Colluding, and Adversarial Servers
Lukas Holzbaur, Ragnar Freij-Hollanti, Camilla Hollanti · 2019
In this work, we first prove the capacity of coded, linear symmetric private information retrieval (SPIR) in the presence of colluding, adversarial, and nonresponsive servers, giving a positive closure to the conjecture stated by Tajeddine et al. It is also shown that, further restricting to strongly-linear PIR schemes with linear interference cancellation, the so-called star product scheme proposed by Freij-Hollanti et al. is optimal. This observation enables to prove the capacity of strongly-linear (non-symmetric) PIR schemes for any number of files. Further, it also provides a positive proof in this practical special case for the conjectures stated in the asymptotic regime by Freij-Hollanti et al. and Tajeddine et al.