In the problem of cacheaided Multiuser Private Information Retrieval (MuPIR), a set of K u cacheaided users wish to download their desired messages from a set of N distributed noncolluding 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 memoryload tradeoff 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 memoryload 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 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). Computeraided investigation also shows that the proposed schemes are optimal in general when N=2,3.
more »
« less
Private Cacheaided Interference Alignment for Multiuser Private Information Retrieval
In the problem of cacheaided Multiuser Private Information Retrieval (MuPIR), a set of Ku cacheaided users wish to download their desired messages from a set of N distributed noncolluding 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 memoryload tradeoff 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 memoryload pairs (N1/2N, N+1/N) and(2(N1)/2N1,N+1/2N1) 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). Computeraided investigation also shows that the proposed schemes are optimal in general when N = 2, 3.
more »
« less
 Award ID(s):
 1817154
 NSFPAR ID:
 10195609
 Date Published:
 Journal Name:
 2020 18th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


This paper formulates the cacheaided multiuser Private Information Retrieval (MuPIR) problem, including K u cacheequipped 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 memoryload tradeoff while preserving the demand privacy. Besides the formulation of the MuPIR problem, the contribution of this paper is twofold. First, we characterize the optimal memoryload tradeoff 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 wellknown SunJafar PIR scheme into coded caching, in order to benefit from the coded caching gain while preserving the privacy of the users’ demands.more » « less

We consider the cacheaided 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 memoryload tradeoff for the considered MuPIR problem by proposing a novel achievable scheme and a tight converse. The proposed achievable scheme uses the idea of cacheaided interference alignment (CIA) developed in the literature by the same authors. The proposed converse uses a treelike decoding structure to incorporate both the decodability and privacy requirements of the users. While the optimal characterization of the cacheaided MuPIR problem is challenging in general, this work provides insight into understanding the general structure of the cacheaided MuPIR problem.more » « less

Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases without revealing the identity of the desired message. There has been significant recent progress on understanding fundamental informationtheoretic limits of PIR, and in particular the download cost of PIR for several variations. Majority of existing works however, assume the presence of replicated databases, each storing all the K messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of μKL bits, where K is the number of messages, L is the size of each message in bits, and μ ∈ [1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any (N, K), with normalized storage μ = t/N, where the parameter t can take integer values t ∈ {1, 2, ..., N}, we show that our proposed PIR scheme achieves a download cost of (1 + 1/t + 1/2 + ⋯ + 1/t K1 ). The extreme case when μ = 1 (i.e., t = N) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the informationtheoretically optimal download cost characterized by Sun and Jafar as (1 + 1/N + ⋯ +1/N K1 ). For the other extreme, when μ = 1/N (i.e., t = 1), the proposed scheme achieves a download cost of K. The most interesting aspect of the result is that for intermediate values of storage, i.e., 1/N <; μ <; 1, the proposed scheme can strictly outperform memorysharing between extreme values of storage.more » « less

null (Ed.)We consider the private information retrieval (PIR) problem from decentralized uncoded caching databases. There are two phases in our problem setting, a caching phase, and a retrieval phase. In the caching phase, a data center containing all the K files, where each file is of size L bits, and several databases with storage size constraint μ K L bits exist in the system. Each database independently chooses μ K L bits out of the total K L bits from the data center to cache through the same probability distribution in a decentralized manner. In the retrieval phase, a user (retriever) accesses N databases in addition to the data center, and wishes to retrieve a desired file privately. We characterize the optimal normalized download cost to be D * = ∑ n = 1 N + 1 N n  1 μ n  1 ( 1  μ ) N + 1  n 1 + 1 n + ⋯ + 1 n K  1 . We show that uniform and random caching scheme which is originally proposed for decentralized coded caching by MaddahAli and Niesen, along with Sun and Jafar retrieval scheme which is originally proposed for PIR from replicated databases surprisingly results in the lowest normalized download cost. This is the decentralized counterpart of the recent result of Attia, Kumar, and Tandon for the centralized case. The converse proof contains several ingredients such as interference lower bound, induction lemma, replacing queries and answering string random variables with the content of distributed databases, the nature of decentralized uncoded caching databases, and bit marginalization of joint caching distributions.more » « less