Timely Private Information Retrieval
This addresses the challenge of timely and private data retrieval for users accessing dynamic information from distributed servers, representing an incremental extension of PIR with timeliness constraints.
The paper tackles the problem of retrieving a message from continuously updating servers while maintaining privacy and timeliness, using age of information (AoI) as a metric, and characterizes the optimal tradeoff between PIR rate and AoI for specific cases (N=2, M=3) with concrete results.
We introduce the problem of \emph{timely} private information retrieval (PIR) from $N$ non-colluding and replicated servers. In this problem, a user desires to retrieve a message out of $M$ messages from the servers, whose contents are continuously updating. The retrieval process should be executed in a timely manner such that no information is leaked about the identity of the message. To assess the timeliness, we use the \emph{age of information} (AoI) metric. Interestingly, the timely PIR problem reduces to an AoI minimization subject to PIR constraints under \emph{asymmetric traffic}. We explicitly characterize the optimal tradeoff between the PIR rate and the AoI metric (peak AoI or average AoI) for the case of $N=2$, $M=3$. Further, we provide some structural insights on the general problem with arbitrary $N$, $M$.