I. INTRODUCTION

Introduced by Chor et al. in 1995 [1], the problem of private information retrieval (PIR) seeks the most efficient way for a user to retrieve a desired message from N distributed databases (each holding a library of K messages) while keeping the desired message identity private from the databases. Sun and Jafar recently characterized the capacity of the PIR problem as C = (1 [2], [3], which is achieved by leveraging the idea of Blind Interference Alignment (BIA) originally introduced to exploit the diversity of coherence patterns in wireless interference networks [4].

Coded caching was originally proposed by Maddah-Ali and Niesen (MAN) in [5] for a shared-link caching system containing a server with a library of K equal-length files, which is connected to K u users through a noiseless sharedlink, each of which can store M files in its cache. Each user demands one file in the delivery phase. The MAN scheme uses a combinatorial design in the placement phase so that during the delivery phase multicast messages can simultaneously satisfy the demands of multiple users. It was proved in [6] that the MAN caching scheme is order optimal within a factor of 2 when K ≥ K u . In addition, the optimal memory-load tradeoff was characterized in [5] for the case where K = K u = 2. 1Under the constraint of uncoded cache placement and for worst-case load, the MAN scheme was proved to be optimal when K ≥ K u [7].

Characterization of the optimal memory-load trade-off for the cache-aided PIR problem, in which the effect of caching is taken into account, has gained significant attentions recently. Two different privacy models are commonly considered. In one line of research [8]- [10], the user-against-database privacy model is studied where individual databases are prevented from learning the single-user's demand. The author in [8] studied the case where a single cache-aided user is connected to a set of N replicated databases and showed that memory sharing between the memory-load pairs (0, 1+ 1

) and (K, 0) (i.e., split the messages and cache memory proportionally and then implement two PIR schemes on independent parts of the messages) is actually optimal if the databases are aware of the user's cached content. However, if the databases are unaware of the user's cached content, then there is an "unawareness gain" in capacity as shown in [9], [10]. Another line of research [11]- [13] deals with the user-against-user privacy model where users are prevented from learning each other's demands. The authors in [11] first formulated the coded caching with private demands problem where a shared-link caching system with demand privacy, i.e., any user should not learn anything about the demands of other users, was considered. The goal is to design efficient delivery schemes such that the communication load is minimized while preserving user demand privacy. Order optimal schemes were proposed based on the novel concept of virtual user. In [14], the authors studied the subpacketizaiton issues for this problem. Later, coded caching with private demands was extended to the Device-to-Device (D2D) network [12]. In general, the exact capacity characterization remains open for these problems.

This paper formulates the problem of cache-aided multiuser PIR (MuPIR), where each of the K u cache-equipped users aims to retrieve a message from N distributed databases while preserving the privacy of user demands given that the cached content of the users are known to the databases. Based on the novel idea of Private Cache-aided Interference Alignment (PCIA), we construct cache placement and private delivery phases achieving the non-trivial memory-load pairs

for the MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 databases. Different from the existing cache-aided interference algiment schemes in [15]- [18] which were designed for the cache-aided interference channels, our proposed private caching scheme is to let each server deliver symmetric messages (in order to keep privacy), each of which contains some uncached and undesired symbols (interferences) of each user. Our main strategy is to align these interferences for each user. We prove that the proposed scheme is optimal under the constraint of uncoded cache placement. Computer-aided investigation also shows that the proposed schemes are optimal in general when N = 2, 3.

II. PROBLEM FORMULATION

We consider a system with K u users, each of which aims to privately retrieve a message from N ≥ 2 replicated (noncolluding) databases (DBs). Each DB stores K independent messages, denoted by

Each user is equipped with a cache memory of size ML bits, where 0 ≤ M ≤ K. Let the random variables Z 1 , Z 2 , • • • , Z Ku denote the cached content of the users. The system operates in two phases, a cache placement phase followed by a private delivery phase. In the cache placement phase, the users fill up their cache memory without the knowledge of their future demands. It is assumed that the cached content of each user is a deterministic function of the messages W 1:K and is known to all DBs. In the private delivery phase, each user k ∈ [K u ] wishes to retrieve a message W θ k where θ

denote the demands of the users. We assume that θ is generated according to the uniform distribution over [K] Ku . Depending on θ and

N , and then send the query Q n , and the information available to DB n, i.e., W 1:K and Z 1:K . Therefore,

After collecting all the answers from the N DBs, the users should be able to recover their desired messages correctly with the help of their caches. This decodability requirement can be written as ∀k ∈ [K u ]:

where ε 1 → 0 as L → ∞. When ε 1 = 0, this corresponds to the zero decoding error case.

To preserve the privacy of the users' demands, from the viewpoint of any individual DB, the demand vector θ should be independent of all the information available to that DB, i.e., the following privacy constraint should be satisfied ∀n ∈ [N ]:

