Cache-Aided Multi-message Private Information Retrieval

We consider the problem of multi-message private information retrieval (MPIR) fromNnon-colluding and replicated servers when the user is equipped with a cache that holds an uncoded fractionrfrom each of theKstored messages in the servers. We assume that the servers are unaware of the cache content. We investigate(D_{P}^*(r)), which is the optimal download cost normalized by the message size, as a function ofK,N,r,P. For a fixedK,N, we develop an inner bound (converse bound) for the(D_{P}^*(r))curve. The inner bound is a piece-wise linear function inr. For the achievability, we propose specific schemes that exploit the cached as private side information to achieve some corner points. We obtain an outer bound (achievability) for any caching ratio by memory-sharing between these corner points. Thus, the outer bound is also a piece-wise linear function inr. The inner and the outer bounds match for the cases where the number of desired messagesPis at least half of the number of the overall stored messagesK. Furthermore, the bounds match in two specific regimes for the case(\frac{K}{P} > 2)and(\frac{K}{P} \in \mathbb {N}): the very high ratio regime, i.e.,(r \ge \frac{1}{N+1})and the very low ratio regime, i.e.,(r \le \frac{(N-1)P \alpha 1}{ N\left( \sum {k=2}^K \left( {\begin{array}{c}K\ k\end{array}}\right) \alpha k -\sum {k=2}^{K-P} \left( {\begin{array}{c}K-P\ k\end{array}}\right) \alpha k \right) + (N-1)P \alpha 1}). Finally, the bounds meet in one specific regime for arbitrarily fixedK,P,N: the very high ratio regime, i.e.,(r \ge \frac{1}{N+1}).