| Paper ID | D4-S4-T4.1 |
| Paper Title |
A New Design of Cache-aided Multiuser Private Information Retrieval with Uncoded Prefetching |
| Authors |
Xiang Zhang, University of Utah, United States; Kai Wan, Technische Universit at Berlin, Germany; Hua Sun, University of North Texas, United States; Mingyue Ji, University of Utah, United States; Giuseppe Caire, Technische Universit at Berlin, Germany |
| Session |
D4-S4-T4: Private Information Retreival I |
| Chaired Session: |
Thursday, 15 July, 23:00 - 23:20 |
| Engagement Session: |
Thursday, 15 July, 23:20 - 23:40 |
| Abstract |
In the problem of cache-aided Private Information Retrieval (MuPIR), a set of $K_{\rm u}$ cache-quipped users wishes to privately download a set of messages from a set of $N$ distributed databases (DBs), each holding a library of $K$ messages. The system works in two phases, i.e., the cache placement (prefetching) phase in which the users fill up their cache memory as a function of the message bits from the library , and the private delivery phase in which the users' demands are revealed and they download an answer from each DB so that any individual DB learns nothing about the users' demands. The goal is to design the placement and delivery phases such that the \emph{load}, which is defined as the total number of downloaded bits normalized by the message size, is minimized given any user memory size. This paper considers the MuPIR problem with two messages and arbitrary number of users and DBs where uncoded prefetching is assumed, i.e., the users directly copy some bits from the library as their cached contents. We propose a novel MuPIR scheme inspired by the Maddah-Ali and Niesen (MAN) coded caching scheme. The proposed scheme achieves better load than existing schemes, especially the product design (PD), and is shown to be optimal within a factor of 8 in general and exactly optimal at very high and low memory regimes.
|
