|Cache-aided Multiuser Private Information Retrieval
|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
|P.10: Private Information Retrieval III
|Cryptography, Security and Privacy
|Click here to download the manuscript
|Click here to watch in the Virtual Symposium
|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.