Technical Program

Paper Detail

Paper IDP.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

Visit Website!