2018/07/16 by Karim Banawan, Şennur Ulukuş, Banawan, Karim +1
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1807.05997
openalex publication_date 2018/07/16 · openalex created_date 2022/08/04 · openalex updated_date 2026/07/28
We consider the problem of noisy private information retrieval (NPIR) from\nN non-communicating databases, each storing the same set of M messages. In\nthis model, the answer strings are not returned through noiseless bit pipes,\nbut rather through \noisy memoryless channels. We aim at characterizing\nthe PIR capacity for this model as a function of the statistical information\nmeasures of the noisy channels such as entropy and mutual information. We\nderive a general upper bound for the retrieval rate in the form of a max-min\noptimization. We use the achievable schemes for the PIR problem under\nasymmetric traffic constraints and random coding arguments to derive a general\nlower bound for the retrieval rate. The upper and lower bounds match for M=2\nand M=3, for any N, and any noisy channel. The results imply that\nseparation between channel coding and retrieval is optimal except for adapting\nthe traffic ratio from the databases. We refer to this as \almost\nseparation. Next, we consider the private information retrieval problem from\nmultiple access channels (MAC-PIR). In MAC-PIR, the database responses reach\nthe user through a multiple access channel (MAC) that mixes the responses\ntogether in a stochastic way. We show that for the additive MAC and the\nconjunction/disjunction MAC, channel coding and retrieval scheme are\n\inseparable unlike in NPIR. We show that the retrieval scheme depends on\nthe properties of the MAC, in particular on the linearity aspect. For both\ncases, we provide schemes that achieve the full capacity without any loss due\nto the privacy constraint, which implies that the user can exploit the nature\nof the channel to improve privacy. Finally, we show that the full unconstrained\ncapacity is not always attainable by determining the capacity of the selection\nchannel.\n