Multi-Access Cache-Aided Multi-User Private Information Retrieval

Kanishak Vaidya

doi:10.1109/TCOMM.2024.3375810

2024-07-01

Kanishak Vaidya

B. Sundar Rajan *

DOI：10.1109/TCOMM.2024.3375810

原文链接

原文求助

摘要

En 中文

In a Multi-user Private Information Retrieval (MuPIR) problem, there are N files replicated across S non-colluding servers and K users, each wanting to retrieve a file from the servers without letting the servers getting any information about the demanded files. In a dedicated-cache-aided MuPIR problem each user is equipped with a cache that can store M files. In this paper, we consider a generalized version, called multi-access cache-aided MuPIR problem, where there are K users and C <= K caches each capable of storing M files and each user can access several cache nodes and every cache node can be accessed by several users. The cache nodes are filled with the content of the files before users decide their demands. Then each user chooses a file index, and users cooperatively send queries to the servers to retrieve their desired files privately. The aim is to reduce the size of broadcast done by the servers as a response to these queries. We propose a scheme that utilizes multi-access caches in generalised combinatorial topology, introduced by (Brunero and Elia, 2023) and show that our scheme is order-optimal within a multiplicative factor of 2, assuming uncoded cache placement. Also, we compare the per-user rate of our setup with dedicated cache setup of (Zhang et al., 2021) in various settings.

Keyword:

Servers

Costs

Information retrieval

Topology

Indexes

Privacy

Encoding

Coded caching

private information retrieval (PIR)

multi-access caches