Cache-Aided Multi-User Private Information Retrieval Using PDAs

doi:10.1109/TCOMM.2023.3325473

2024-02-01

Kanishak Vaidya

B. Sundar Rajan *

DOI：10.1109/TCOMM.2023.3325473

原文链接

原文求助

摘要

En 中文

We consider the problem of cache-aided multi-user private information retrieval (MuPIR). In this problem, N independent files are replicated across S >= 2 non-colluding servers. There are K users, each equipped with cache memory which can store M files. Each user wants to retrieve a file from the servers, but the users don't want any of the servers to get any information about their demand. The user caches are filled with some arbitrary function of the files before the users decide their demands, known as the placement phase. After deciding their demands, users cooperatively send queries to the servers to retrieve their desired files privately. Upon receiving the queries, servers broadcast coded transmissions which are a function of the queries they received and the files, known as the delivery phase. Conveying queries to the servers incurs an upload cost for the users, and downloading the answers broadcasted by the servers incurs a download cost. To implement cache-aided MuPIR schemes, each file has to be split into F packets. In this paper, we propose 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. 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, IEEE Trans. Inform. Theory, 2019] as a special case. Our scheme also achieves optimal rate for single-user cache-aided PIR setup reported in [R. Tondon, The capacity of cache aided private information retrieval, Annual Allerton Conference on Communication, Control and Computing, 2017.]

Keyword:

Private information retrieval

coded caching

placement delivery array

multi-user PIR

subpacketization level