Private Cache-aided Interference Alignment for Multiuser Private Information Retrieval
Xiang Zhang, Kai Wan, Hua Sun, Mingyue Ji, Giuseppe Caire · Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks · 2020
In the problem of cache-aided Multiuser Private Information Retrieval (MuPIR), a set of K u cache-aided users wish to download their desired messages from a set of N distributed non-colluding databases each holding a library of K independent messages. The communication load of this problem is defined as the total number of bits downloaded (normalized by the message length) by the users. The goal is to find the optimal memory-load trade-off under the constraint of user demand privacy, which ensures that any individual database learns nothing about the demands of the users. In this paper, for the MuPIR problem with $K=2$ messages, $K_{u}=2$ users and $N\geq 2$ databases, we provide achievability for the memory-load pairs $\left(\frac{N-1}{2N},\frac{N+1}{N}\right)$ and $\left(\frac{2\left(N-1\right)}{2N-1},\frac{N+1}{2N-1}\right)$ by constructing specific achievable schemes based on the novel idea of Private Cache-aided Interference Alignment (PCIA). We prove that the proposed scheme is optimal if the cache placement is uncoded (i.e., users directly cache a subset of the library bits). Computer-aided investigation also shows that the proposed schemes are optimal in general when $N=2,3$.