On the Fundamental Limits of Cache-Aided Multiuser Private Information Retrieval
On the Fundamental Limits of Cache-Aided Multiuser Private Information Retrieval
复制标题
DOI：
10.1109/tcomm.2021.3091612
复制
发表时间：
2021-09-01
影响因子：
8.3
通讯作者：
Caire, Giuseppe
中科院分区：
文献类型：
--
作者：
Zhang, Xiang;Wan, Kai;Caire, Giuseppe
我们考虑的问题，缓存辅助多用户私人信息检索（MuPIR），这是一个扩展的单用户缓存辅助PIR问题的情况下，多个用户。在高速缓存辅助的MuPIR中，K-u个配备高速缓存的用户中的每一个都希望从N个数据库中的K个消息中私下检索消息，每个数据库都可以访问整个消息库。需求隐私要求任何单独的数据库都不了解所有用户的需求。用户通过一个无错误的共享链接连接到每个数据库。在本文中，我们的目标是表征用户的缓存内存和通信负载之间的最佳权衡，这样的系统。首先，我们提出了一种新的方法的缓存辅助干扰对齐（CIA），与K = 2消息，K-u = 2用户和N >= 2数据库的MuPIR问题。当该高速缓存放置未编码时，CIA方法是最佳的。对于一般的高速缓存布局，CIA方法是最佳的，当N = 2和3的计算机辅助匡威方法验证。其次，对于一般情况下，我们提出了一个产品设计（PD），它将PIR代码的线性缓存代码。的产品设计示出的乘法因子为8内的顺序最优，是完全最佳的高记忆制度。
We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the K-u cache-equipped users wishes to privately retrieve a message out of K messages from N databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach of cache-aided interference alignment (CIA), for the MuPIR problem with K = 2 messages, K-u = 2 users and N >= 2 databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when N = 2 and 3 verified by the computer-aided converse approach. Second, for the general case, we propose a product design (PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime.