FR4.R8.2

An Efficient, High-Rate Scheme for Private Information Retrieval over the Gaussian MAC

Or Elimelech, Asaf Cohen, Ben Gurion University, Israel

Session:
Private Information Retrieval 3

Track:
16: Private Information Retrieval

Location:
Omega

Presentation Time:
Fri, 12 Jul, 16:45 - 17:05

Session Chair:
Ago-Erik Riet, University of Tartu, Estonia
Abstract
This paper addresses the challenge of the private information retrieval (PIR) problem wherein there are $N$ replicated non-communicating databases containing the same $M$ messages and a user who wants to retrieve one of the messages without revealing the wanted message's index to the databases. In addition, we assume a block-fading additive white Gaussian noise multiple access channel (AWGN MAC) linking the user and the databases. Shmuel's contribution \cite{shmuel2021private}, presenting a joint channel-PIR scheme utilizing the C\&F protocol, has shown the potential of a joint channel-PIR scheme over a separated scheme. In this paper, we propose an improved joint channel-PIR approach 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. Our 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, our analysis demonstrates that our improved rate exhibits only a finite gap from the channel capacity of one bit as $N$ increases.
Resources