where

The load (or transmission rate) of the MuPIR problem, denoted by R, is defined as the average (over random demands) number of bits downloaded from the DBs per useful message bit. Let D denote the total number of bits broadcasted from the DBs, then

Note that R does not depend on θ, otherwise this leaks information of the user demands to the DBs. A memoryload pair (M, R) is said to be achievable if there exists a MuPIR scheme satisfying the decodability constraint (2) and the privacy constraint (3). The goal of the MuPIR problem is to design the cache placement and the corresponding private delivery phases such that the load is minimized. For any 0 ≤ M ≤ K, let R (M ) denote the minimal achievable load.

In addition, if users directly cache a subset of the library bits, the placement phase is referred to as uncoded cache placement.

We denote the minimum achievable load under the constraint of uncoded cache placement by R u (M ).

III. MAIN RESULT

In this section we present the main results of this paper. Theorem 1: For the cache-aided MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 DBs, the following load is achievable

Proof: The achievability proof of Theorem 1 is presented in Section IV where specific schemes are constructed based on the novel idea of PCIA achieving the memory-load pairs

). In addition, the memoryload pairs (0, 2) and (2, 0) are trivially achievable. By memory sharing, the lower convex envelope of the above four corner points can be achieved, which gives the achievable rate in Theorem 1.

Remark 1: Computer-aided investigation using the information theory toolbox [19] showed that the achievable rate provided in Theorem 1 is optimal when N = 2 and 3.

Theorem 2: For the cache-aided MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 DBs, the optimal memory-load trade-off under the constraint of uncoded cache placement is given by

Proof: For the achievability part, the corner points in Theorem 2 are the memory-load pairs (0, 2), ( 2(N -1)

2N -1 , N +1 2N -1 ), and (2, 0), which can be achieved by the same achievable schemes as Theorem 1.

For the converse part, under the constraint of uncoded cache placement, the converse bound for the original MAN caching problem without privacy constraint in [7] is also the converse for our considered problem. When M ∈ [0, 1], it was proved in [7] that

In addition, the converse bound for the single-user cache-aided PIR problem in [8] is also the converse for our considered problem since increasing the number of users while keeping demand privacy can only possibly increase the load. When

By combining Eqs. ( 7) and ( 8), the converse bound of Eq. ( 6) can be obtained, which coincides with the achievability.

IV. ACHIEVABILITY

In this section we provide the proof of Theorems 1 and 2 by showing the achievability of the non-trivial memoryload pairs

for the MuPIR problem with K = 2 messages, K u = 2 users and N ≥ 2 DBs. The design of the achievable schemes utilizes the novel idea of PCIA where certain undesired message symbols (i.e., interferences) are aligned into certain dimensions such that the users can decode their desired messages by solving linear equations after removing the aligned interference.

In this section we present the achievability of the memoryload pair ( N -1 2N , N +1 N ). We first provide an example to illustrate the basic design idea and then generalize the proposed scheme to arbitrary number of DBs.

Example 1: (Achievability of ( 1 4 , 3 2 )) Consider the MuPIR problem with K = 2 messages, K u = 2 users and N = 2 DBs. For simplicity, let W 1 = A and W 2 = B denote the two messages. Let θ = (θ 1 , θ 2 ) be the user demands. We next show that the memory-load pair ( 1 4 , 3 2 ) can be achieved. 1) Cache placement: Assume that each message consists of F = 4 symbols over some finite field F q , i.e, A = [4] for some prime power q. For this case, binary field is sufficient for the proposed scheme to work. Each user stores a linear combination of the message symbols, i.e.,

in which α i , β i , ∀i = 1, 2 are the linear combination coefficients randomly picked from [F 2 ] 1×2 \{[0, 0]}. Without loss of generality, we use the coefficients

2) Private delivery: In this phase, the users download an answer from each DB. These answers take the form of linear combinations of the message symbols. For different user demands θ = (θ 1 , θ 2 ), the linear combination coefficients are designed accordingly such that the users can correctly decode their desired messages while preserving demand privacy. More specifically, the answer from DB 1 consists of two linear combinations

The answer from DB 2 consists of four linear combinations

2,3 and

2,4 which are

in which the coefficients [1,1]} are subject to design. The answers can be written in a more compact form as

We next show how these coefficients can be designed according to different user demands (θ 1 , θ 2 ) such that decodabilty and privacy can be guaranteed. Due to space limitation, we will only illustrate the case of (θ 1 , θ 2 ) = (1, 2) and omit other cases, which can be achieved similarly. In this case, users 1 and 2 request A and B respectively. We require that the following six coefficient matrices to be full rank:foot_3

and u 1,1 and v 1,2 are chosen as

Now we show that with the above full rank and alignment conditions the users can correctly decode their desired messages.

From Eq. ( 18), we obtain

Since

e, the interferences B 3 and B 4 are aligned. Removing the interferences and due to rank([u 1,2 ; g 3 ]) = 2, the symbols A (3:4) can be solved from Eq. (21) as

From Eq. ( 18), we also obtain

Since

2) , i.e, the interferences A 1 , A 2 are aligned. Removing the interferences, B (1:2) can be solved from Eq. (23) as

Hence, both users can correctly decode A 3 , A 4 and B 1 , B 2 . Now, user 1 still needs A 1 , A 2 while user 2 needs B 3 , B 4 . For user 1, the interference term β 1 B T (1:2) in Z 1 can be eliminated since B 1 , B 2 are already available. Therefore, user 1 can decode A 1 , A 2 from

Similarly, for user 2, the interference term α 2 A T (3:4) can be eliminated since A 3 , A 4 are already available. Therefore, user 2 can decode B 3 , B 4 from

As a result, both users can correctly recover their desired messages.

We next show that how the specific coefficients are chosen such that user demand privacy can be preserved.

Privacy: Due to the full rank requirements and alignment conditions, it must hold that u 1,i , v 1,i = [1, 1], [0, 0], ∀i ∈ [2] and g j = [1, 1], [0, 0], ∀j ∈ [4]. Therefore, there are

For each choice, we can uniquely determine (g 1 , g 2 , g 3 , g 4 ) ∈ {[0, 1], [1, 0]} 4 for each demand (θ 1 , θ 2 ) ∈ [2] 2 according to the corresponding full rank and alignment conditions. If we employ each choice of the linear coefficients of the DBs with equal probability, then for any choice of the DB 1 linear combination coefficients, (θ 1 , θ 2 ) is equally likely to be (1, 2), (2, 1), (1, 1) or (2, 2) from the perspective of DB 1. On the other hand, there are also

2 according to the full rank and alignment conditions therein. If we employ each choice of the linear coefficients of the DBs with equal probability, then for any choice of the DB 2 linear combination coefficients, (θ 1 , θ 2 ) is equally likely to be (1, 2), (2, 1), (1, 1) or (2, 2) from the perspective of DB 2. Therefore, the proposed scheme is private.

Performance: Since D = 6 linear combinations are downloaded in total, the achieved load is R = D F = 3 2 . ♦ We next present the general achievable schemes for arbitrary number of databases. The cache placement and the corresponding private delivery phases are formally described as follows.

1) Cache placement: Let W 1 = A, W 2 = B denote the two messages. Each message is assumed to consist of F = 2N symbols over some finite field F q , i.e.,

Each user then stores N -1 linear combinations of the message symbols in its cache (therefore M = N -1 2N ), i.e.,

2) Private delivery: The answer of each DB consists of several linear combinations of the message symbols. More specifically, the answer of DB n ∈ [N -1] consists of two linear combinations

and the answer of DB N consists of four linear combinations

The linear coefficients g 1 , g 2 , g 3 , g 4 , u n,j , v n,j , ∀n ∈ [N -1], ∀j ∈ [2] belong to [F q ] 1×N \{0 N } and are designed according to the user demands.

In the private delivery phase, the users download all the 2N + 2 linear combinations from the N DBs. The linear combination coefficients of the answers are chosen according to θ such that both users can correctly decode their desired messages. In the following, we will focus on the case of θ = (1, 2) and omit the other demands, which can be designed similarly. In the case of (θ 1 , θ 2 ) = (1, 2), user 1 and 2 demand message A and B respectively. We let

and the linear coefficient vectors

are picked independently and uniformly at random from [F q ] 1×N \{0 N } such that with high probability, 3 the following six matrices are full rank

With such a design of the linear coefficients, we now demonstrate that the users can correctly recover their desired messages.

Due to the alignment condition of Eq. (40), we have A

(N +1:2N ) , i.e., the interfering symbols B (N +1:2N ) are aligned among the linear combinations 3 The base field q is assumed to be large enough such that the probability of the random matrices being full rank is arbitrarily close to 1.

Since the linear coefficient matrix on the RHS of Eq. ( 42) is full rank, A (N +1:2N ) can be solved from

Therefore, both users can correctly decode the symbols A (N +1:2N ) . Similarly, due to the alignment condition of Eq. (39), we have A

, the interfering symbols A (1:N ) are aligned among the linear combinations A

Since the linear coefficient matrix on the RHS of Eq. ( 44) is full rank, B (1:N ) can be solved from

Therefore, both users can correctly decode the packets B (1:N ) . Now the message symbols A (N +1:2N ) and B (1:N ) are available to both users. User 1 still needs A (1:N ) and user 2 still needs B (N +1:2N ) . For user 1, since B (1:N ) are already available, it obtains N -1 linear combinations of A (1:N ) according to Eq. ( 29). Together with A

(1:N ) , user 1 obtains N independent linear combinations of A (1:N ) , from which A (1:N ) can be solved as = g 4 B T (N +1:2N ) , user 2 obtains N independent linear combinations of B (N +1:2N ) , from which B (N +1:2N ) can be solved as

(47) Therefore, user 2 can correctly decode all the symbols B (1:2N ) of the desired message B. As a result, both users can correctly decode their desired messages.

Privacy: For any θ, for each DB n ∈ [N -1], its answer contains one linear combinations of A (1:N ) , B (1:N ) and one linear combination of A (N +1:2N ) , B (N +1:2N ) , which are generated randomly and independently from its viewpoint. For DB N , its answer contains four linear combinations of A (1:N ) , A (N +1:2N ) , B (1:N ) , and B (N +1:2N ) respectively, which are generated randomly and independently from its viewpoint. In addition, all of these linear combinations are generated independently to the cache content of each user. Since each individual DB does not know the exact full rank and alignment conditions, the user demands (θ 1 , θ 2 ) can be arbitrary from that DB's point of view. As a result, the proposed scheme is private.

Performance: Since D = 2N + 2 linear combinations are downloaded in total, the achieved load is

In this section we present the achievability of the memoryload pair ( 2(N -1)

2N -1 , N +1 2N -1 ), which is also based on the PCIA strategy. We provide an example first and then generalize the scheme to arbitrary number of databases.

Example 2: (Achievability of ( 2 3 , 1)) Consider the same setting as Example 1 and each user has a cache memory of M = 2 3 messages. We assume that each message consists of L = 3 bits, i.e., A = (A 1 , A 2 , A 3 ) and B = (B 1 , B 2 , B 3 ).

1) Cache placement: The cache placement is

2) Private delivery: The answer of each DB 1 consists of a linear combination

) and the answer of DB 2 consists of two linear combinations

2,2 = g 2 B T (1:3) where the linear coefficients

1×3 \{[0, 0, 0]} and are subject to design according to different user demands (θ 1 , θ 2 ). The answers from the DBs can be written in a more compact form as ⎡

In the private delivery phase, the users download all the three linear combinations from the two DBs. In the following, we will only illustrate the case of (θ 1 , θ 2 ) = (1, 2). In this case, we require that the following two coefficient matrices to be full rank: 4u

and

i.e., the symbols A 1 , A 3 are aligned among the linear combinations A

[(1,2)] 1

and A

. We next show that with the above full rank and alignment conditions, both users can correctly decode their desired messages.

For user 1, since

Then from Eq. (50), we obtain that

where

(54) Since A 1 , B 1 are already stored by user 1, it can correctly decode the desired symbols A 2 and A 3 . For user 2, since

-g 1,2 A 2 . Then from Eq. (50), we obtain that

where

(56) Since A 2 , B 2 are already stored by user 2, it can correctly decode the desired symbols B 1 and B 3 . Together with the cached symbols, both users can recover their desired messages.

Next we show how to choose the specific linear coefficients such that the user demand privacy can be preserved.

Privacy: From the full rank and alignment requirements, to preserve demand privacy, it must hold that u

For each choice, we can uniquely determine the DB 2 linear combination coefficients g 1 , g 2 for each (θ 1 , θ 2 ) ∈ [2] Since for different configurations of the symbol alignment and full rank coefficient matrices, different messages can be decoded by the users, each individual DB can not determine the actual user demands (θ 1 , θ 2 ). Therefore, the proposed scheme is private.

Performance: Since D = N + 1 linear combinations are downloaded in total, the achieved load is R = D F = N +1 2N -1 .

V. CONCLUSION

In this paper, we formulated the problem of cache-aided multiuser Private Information Retrieval (MuPIR) where the users wish to retrieve a set of messages from a set of distributed databases while keeping the user demands private from any individual database. For the MuPIR problem with two users, two messages and arbitrary number of databases, general achievable schemes utilizing the novel idea of PCIA were proposed for the memory-load pairs N -1 2N , N +1 N and ( 2(N -1)

2N -1 , N +1 2N -1 ). This is the very first achievability result on the cache-aided MuPIR problem with arbitrary number of databases. On-going directions include: 1) Characterization of the optimal memory-load trade-off for the MuPIR problem with two messages, two users and arbitrary number of databases; 2) Extending the achievability to more general cases where the number of messages, users and databases are arbitrary. Future directions may include extension to colluding databases and characterization of the optimal memory-load trade-off under the assumption of uncoded cache placement.