2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | P.10.5 | ||
| Paper Title | Cache-aided Multiuser Private Information Retrieval | ||
| Authors | Xiang Zhang, University of Utah, United States; Kai Wan, Technische Universitat Berlin, Germany; Hua Sun, University of North Texas, United States; Mingyue Ji, University of Utah, United States | ||
| Session | P.10: Private Information Retrieval III | ||
| Presentation | Lecture | ||
| Track | Cryptography, Security and Privacy | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | This paper formulates the cache-aided multi-user PIR (MuPIR) problem, including K_u cache-equipped users, each of which wishes to retrieve a desired message efficiently from N distributed databases with access to K independent messages. Privacy of the users’ demands requires that any individual database can not learn anything about the demands of the users. The load of this problem is defined as the average number of downloaded bits per desired message bit. The goal is to find the optimal memory-load trade-off while preserving the demand privacy. Besides the formulation of the MuPIR problem, the contribution of this paper is two-fold. First, we characterize the optimal memory-load trade-off for a system with N = 2 databases, K = 2 messages and Ku = 2 users demanding distinct messages; Second, a product design with order optimality guarantee is proposed. In addition, the product design can achieve the optimal load when the cache memory is large enough. The “product design” embeds the well-known Sun-Jafar PIR scheme into the coded caching, in order to benefit from the coded caching gain while preserving the privacy of the users’ demands. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
