PIR refers to a problem where a client wishes to download, as efficiently as possible, one of the K files that are replicated among a set of distributed servers such that the servers cannot learn anything about the client's file selection [1], [2].
The PIR problem was studied in [3] from an informationtheoretic point of view to characterize the maximum number of bits of desired information that can be retrieved privately per bit of downloaded information. In [3], the authors showed that this quantity is (1+1/N +1/N 2 +• • •+1/N K-1 ) when a client wishes to retrieve one of the K files that are distributed in N replicated and non-colluding servers. This problem was subsequently extended to various scenarios. [4] considered a PIR problem where T of the N servers may collude and some of the servers may not respond. [5]- [7] studied PIR with N non-colluding servers, where each server stores an MDScoded version of the K files. [8], [9], extended the results to symmetric PIR, in which the privacy of both the client and the servers is considered.
In this paper, we study a PIR problem where the client wants to retrieve one of the K files that are replicated in N servers and T of these servers may collude. As reviewed in the next section, so far, only PIR with noiseless side information,
The authors are with the Department of Electrical Engineering and Computer Science, Wichita State University, Wichita, KS. This work was supported in part by NSF grant CCF-2047913. E-mails: {hassan.zivarifard, remi.chou}@wichita.edu. which means that the client has access to a subset of the files or portions of each file and their corresponding positions in the original files, has been studied in the literature. By contrast, in our problem setting, the client has a noisy version of each file which is obtained by passing each file through a discrete memoryless test channel. As depicted in Fig. 1, we assume that there are D ≤ K different test channels whose statistics are public knowledge and known by the client and the servers. We denote the mapping between the files and the test channels by M. We study this problem when the client wants to preserve the privacy of both the intended file and the mapping M, and we derive the optimal download rate.
As identified in [10], three main models for PIR with side information have been studied in the literature, which are summarized in the following.
• PIR with side information globally known by all the terminals: The effect of side information on the informationtheoretic capacity of the PIR problem was first studied in [11], where the author considers a PIR problem in which a client wishes to privately retrieve one out of K files from N replicated non-colluding servers. Specifically, in [11], the client has a local cache that can store any function of the K files. • PIR with non-private side information, where the privacy of the side information is not required: The single-server PIR problem where the client has access to a subset of the files and wants to protect only the identity of the desired file, is introduced and solved in [12]. An achievability result for the multiserver case is also derived in [12], and was later shown to be optimal in [13]. Single-server PIR when the client knows M files out of K files, or a linear combination of M files, has further been studied in [14]- [16] under various scenarios. Also, a multiserver PIR when the client has a noisy version of the desired file is studied in [17].
• PIR with private side information, where the joint privacy of the file selection and the side information is required: [12] derived an achievable rate region for N replicated and non-colluding servers. PIR from N replicated and non-colluding servers, where a cache-enabled client possesses side information, in the form of uncoded portions of the files, that is unknown to the servers, is studied in [18]. Also, PIR from N replicated and non-colluding servers when the client knows M files out of K files as side information, and each server knows the identity of a subset of the side information files, is studied in [19].
In [10], the authors studied the PIR problem where the client wishes to retrieve one of the K files from N replicated servers, when T of the servers may collude, and the client has access to M files in a noiseless manner. This problem is extended to the case where the client wants to retrieve multiple files privately in [20]. Difference between our model and previous models: In this paper, we focus on PIR with private side information. Note that the side information in the PIR problems in [10]- [16], [18]- [22] is always noiseless, in the sense that all the side information available at the client corresponds to subsequences of each file and the client knows the corresponding symbol positions in the original files. By contrast to [10]- [16], [18]- [22], the side information in this paper is noisy, for instance, if the test channels are Binary Symmetric Channels (BSCs), then the client does not know which information bits have been flipped by the BSCs and which ones have not been flipped.
Previous works recovered as special case of our model: The problem studied in this paper subsumes the PIR problem [3], the PIR problem with colluding servers [4], the PIR problem with noiseless private side information [12,Theorem 2], the PIR problem with private side information under storage constraints [18], and the PIR problem with colluding servers and noiseless private side information [10] as special cases.
Let N * be the set of positive natural numbers, and R be the set of real numbers. For any a, b ∈ N * such that a ≤ b, [a : b] denotes the set {a, a + 1, . . . , b}, [a] denotes the set {1, 2, . . . , a}. Random variables are denoted by capital letters and their realizations by lower case letters. Superscripts denote the dimension of a vector, e.g., X n . For a set of indices I ⊂ N * , X I denotes (X i ) i∈I . E X [•] is the expectation with respect to the random variable X. The cardinality of a set is denoted by
.
Consider a client and N servers, where up to T of these N servers may collude, and each server has a copy of K files of length n. Additionally, consider a set of D test channels, whose transition probabilities are known to the client and the servers, and whose outputs take value in finite alphabets. We assume that the client has noisy side information about all the K files in the sense that each file is passed through one of the D test channels, and the output of this test channel is
PIR with private noisy side information and T -colluding servers, where the side information about a specific file is obtained by passing this file through one of D possible discrete memoryless test channels
, where D ≤ K, i.e., for j ∈ [K], there exists some i ∈ [D] such that Y n j is the output of channel C (i) when X n j is the input. Here, X n i i∈[K] are the K files that are replicated in N servers, (Q i ) i∈[N ] are the queries for the servers, and (A i ) i∈[N ] are the corresponding answers of the servers. Z is the index of the client's file selection and X n Z is the file desired by the client.
available at the client but not the servers, as depicted in Fig. 1.
The mapping M between the files and the test channels is not known at the servers. The objective of the client is to retrieve one of the files such that the index of this file and the mapping M are kept secret from the servers.
where U is uniformly distributed over X and V i and V j are the outputs of C (i) and C (j) , respectively, when U is the input. A PIR protocol with private noisy side information and parameters K, n, N, D,
[K] uniformly distributed over X n , which represent K files shared at each of the N servers;
• a mapping M chosen at random from the set
this mapping is only known at the client and not at the servers; • for each file X n i , where i ∈ [K], the client has access to a noisy version of X n i , denoted by Y n i,M(i) , which is the output of the test channel C (M(i)) when X n i is the input; • the random variable Z is uniformly distributed over [K] and represents the index of the file that the client wishes to retrieve, i.e., the client wants to retrieve the file X n Z .
• a stochastic and one-to-one query function
where Q i is a finite alphabet;
and operates as follows, 1) the client creates the queries
, and sends it to Server i ∈ [N ]; we assume that the queries must be of negligible length compared to the file length n, i.e., log
, and sends it to the client; therefore,
3) finally, the client computes an estimate of
. Therefore, the probability of error at the client is,
, is the rate of the PIR protocol and is random with respect to Q [N ] , which makes the protocol a variable length coding scheme. We also define the expected rate of the protocol as
We keep the index of the desired file Z and the mapping M private from the servers.
). An expected rate R ∈ R + is achievable with private noisy side information, when up to T servers may collude, if there exists PIR protocols such that, for any set T ⊆ [N ] such that |T | = T ,
The privacy metric (3b) means that the client file choice Z and mapping M must be kept secret from any T colluding servers. The supremum of all achievable rates is referred to as the PIR capacity with private noisy side information, and is denoted by C PIR-PNSI .
In Example 1, Example 2, and Example 3, we show that our problem setup recovers the problem setup for PIR with colluding servers [4], PIR with colluding servers and noiseless side information [10], [12], and PIR with private side information under storage constraints [18]. Then, we illustrate our definitions when K = D = 2 and T = 1 in Example 4.
Example 1 (PIR with colluding servers). When D = 1 and the test channel is a BEC with parameter ϵ = 1, then the client has no side information about the files. In this case, Definition 1 reduces to PIR without side information as introduced in [4], and the privacy constraint in Definition 2 is equivalent to the privacy constraint in [4].
Example 2 (PIR with private noiseless side information). When D = 2 and the test channels are BECs with parameters ϵ 1 = 0, and ϵ 2 = 1, the client has access to d 1 files in a noiseless manner as side information. This case corresponds to PIR with side information as introduced in [12, Theorem 2] for non-colluding servers and in [10, Theorem 1] for colluding servers.
Example 3 (PIR with private side information under storage constraints). Suppose that T = 1, D = M + 1, for M ∈ N * and M ≤ K, the test channels are BECs with parameters andd
. This problem setup, under the privacy constraint in Definition 2, is related to the problem studied in [18]. The difference with [18] is that the positions of the erasures are known at the servers in [18], whereas in our setting, the positions of the erasures are random and unknown at the servers. Therefore, the optimal download rate for our problem setup in this example might be higher than the download rate in [18]. However, we will show in the next section that the same download rate as in [18] is achievable. be the side information about X n i , i ∈ {1, 2}, available at the client but unavailable at the server, where Y n i,M(i) is the output of the test channel C M(i) when the input is X n i . Note that M can take two values (with the notation introduced in Section II):
When Z = 1, since there are two different possibilities for the side information about X n 1 , that are Y n 1,1 and Y n 1,2 , we define,
Similarly, when Z = 2, since there are two different possibilities for the side information about X n 2 at the server, that are Y n 2,1 and Y n 2,2 , we define,
Therefore, the probability of error in (2), by taking lim sup when n → ∞, is equal to
In this section, we provide the main results of the paper and present some examples that recover and extend known results. Theorem 1. Consider K files that are replicated in N servers where up to T of them may collude. Then, the capacity of PIR with private noisy side information is
where
, and for i, j ∈ N * , d [i:j] ≜ j t=i d t , when i ≤ j, and d [i:j] ≜ 0, when i > j.
Proof. The achievability proof, which is outlined here, is based on source coding with side information and the achievability schemes in [4], [10]. We use a nested random binning scheme and assign D nested random bin indices to each file
. Specifically, the ℓ th random bin indices of all the files, referred to as ℓ th database, enable lossless reconstruction of the d ℓ files that are associated with the test channel C (ℓ) . Therefore, by downloading the database ℓ, the client, in addition to being able to reconstruct the d ℓ files that are associated with the test channel C (ℓ) , also receives the ℓ th random bin indices of all the other files. The achievability scheme consists in successively downloading each of the D databases, in ascending order, by using the same coding scheme and query structure as [10], for each database. The details of the proof are available in Section V-A. The converse proof is omitted due to the space limitation and is available in [23].
Remark 1 (Index of random variables). Since all the files are generated according to the same distribution, namely, the uniform distribution over X n , the index 1 of X 1 and Y 1,ℓ in Theorem 1 can be replaced with any other index i ∈ [K].
Corollary 1. Consider K files, that are replicated in N servers where up to T of them may collude. Additionally, the test channels are BECs with parameters (ϵ i ) i∈[D] ∈ [0, 1] D such that ϵ i < ϵ j , for i, j ∈ N * and i < j. Then, the capacity of PIR with private noisy side information is
Example 5 (No side information). In Corollary 1, if we set D = 1, and ϵ 1 = 1, which means that the client has no side information and d D = K, then the capacity result in Corollary 1 reduces to [4, Theorem 1], i.e.,
.
Example 6 (Private noiseless side information). In Corollary 1, if we set D = 2 and T = 1, ϵ 1 = 0, which means that the client knows d 1 files as side information in a noiseless manner, and ϵ 2 = 1, which means that there is no side information about d 2 files, then the capacity result in Corollary 1 reduces to [12, Theorem 2], i.e.,
.
Example 7 (PIR with private side information under storage constraints).
Note that, this result is stronger than that of [18, Theorem 1], since in [18] it is assumed that the client knows the first r i bits, for i ∈ [M ], of M randomly selected files, whereas, in our setting, the r i bits of side information for file i are chosen at random and we obtain the same capacity.
A high level description of the achievability scheme is provided after Theorem 1. Assume that each file is of length n = N K with symbols in a sufficient large finite field F q . Fix δ > 0.
1) Random Binning: For every file x n i , i ∈ [K], assign D random bin indices as follows. For ℓ ∈ [D], randomly and independently assign a bin index j (i) ℓ ∈ J ℓ ≜ q n ℓ to x n i , where q ℓ ≜ q R ℓ , with R ℓ > 0, to be defined later, and R 0 ≜ 0.
We refer to M ℓ ≜ j
(1) ℓ , . . . , j
as the database ℓ. The query is constructed to retrieve each one of the M ℓ databases in ascending order.
2) Query Structure Construction: The client constructs the query in D different levels. In the first level, we apply to the database M 1 the same query structure as in [4], which consists of K sublevels. In the level ℓ ∈ [2 : D], we apply to the database M ℓ the same query structure as in [10], which also consists of K sublevels. Specifically, as in [10], the k ℓ th sublevel consists of sums of k ℓ symbols, which are called k-sums. There are K k ℓ different types of k-sums and (N -T ) k ℓ -1 T K-k ℓ different instances of each type in the k ℓ th sublevel. Hence, the total number of symbols that will be downloaded from each server is
3) Query Specialization: For ℓ ∈ [D], we do the query structure construction and query specialization without considering availability of any side information as in [10], and denote this scheme by Π ℓ . Then, we do query redundancy removal based on availability of noiseless side information similar to [10]. Specifically, after each level ℓ ∈ [D], the client is able to recover the d ℓ files that are associated with the ℓ th test channel, and therefore considering the files that it has decoded in the previous levels, the client knows X n in level ℓ + 1.
For level ℓ = 1, the client does not have any noiseless side information and cannot perform query redundancy removal but, for level ℓ ∈ [2 : D], since it has recovered ℓ-1 t=1 d t files, the client can perform query redundancy removal. For each ℓ ∈ [D] and for each server, let p ℓ,1 denote the number of symbols downloaded with Π ℓ . Out of these p ℓ,1 symbols, we denote by p ℓ,2 < p ℓ,1 the number of symbols that the client already knows by decoding some of the files in the previous levels. For ℓ ∈ [D], let U ℓ,j ∈ F p ℓ,1 q ℓ denote the symbols downloaded from the j th server with Π ℓ . For each server, use a systematic (2p ℓ,1 -p ℓ,2 , p ℓ,1 ) Maximum Distance Separable (MDS) code [24], with generator matrix
] ⊺ to encode the p ℓ,1 symbols into 2p ℓ,1 -p ℓ,2 symbols, of which p ℓ,1 are systematic, and p ℓ,1 -p ℓ,2 are parity symbols, such that it is sufficient to download V ⊺ p ℓ,1 ×(p ℓ,1 -p ℓ,2 ) U ℓ,j . For level ℓ = 1, since the client does not have any noiseless side information about M 1 , p 1,2 = 0.
4) Decoding: For ℓ ∈ [D], after reconstructing (j
M , the client declares Xn t to be an estimate of the sequence X n t if it is a unique sequence that is typical with Y n t,ℓ in the bin (j
. Ac-cording to the Slepian-Wolf theorem, e.g. [25], the decoding is successful, i.e., P Xn t ̸ = X n t ----→ n→∞ 0, if
5) Rate Calculation: Similar to [10], for the scheme Π ℓ , the total number of downloaded symbols from each server is 22), ( 25)], we have
Therefore, the transmission rate for the level ℓ is, Therefore, the total transmission rate is,
) Privacy Analysis: Note that for all the D levels, the client does not use any side information to construct the queries. Indeed, the systematic MDS codes of all the levels in the query redundancy removal do not depend on the side information that the client obtain after each level. The decoding in 4) starts when the client collects all the answers from the servers for all the D levels. Thus, the side information is used only when the client collects all the answers from the servers for all the D levels. Therefore, privacy is inherited from the privacy of the schemes in [10] and [4].
Authorized licensed use limited to: University of Texas at Arlington. Downloaded on October 10,2023 at 16:29:39 UTC from IEEE Xplore. Restrictions apply.
When D = 1 and the test channel is a Binary Erasure Channel (BEC) with parameter ϵ 1 = 1, or when D =
and the test channels are BECs with parameters ϵ 1 = 0 and ϵ 2 = 1, which correspond to PIR without side information in[4] and PIR with side information in[10], respectively, it is shown in[4],[10] that there is no loss of generality by making this assumption. In general, allowing the query rate to be non-negligible with the file length n is a different problem. However, similar to [12, Remark 1] and[18], this assumption can also be removed in our converse proofs when the queries Q i , for i ∈ [N ], are only allowed to depend on (Z, M).
IEEE International Symposium on Information Theory (ISIT)