Cache-Aided Multi-User Private Information Retrieval using PDAs

被引:2
作者
Vaidya, Kanishak [1 ]
Rajan, B. Sundar [1 ]
机构
[1] IISc Bangalore, Dept Elect Commun Engn, Bengaluru, India
来源
2023 IEEE INFORMATION THEORY WORKSHOP, ITW | 2023年
关键词
FUNDAMENTAL LIMITS; CAPACITY;
D O I
10.1109/ITW55543.2023.10161671
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider the problem of cache-aided multi-user private information retrieval (MuPIR). In this problem, each of K cache-equipped users wants to privately retrieve a file out of N files replicated across B non-colluding servers. The user caches are filled with some arbitrary function of the files before the users decide their demands, known as the placement phase. Then in the delivery phase, users decide their demands and send queries to the servers to retrieve their desired files. This paper proposes MuPIR schemes that utilize placement delivery arrays (PDAs) to characterize placement and delivery. Proposed MuPIR schemes significantly reduce subpacketization levels while slightly increasing the download cost for the users. The proposed scheme also substantially reduces the upload cost for the users. For PDAs based on Ali-Niesen scheme for centralized coded caching, we show that our scheme is order optimal in terms of download cost. We recover the optimal single-user PIR scheme presented by Tian et al. in "Capacity-Achieving Private Information Retrieval Codes With Optimal Message Size and Upload Cost" as a special case. Our scheme also achieves optimal rate for single-user cache-aided PIR setup as described by R. Tondon in "The capacity of cache aided private information retrieval".
引用
收藏
页码:125 / 130
页数:6
相关论文
共 12 条
[1]   The Capacity of T-Private Information Retrieval With Private Side Information [J].
Chen, Zhen ;
Wang, Zhiying ;
Jafar, Syed Ali .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (08) :4761-4773
[2]  
Chor B, 1995, AN S FDN CO, P41, DOI 10.1109/SFCS.1995.492461
[3]   Improved Lower Bounds for Coded Caching [J].
Ghasemi, Hooshang ;
Ramamoorthy, Aditya .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (07) :4388-4413
[4]  
Lin HY, 2019, IEEE INT SYMP INFO, P1257, DOI [10.1109/ISIT.2019.8849444, 10.1109/isit.2019.8849444]
[5]   Fundamental Limits of Caching [J].
Maddah-Ali, Mohammad Ali ;
Niesen, Urs .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2014, 60 (05) :2856-2867
[6]   The Capacity of Robust Private Information Retrieval With Colluding Databases [J].
Sun, Hua ;
Jafar, Syed Ali .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (04) :2361-2370
[7]   The Capacity of Private Information Retrieval [J].
Sun, Hua ;
Jafar, Syed Ali .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (07) :4075-4088
[8]  
Tandon R, 2017, ANN ALLERTON CONF, P1078, DOI 10.1109/ALLERTON.2017.8262857
[9]   Capacity-Achieving Private Information Retrieval Codes With Optimal Message Size and Upload Cost [J].
Tian, Chao ;
Sun, Hua ;
Chen, Jun .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2019, 65 (11) :7613-7627
[10]   On the Placement Delivery Array Design for Centralized Coded Caching Scheme [J].
Yan, Qifa ;
Cheng, Minquan ;
Tang, Xiaohu ;
Chen, Qingchun .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2017, 63 (09) :5821-5833