In the problem of cache-aided Multiuser Private Information Retrieval (MuPIR), a set of K u cache-aided users wish to download their desired messages from a set of N distributed non-colluding databases each holding a library of K independent messages. The communication load of this problem is defined as the total number of bits downloaded (normalized by the message length) by the users. The goal is to find the optimal memory-load trade-off under the constraint of user demand privacy, which ensures that any individual database learns nothing about the demands of the users. In this paper, for the MuPIR problem with K=2 messages, Ku=2 users and N≥2 databases, we provide achievability for the memory-load pairs (N−12N,N+1N) and (2(N−1)2N−1,N+12N−1) by constructing specific achievable schemes based on the novel idea of Private Cache-aided Interference Alignment (PCIA). We prove that the proposed scheme is optimal if the cache placement is uncoded (i.e., users directly cache a subset of the library bits). Computer-aided investigation also shows that the proposed schemes are optimal in general when N=2,3.
more »
« less
Cache-aided Multiuser Private Information Retrieval
This paper formulates the cache-aided multi-user Private Information Retrieval (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 K u = 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 coded caching, in order to benefit from the coded caching gain while preserving the privacy of the users’ demands.
more »
« less
- NSF-PAR ID:
- 10188069
- Date Published:
- Journal Name:
- 2020 IEEE International Symposium on Information Theory (ISIT)
- Page Range / eLocation ID:
- 1095 to 1100
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In the problem of cache-aided Multiuser Private Information Retrieval (MuPIR), a set of Ku cache-aided users wish to download their desired messages from a set of N distributed non-colluding databases each holding a library of K independent messages. The communication load of this problem is defined as the total number of bits downloaded (normalized by the message length) by the users. The goal is to find the optimal memory-load trade-off under the constraint of user demand privacy, which ensures that any individual database learns nothing about the demands of the users. In this paper, for the MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 databases, we provide achievability for the memory-load pairs (N-1/2N, N+1/N) and(2(N-1)/2N-1,N+1/2N-1) by constructing specific achievable schemes based on the novel idea of Private Cacheaided Interference Alignment (PCIA). We prove that the proposed scheme is optimal if the cache placement is uncoded (i.e., users directly cache a subset of the library bits). Computer-aided investigation also shows that the proposed schemes are optimal in general when N = 2, 3.more » « less
-
In the coded caching literature, the notion of privacy is considered only against demands. On the motivation that multi-round transmissions almost appear everywhere in real communication systems, this paper formulates the coded caching problem with private demands and caches. Only one existing private caching scheme, which is based on introducing virtual users, can preserve the privacy of demands and caches simultaneously, but at the cost of an extremely large subpacketization exponential in the product of the number of users (K) and files (N) in the system. In order to reduce the subpacketization while satisfying the privacy constraints, we propose a novel approach which constructs private coded caching schemes through private information retrieval (PIR). Based on this approach, we propose novel schemes with private demands and caches which have a subpacketization level in the order exponential with K instead of NK in the virtual user scheme. As a by-product, for the coded caching problem with private demands, a private coded caching scheme could be obtained from the proposed approach, which generally improves the memory-load tradeoff of the private coded caching scheme by Yan and Tuninetti.more » « less
-
We consider the cache-aided multiuser private information retrieval (MuPIR) problem with a focus on the special case of two messages, two users and arbitrary number of databases where the users have distinct demands of the messages. We characterize the optimal memory-load trade-off for the considered MuPIR problem by proposing a novel achievable scheme and a tight converse. The proposed achievable scheme uses the idea of cache-aided interference alignment (CIA) developed in the literature by the same authors. The proposed converse uses a tree-like decoding structure to incorporate both the decodability and privacy requirements of the users. While the optimal characterization of the cache-aided MuPIR problem is challenging in general, this work provides insight into understanding the general structure of the cache-aided MuPIR problem.more » « less
-
In this paper, we propose a new design framework on Device-to-Device (D2D) coded caching networks with optimal communication load (rate) but significantly less file subpacketizations compared to that of the well-known D2D coded caching scheme proposed by Ji, Caire and Molisch (JCM). The proposed design framework is referred to as the Packet Type-based (PTB) design, where each file is partitioned into packets according to their pre-defined types while the cache placement and user multicast grouping are based on the packet types. This leads to the so-called raw packet saving gain for the subpacketization levels. By a careful selection of transmitters within each multicasting group, a so-called further splitting ratio gain of the subpacketizatios can also be achieved. By the joint effect of the raw packet saving gain and the further splitting ratio gain, an order-wise subpacketization reduction can be achieved compared to the JCM scheme while preserving the optimal rate. In addition, as the first time presented in the literature according to our knowledge, we find that unequal subpacketizaton is a key to achieve subpacketization reductions when the number of users is odd. As a by-product, instead of directly translating shared link caching schemes to D2D caching schemes, at least for the sake of subpackeitzation, a new design framework is indeed needed.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ISIT44484.2020.9174083
