An Efficient, High-Rate Scheme for Private Information Retrieval over the Gaussian MAC
Or Elimelech, Asaf Cohen · 2024
This paper revisited the problem of Private Information Retrieval (PIR), where there are$N$replicated non-communicating databases containing the same$M$messages, and a user who wishes to retrieve one of the messages without revealing the wanted message's index to the databases. However, we assume a block-fading additive white Gaussian noise multiple access channel (AWGN MAC) linking the user and the databases. Previous work [1] presented a joint channel-PIR scheme, utilizing the Compute and Forward protocol, showing the potential of a joint channel-PIR scheme over a separated one. In this paper, we propose an improved joint scheme tailored for the PIR problem with$N$databases over a block-fading AWGN. Unlike the C&F protocol, our scheme offers reduced computational complexity while improving the scaling laws governing the achievable rate. Specifically, the achievable rate scales with the number of databases$N$and the power$P$similarly to the channel capacity without the privacy constraint and outperforms the C&F-based approach. Furthermore, the analysis demonstrates that the improved rate exhibits only a finite gap from the unconstrained channel capacity - one bit per second per Hz as$N$increases.