Noisy Private Information Retrieval
Karim Banawan, Şennur Ulukuş · 2018 52nd Asilomar Conference on Signals, Systems, and Computers · 2018
We consider the problem of noisy private information retrieval (NPIR) from N non-communicating databases, each storing the same set of M messages. In this model, the answer strings are not returned through noiseless bit pipes, but rather through noisy memoryless channels. We aim at characterizing the PIR capacity for this model as a function of the statistical information measures of the noisy channels. We derive a general upper bound for the retrieval rate in the form of a max-min optimization. We use the achievable schemes for the PIR problem under asymmetric traffic constraints and the random coding arguments to derive a general lower bound for the retrieval rate. The upper and lower bounds match for M = 2 and M = 3, for any N, and any noisy channel. The results imply that separation between channel coding and retrieval is optimal except for adapting the traffic ratio from the databases.